【文章內(nèi)容簡介】 = queue[front]； front = front +1； 顯然，對于第 1個元素和其它元素的讀操作，將出現(xiàn)不一致。 判別隊(duì)列為空的條件也將復(fù)雜化。 下一頁 上一頁 停止放映 第 40/89 頁 關(guān)于隊(duì)列表示的約定 為解決這個問題，約定如下： 隊(duì)頭指針 front總是指向隊(duì)頭元素的前一個位置； 隊(duì)尾指針 rear總是指向隊(duì)尾元素的位置。 這樣一來，無論對什么元素，出隊(duì)操作都是一樣的。 front = front +1 ； x = queue [front ]； front rear a1 a2 … a n 下一頁 上一頁 停止放映 第 41/89 頁 舉例：順序隊(duì)列的入隊(duì)、出隊(duì)操作 （ A）空隊(duì)列 （ B） A、 B、 C、 D、 E入隊(duì) （ C） A、 B、 C出隊(duì) A B C D E front rear front rear D E front rear 入隊(duì)時， rear在變 出隊(duì)時， front在變 下一頁 上一頁 停止放映 第 42/89 頁 舉例 :順序隊(duì)列入隊(duì)、出隊(duì)操作 （ D） F、 G、 H入隊(duì) (E） D、 E、 F、 G、 H出隊(duì)，出現(xiàn)假 ? 溢出 ? 注： 一方面隊(duì)列中是空的，另一方面又出現(xiàn)溢出。顯然，這是邏輯設(shè)計(jì)上的問題。 front front rear D E F G H rear 下一頁 上一頁 停止放映 第 43/89 頁 解決假溢出的方法 如果使當(dāng) rear = MAXSIZE+1 時，即超過隊(duì)列末端時，令 rear = 1；從而使隊(duì)列的首尾相連接。 用表達(dá)式描述 : if （ rear MAXSIZE ） rear = 1 。 else rear = rear + 1 。 這就是循環(huán)隊(duì)列的處理思想。 下一頁 上一頁 停止放映 第 44/89 頁 循環(huán)隊(duì)列 設(shè)定 queue[1]接在 queue[MAXSIZE]之后 ,使得 if （ rear MAXSIZE ） rear = 1 。 else rear＝ rear + 1。 這樣構(gòu)成循環(huán)隊(duì)列。 下一頁 上一頁 停止放映 第 45/89 頁 循環(huán)隊(duì)列的指針移動 （ 1） 隊(duì)頭指針 front = front% MAXSIZE + 1； 等價于： if（ front MAXSIZE ） front = 1 。 else front ＝ front + 1。 （ 2）隊(duì)尾指針 rear = rear % MAXSIZE +1 ； 等價于： if （ rear MAXSIZE ） rear = 1。 else rear＝ rear + 1。 循環(huán)隊(duì)列在指針移動處理時與一般隊(duì)列不同： 下一頁 上一頁 停止放映 第 46/89 頁 循環(huán)隊(duì)列隊(duì)空、隊(duì)滿條件 隊(duì)空條件 front = rear ； 隊(duì)滿條件 front = rear % MAXSIZE +1 rear front 1 2 3 MAXSIZE ... 1 2 3 4 ... i rear i+1 front MAXSIZE a1 a2 a3 ai1 示例 … 下一頁 上一頁 停止放映 第 47/89 頁 循環(huán)隊(duì)列入隊(duì)操作 算法 112描述 : step1 判別隊(duì)列是否已滿 。 step2 隊(duì)尾指針后移一個位置 ,將新結(jié)點(diǎn)元素值存入當(dāng)前結(jié)點(diǎn)單元。 數(shù)據(jù)結(jié)構(gòu)定義： define MAXSIZE n int queue[MAXSIZE]； int front， rear； 下一頁 上一頁 停止放映 第 48/89 頁 循環(huán)隊(duì)列入隊(duì)操作程序 addqueue(int x) { if (front = = rear % MAXIZE +1 ) { printf(“循環(huán)隊(duì)列已滿 \n”)。 exit(1)。 } else { rear = rear % MAXSIZE +1。 queue[rear] = x 。 } } 下一頁 上一頁 停止放映 第 49/89 頁 循環(huán)隊(duì)列出隊(duì)操作 算法 113描述 : step1 判別隊(duì)列是否為空 。若空 ,則顯示隊(duì)列 ‘ 下溢 ’ 。 step2 隊(duì)頭指針后移一個位置。 下一頁 上一頁 停止放映 第 50/89 頁 循環(huán)隊(duì)列出隊(duì)操作程序 delqueue( ) { int y。 if ( front = = rear ) { printf( “ 循環(huán)隊(duì)列已空 \n”) 。 y = 1 ； } else { front = front % MAXSIZE +1 ； y = queue[front] ； } return y ； } 下一頁 上一頁 停止放映 第 51/89 頁 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu) 用帶頭結(jié)點(diǎn)的單鏈表作為隊(duì)列的存儲結(jié)構(gòu)，稱為隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)。 存儲結(jié)構(gòu)的 C語言描述， struct qnode { int data ； struct qnode * next； } ； typedef struct qnode QNODE ； QNODE *front， *rear； data next 數(shù)據(jù)域 指針域 下一頁 上一頁 停止放映 第 52/89 頁 鏈隊(duì)列為空的表示 鏈隊(duì)列為空 = 表示形式： front rear ^ front rear ^ ... an a2 a1 非空隊(duì)列 下一頁 上一頁 停止放映 第 53/89 頁 鏈隊(duì)列為滿的條件 鏈滿的條件為 : T = NULL T 為新創(chuàng)建的結(jié)點(diǎn) ,當(dāng)沒有存儲空間時 ,T為 NULL,表示鏈隊(duì)列已滿。 下一頁 上一頁 停止放映 第 54/89 頁 鏈隊(duì)列的入隊(duì)操作 算法 114描述 : step1 申請建立一個新結(jié)點(diǎn) T。 step2 判別 T是否為空 。若空 ,表示 隊(duì)列已滿 。 step3 非空 ,將 T插入鏈中 ,修改 rear指針。 下一頁 上一頁 停止放映 第 55/89 頁 鏈隊(duì)列的入隊(duì)操作 addqueue(int x) { QNODE *t。 t = (QNODE*)malloc(sizeof(QNODE))。 if （ t = = NULL） { printf（ ? 內(nèi)存無可用空間 \n”)。 exit(1)。 } else { rear next = t。 rear = t。 t data = x。 t next = NULL 。 } } 下一頁 上一頁 停止放映 第 56/89 頁 鏈隊(duì)列的出隊(duì)操作 當(dāng)隊(duì)列長度大于 1時 ,只修改隊(duì)頭指針即可。 an ^ front rear Queue Queue front rear ^ an ^ T ... Queue Queue front rear rear front a1 an ^ a1 a2 a2 ^ ... an ^ 出隊(duì)操作要考慮兩種情況 。 當(dāng)隊(duì)列長度為 1時 ,除了修改隊(duì)頭指針外 ,還要修改隊(duì)尾指針。 下一頁 上一頁 停止放映 第 57/89 頁 鏈隊(duì)列的出隊(duì)操作 算法 115描述 : step1 判別隊(duì)列是否為空 。若空 ,則顯示 隊(duì)列 ‘ 下溢 ’ 。 step2 非空 ,則判別隊(duì)長度是否為 1。 不為 1,修改頭指針 。 為 1,則修改頭、尾指針； step3 釋放 T。 下一頁 上一頁 停止放映 第 58/89 頁 鏈隊(duì)列的出隊(duì)操作的程序 delqueue( ) { int x。 QNODE *t。 if ( front = = rear) { printf(“鏈隊(duì)列已空 \n”)。 exit(1) 。 } else { t = frontnext。 x = t data 。 frontnext = tnext