棧棧的應用隊列隊列的應用第三章棧和隊列3.4隊列3.4.1抽象數據類型隊列的定義

隊列(Queue)也是一種運算受限的線性表。它只允許在表的一端進行插入，而在另一端進行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。（a0,a1,...,ai-1,ai,ai+1,…,an-1）插入刪除例如：排隊購物。操作系統中的作業排隊。先進入隊列的成員總是先離開隊列。因此隊列亦稱作先進先出(FirstInFirstOut)的線性表，簡稱FIFO表。a0a1a2……an-1rear隊頭隊尾front隊列的示意圖隊列的特點先進先出說明：第一個入隊的元素在隊頭，

最后一個入隊的元素在隊尾，第一個出隊的元素為隊頭元素，最后一個出隊的元素為隊尾元素隊列的抽象數據定義見書Ｐ593.4.2非循環隊列和循環隊列

分配一塊連續的存儲區域來存放隊列里的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設兩個指針和分別指示隊頭和隊尾元素在隊列中的位置。它們的初始值在隊列初始化時均應置為０。入隊時將新元素插入所指的位置，然后尾指針加１。出隊時，刪去所指的元素，然后頭指針加１并返回被刪元素。由此可見，當頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素，而尾指針始終指向隊尾元素的下一位置。０１２３0123

FrontrearabcFrontrear

(a)隊列初始為空（b）A,B,C入隊０１２３０１２３bc

frontrearfrontrear（c)a出隊(d)b,c出隊，隊為空

#defineMAXQSIZE100typedefstruct{ElemTypedata[MAXQSIZE];intfront;/*隊頭位置*/intrear;/*隊尾位置*/}SqQueue;順序隊列的操作演示隊列的順序存儲結構定義：SqQueueQQ->front存放即將要被刪除的元素的下標。Q->rear存放即將要被插入的元素（目前不在隊列中）的下標。Q->data[Q->front]和Q->data[Q->rear]和棧類似，隊列中亦有上溢和下溢現象。此外，順序隊列中還存在“假上溢”現象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠無法重新利用。因此，盡管隊列中實際的元素個數遠遠小于向量空間的規模，但也可能由于尾指針巳超出向量空間的上界而不能做入隊操作。該現象稱為假上溢。為充分利用向量空間，克服上述假上溢現象，可以將向量空間想象為一個首尾相接的圓環，并稱這種向量為循環向量，存儲在其中的隊列稱為循環隊列（CircularQueue)。在循環隊列中進行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當頭尾指針指向向量上界（QueueSize-1）時，其加1操作的結果是指向向量的下界0。

顯然，因為循環隊列元素的空間可以被利用，除非向量空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應用外，真正實用的順序隊列是循環隊列（環形隊列）。

入隊和出隊如何表示？由于入隊時尾指針向前追趕頭指針，出隊時頭指針向前追趕尾指針，故隊空和隊滿時頭尾指針均相等。因此，我們無法通過Q->f

=Q->r來判斷隊列“空”還是“滿”。

front540312J6J7J8J4J5rear隊空：Q.front=Q.rear隊滿：Q.front=(Q.rear+1)%maxSize入隊:Q.rear=(Q.rear+1)%maxSize出隊:Q.front=(front+1)%maxSize;求隊長:(Q.rear-Q.front+maxSize)%maxSize循環隊列【例】設循環隊列的容量為40（序號從0到39），現經過一系列的入隊和出隊運算后，有①front=11，rear=19;②front=19，rear=11；問在這兩種情況下，循環隊列中各有元素多少個？答：用隊列長度計算公式：

(Q.rear-Q.front+maxSize)%maxSize①L=（40＋19－11）%40=8②L=（40＋11－19）%40=32循環隊列的操作演示2)出隊列實現程序StatusDeQueue(SqQueue&Q,ElemType&e){if(Q.rear==Q.front)return(ERROR);e=Q.data[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return(OK);}2.出隊列1)出隊列算法（1）檢查隊列是否為空，若隊空，則進行下溢錯誤處理；（2）取隊首元素的值。（3）將隊首指針后移一個位置（即加1）；(4)取隊頭元素ElemTypeGetHead(SqQueueQ){if(Q.front==Q.rear)return(ERROR);return(Q.data[Q.front]);}(3)隊列初始化Q.front=Q.rear=0;(5)判隊列空否intQueueEmpty(SqQueueQ){if(Q.front==Q.rear)reurn(1);elsereturn(0);}3.4.3鏈隊列隊列的鏈式存儲結構簡稱為鏈隊列，它是限制僅在表頭刪除和表尾插入的單鏈表。顯然僅有單鏈表的頭指針不便于在表尾做插入操作，為此再增加一個尾指針，指向鏈表的最后一個結點。于是，一個鏈隊列由頭指針和尾指針唯一確定。和順序隊列類似，我們也是將這兩個指針封裝在一起，將鏈隊列的類型LinkQueue定義為一個結構類型：typedefstructqueuenode{ElemTypedata;structqueuenode*next;}QueueNode;typedefstruct{QueueNode*front;QueueNode*rear;}LinkQueue;LinkQueueQ;Q->front隊列的頭指針Q->rear隊列的尾指針運算的實現voidInitQueue(LinkQueue&Q){Q.front=Q.rear=(queuenode*)malloc(sizeof(queuenode));Q.front->next=Q.rear->next=NULL;}q.fq.rnull*q1、創建一個空隊列：2、隊列的判空:intQueueEmpty(LinkQueueQ){return(Q.front->next==NULL&&Q.rear->next==NULL);}4、出隊操作：StatusDeQueue(LinkQueue&Q,ElenType&e){QueueNode*p;if(QueueEmpty(Q))returnERROR;p=Q.front->next;e=p–>data;Q.front->next=p–>next;null*qq.rearxnullq.frontp存儲池

if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}隊列的應用

隊列在日常生活中和計算機程序設計中，有著非常重要的作用，在此，僅舉出兩個方面例子來說明它，其它應用在后面章節中將會遇到。第一個例子就是CPU資源的競爭問題。在具有多個終端的計算機系統中，有多個用戶需要使用CPU各自運行自己的程序，它們分別通過各自終端向操作系統提出使用CPU的請求，操作系統按照每個請求在時間上的先后順序，將其排成一個隊列，每次把CPU分配給隊頭用戶使用，當相應的程序運行結束，則令其出隊，再把CPU分配給新的隊頭用戶，直到所有用戶任務處理完畢。1、稱正讀和反讀都相同的字符序列為“回文”，例如“abba”，寫一個算法，判別讀入以“@”為結束符的字符序列是否為“回文”。2、假設以帶頭結點的循環鏈表表是隊列，并且只設一個指針指向隊尾結點，但不設頭指針，設計相應的入隊和出隊算法。intTest()//判別輸入的字符串是否回文序列,是返回1,否返回0

{StackS;QueueQ;chara,b;

InitStack(S);InitQueue(