【正文】 (指向頭結(jié)點(diǎn) )。 循環(huán)隊(duì)列 ——隊(duì)列的順序表示和實(shí)現(xiàn) 和順序棧相類似 ， 在隊(duì)列 Q的順序存儲(chǔ)結(jié)構(gòu)中 ， 除了用一組地址連續(xù)的存儲(chǔ)單元依次存放從隊(duì)列頭到隊(duì)列尾的元素之外 ， 尚需附設(shè)兩個(gè)指針 front和 rear分別指示隊(duì)列頭元素和隊(duì)列尾元素的位置 。 為了在 C語(yǔ)言中描述方便起見 ， 在此我們約定：初始化建空隊(duì)列時(shí) ， 令 front = rear = 0， 每當(dāng)插入新的隊(duì)列尾元素時(shí) ， “ 尾指針增1” ；每當(dāng)刪除隊(duì)列頭元素時(shí) ， “ 頭指針增 1” 。 因此 ，在非空隊(duì)列中 ， 頭指針始終指向隊(duì)列頭元素 ， 而尾指針始終指向隊(duì)列尾元素的下一個(gè)位置 。 如圖 。 (a)空隊(duì)列； (b)J J2和 J3， 相繼入隊(duì)列； (b)J1和 J2相繼被刪除； (d)J J5和 J6相繼插入隊(duì)列之后 J J4被刪除 。 (a) (b) ( c ) (d) 圖 頭 、 尾指針和隊(duì)列中元素之間的關(guān)系 J1 J2 J3 J3 J5 J6 假設(shè)當(dāng)前為隊(duì)列分配的最大空間為 6， 則當(dāng)隊(duì)列處于圖(d)的狀態(tài)時(shí)不可再繼續(xù)插入新的隊(duì)尾元素 ， 否則會(huì)因數(shù)組越界而遭致程序代碼被破壞 。 然而此時(shí)又不宜如順序棧那樣 ， 進(jìn)行存儲(chǔ)再分配擴(kuò)大數(shù)組空間 ， 因?yàn)殛?duì)列的實(shí)際可用空間并未占滿 。 一個(gè)較巧妙的辦法是將順序隊(duì)列臆造為一個(gè)環(huán)狀的空間 ， 如圖 ， 稱之為循環(huán)隊(duì)列 。 1 0 maxsize1 圖 空閑空間 0 1 2 3 4 5 6 7 front rear front 0 1 2 3 4 5 6 7 rear front 0 1 2 3 4 5 6 7 B C rear 隊(duì)列初值 A進(jìn) 隊(duì) B, C進(jìn) 隊(duì) A退 隊(duì) B退 隊(duì) front A A 0 1 2 3 4 5 6 7 B C rear A front 0 1 2 3 4 5 6 7 B C rear front 6 7 0 1 2 3 4 5 X W Y Z rear = rear+1 ( ) % maxsize 6 7 0 1 2 3 4 5 B A C rear A出 隊(duì) B出 隊(duì) front = front+1 ( ) % maxsize front ？ 空 C出 隊(duì) front front= =rear A B C D ？ 滿 rear C進(jìn) 隊(duì) front= =rear ？如何區(qū)別滿和空 6 7 0 1 2 3 4 5 X W Y Z A B C 方法一 ： 增加一個(gè)存儲(chǔ)單元 n 用于存儲(chǔ)隊(duì)列的長(zhǎng)度 n==0 空 n==maxsize 滿 方法二 ： 利用隊(duì)列中最后一個(gè) 存儲(chǔ)單元標(biāo)志滿 (常用 ) 空： front==rear 滿 : rear front front = = rear +1 ( )%maxsize 從上述分析可見 ， 如果用戶的應(yīng)用程序中設(shè)有循環(huán)隊(duì)列 ， 則必須為它設(shè)定一個(gè)最大隊(duì)列長(zhǎng)度；若用戶無法估計(jì)所用隊(duì)列的最大長(zhǎng)度 ， 則宜采用鏈隊(duì)列 。 循環(huán)隊(duì)列類型的模塊說明如下： //— — — — —循環(huán)隊(duì)列 ——隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) — — — — — define MAXQSIZE 100 //最大隊(duì)列長(zhǎng)度 typedef struct { QElemType *base； //初始化的動(dòng)態(tài)分配存儲(chǔ)空間 int front； //頭指針 ， 若隊(duì)列不空 ， 指向隊(duì)列頭元素 int rear； //尾指針 ， 若隊(duì)列不空 ， 指向隊(duì)列尾元素的下一個(gè)位置 }SqQueue ； //循環(huán)隊(duì)列的基本操作的算法描述 Status InitQueue (SqQueue amp。Q){ //構(gòu)造一個(gè)空隊(duì)列 Q =( QElemType)malloc (MAXQSIZE*sizeof(QElemType))； if(!)exit(OVERFLOW)； //存儲(chǔ)分配失敗 = = 0； return OK； } Int QueueLength (SqQueue Q){ //返回 Q的元素個(gè)數(shù) ， 即隊(duì)列的長(zhǎng)度 return( – + MAXQSIZE) % MAXQSIZE； } Status EnQueue (SqQueue amp。Q， QElemType e){ //插入元素 e為 Q的新的隊(duì)尾元素 if((+1)％ MAXQSIZE==) return ERROR； //隊(duì)列滿 [] = e； = (+1) ％ MAXQSIZE； return OK； } Status DeQueue (SqQueue amp。Q， QElemType amp。e){ //若隊(duì)列不空 ， 則刪除 Q的隊(duì)頭元素 ， 用 e返回其值 ， 并返回 OK //否則返回 ERROR if ( = = ) return ERROR； e = [ ]； = (+1)％ MAXQSIZE； return OK； } 小 結(jié) 棧 隊(duì)列 共同點(diǎn)： 線性表 基本運(yùn)算受限制的 不同點(diǎn)： 一端插入和刪除 表尾（ 棧頂 ） 一端插入 表尾（ 隊(duì)尾 ） 另一端刪除 表頭（ 隊(duì)頭 ） 操作原則： 后進(jìn)先出 先進(jìn)先出 基本運(yùn)算： push(s,x) pop(s) empty(s) enqueue(q,x) dequeue(q) empty(q) 存儲(chǔ)結(jié)構(gòu)： 順序棧 鏈棧 順序隊(duì)列 循環(huán)隊(duì)列（空、滿） 鏈?zhǔn)疥?duì)列 兩個(gè)棧共享（空、滿） 復(fù)習(xí)二 知識(shí)點(diǎn) 棧和隊(duì)列的定義、特性及其基本運(yùn)算的定義 棧和隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn)（循環(huán)隊(duì)列） 棧和隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)以及基本運(yùn)算的實(shí)現(xiàn) 棧與遞歸的實(shí)現(xiàn) 內(nèi)容精要 棧的定義和術(shù)語(yǔ) 棧 棧頂 棧底 棧的長(zhǎng)度 空棧 棧的特性 由于棧的插入、刪除操作是限制在棧頂進(jìn)行的，因而后進(jìn)棧的元素必然是先出棧。所以棧是“后進(jìn)先出”表，簡(jiǎn)稱 LIFO表。 棧的順序存儲(chǔ)結(jié)構(gòu) 棧的順序存儲(chǔ)結(jié)構(gòu)是用一片地址連續(xù)的存儲(chǔ)單元依次存放棧底到站頂?shù)臄?shù)據(jù)元素，并設(shè)置指針指示棧頂位置。這種方式表示的棧稱為順序棧。在 C語(yǔ)言中，順序棧也可以采用靜態(tài)和動(dòng)態(tài)兩種不同的方式。 在棧的順序存儲(chǔ)結(jié)構(gòu)上運(yùn)算的實(shí)現(xiàn) 在靜態(tài)分配方式下，棧空條件為 ==0， 棧滿條件為 ==maxsize； 在動(dòng)態(tài)分配方式下，?？諚l件為==， 棧滿條件為 == maxsize。 運(yùn)算時(shí)入棧操作首先應(yīng)檢查棧是否已滿。在靜態(tài)分配方式下，棧滿情況下要插入元素則產(chǎn)生上溢出錯(cuò)誤，插入失??；在動(dòng)態(tài)分配方式下，若棧滿時(shí)要插入元素，則可向系統(tǒng)申請(qǐng)分配一個(gè)存儲(chǔ)空間增量 StackIncrement，然后再行插入。 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)及運(yùn)算的實(shí)現(xiàn) 棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)又稱為鏈?zhǔn)綏?，它是運(yùn)算受限的單鏈表。操作時(shí)無需考慮上溢出問題。插入、刪除運(yùn)算的操作方法與單鏈表操作相似，只是鏈棧是限制在棧頂操作而已。 隊(duì)列的定義和術(shù)語(yǔ) 隊(duì)列 隊(duì)頭 隊(duì)尾 隊(duì)列的長(zhǎng)度 隊(duì)列的特性 由于隊(duì)列的輸入、輸出操作分別在隊(duì)的兩端進(jìn)行，因此先入隊(duì)的元素必然先輸出 (First In First Out)， 故隊(duì)列又稱為先進(jìn)先出表，簡(jiǎn)稱 FIFO表。 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu) 隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)是用一片地址連續(xù)的存儲(chǔ)單愿意次存入從對(duì)頭到隊(duì)尾的元素。在 C語(yǔ)言中用一個(gè)向量來實(shí)現(xiàn)，同時(shí)還需要用隊(duì)頭指針和隊(duì)尾指針分別指示隊(duì)頭和隊(duì)尾的位置。順序隊(duì)列在工作過程中會(huì)遇到假溢出或假滿。為解決這一問題，一般將順序隊(duì)列組成循環(huán)隊(duì)列，即將隊(duì)列的頭、尾臆想為相連的，整個(gè)對(duì)列為一個(gè)環(huán)，頭、尾指針分別指向隊(duì)頭和隊(duì)尾。 在循環(huán)隊(duì)列上運(yùn)算的實(shí)現(xiàn) 隊(duì)空條件： ==。 隊(duì)滿條件：為避免在隊(duì)滿是隊(duì)頭指針和隊(duì)尾指針也是重合的情況，規(guī)定隊(duì)列中還有一個(gè)空的存儲(chǔ)單元時(shí)為隊(duì)滿，即為 ==(+1)MOD maxsize(MOD為取余運(yùn)算符）。因而，這種循環(huán)隊(duì)列不適合用動(dòng)態(tài)數(shù)組作為存儲(chǔ)結(jié)構(gòu)。 初始化、出隊(duì)、入隊(duì)運(yùn)算實(shí)現(xiàn)（略）。 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是一個(gè)運(yùn)算受限的單鏈表，即限制在對(duì)頭輸出、隊(duì)尾輸入。為了運(yùn)算方便，通常給鏈隊(duì)列添加一個(gè)頭結(jié)點(diǎn)，且令對(duì)頭指針指向頭結(jié)點(diǎn)。鏈?zhǔn)疥?duì)列上運(yùn)算的實(shí)現(xiàn)與單鏈表相似。