隊列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊頭(front)，允許插入的一端稱為隊尾(rear)。例如：排隊購物。操作系統(tǒng)中的作業(yè)排隊。先進(jìn)入隊列的成員總是先離開隊列。因此隊列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡稱FIFO表。當(dāng)隊列中沒有元素時稱為空隊列。在空隊列中依次加入元素a1,a2,…an之后，a1是隊頭元素，an是隊尾元素。顯然退出隊列的次序也只能是a1,a2,…an，也就是說隊列的修改是依先進(jìn)先出的原則進(jìn)行的。3.4隊列的類型定義ADTQueue{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關(guān)系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}約定其中a1端為隊列頭，an端為隊列尾基本操作：隊列的抽象數(shù)據(jù)類型定義}

ADTQueue隊列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTraverse(Q,visit())InitQueue(&Q)

操作結(jié)果：構(gòu)造一個空隊列Q。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：隊列Q被銷毀，

不再存在。

QueueEmpty(Q)

初始條件：隊列Q已存在。

操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。

QueueLength(Q)

初始條件：隊列Q已存在。

操作結(jié)果：返回Q的元素個數(shù)，即隊列的長度。

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：用e返回Q的隊頭元素。a1a2an……

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結(jié)果：將Q清為空隊列。

EnQueue(&Q,e)

初始條件：隊列Q已存在。

操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane……

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an……

3.5隊列類型的實(shí)現(xiàn)鏈隊列——鏈?zhǔn)接诚笱h(huán)隊列——順序映象

typedefstructQNode{//結(jié)點(diǎn)類型

QElemTypedata;

structQNode*next;

}QNode,*QueuePtr;鏈隊列——鏈?zhǔn)接诚髏ypedefstruct{//鏈隊列類型QueuePtrfront;//隊頭指針QueuePtrrear;//隊尾指針}LinkQueue;a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊列非空隊列

StatusInitQueue(LinkQueue&Q){//構(gòu)造一個空隊列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));

if(!Q.front)exit(OVERFLOW);//存儲分配失敗

Q.front->next=NULL;

returnOK;}

StatusDestroyQueue(LinkQueue&Q){//銷毀隊列Qwhile(Q.front){Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;

}

returnOK;}

StatusEnQueue(LinkQueue&Q,QElemTypee){//插入元素e為Q的新的隊尾元素(尾插法）

p=(QueuePtr)malloc(sizeof(QNode));

if(!p)exit(OVERFLOW);//存儲分配失敗p->data=e;p->next=NULL;

Q.rear->next=p;Q.rear=p;

returnOK;}

StatusDeQueue(LinkQueue&Q,QElemType&e){

//若隊列不空，則刪除Q的隊頭元素，（頭刪法）//用e返回其值，并返回OK；否則返回ERROR

if(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;

Q.front->next=p->next;

if(Q.rear==p)Q.rear=Q.front;//第一個結(jié)點(diǎn)也是最后一個結(jié)點(diǎn)

free(p);

returnOK;}非循環(huán)隊列（順序隊列）

隊列的順序存儲結(jié)構(gòu)稱為順序隊列，順序隊列實(shí)際上是運(yùn)算受限的順序表，和順序表一樣，順序隊列也是必須用一個地址連續(xù)的空間來存放當(dāng)前隊列中的元素。由于隊列的隊頭和隊尾的位置是變化的，因而要設(shè)兩個指針和分別指示隊頭和隊尾元素在隊列中的位置，它們的初始值在隊列初始化時均應(yīng)置為０。入隊時先將新元素插入所指的位置，然后加１。出隊時，先刪去所指的元素，然后加１并返回被刪元素。由此可見，當(dāng)頭尾指針相等時隊列為空。在非空隊列里，頭指針始終指向隊頭元素（實(shí)位以在），而尾指針始終指向隊尾元素的下一位置（虛位以待）。０１２３0123

frontrearabcfrontrear

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

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

隊空：Q.front=Q.rear隊滿：Q.rear-Q.front=maxsize（求隊長）

入隊：新元素按

rear

指示位置加入，再將隊尾指針加一，即Q.rear=Q.rear+1

出隊：將front指示的元素取出，再將隊頭指針加一，即Q.front=Q.front+1非循環(huán)隊列（順序隊列）存在“假上溢”的現(xiàn)象

和棧類似，隊列中亦有上溢和下溢現(xiàn)象。此外，順序隊列中還存在“假上溢”現(xiàn)象。因為在入隊和出隊的操作中，頭尾指針只增加不減小，致使被刪除元素的空間永遠(yuǎn)無法重新利用。因此，盡管隊列中實(shí)際的元素個數(shù)遠(yuǎn)遠(yuǎn)小于數(shù)組的規(guī)模，但也可能由于尾指針?biāo)瘸鰯?shù)組的上界而不能做入隊操作。該現(xiàn)象稱為假上溢。

為充分利用數(shù)組，克服上述假上溢現(xiàn)象，可以將數(shù)組想象為一個首尾相接的圓環(huán)，并稱這種數(shù)組為循環(huán)數(shù)組，存儲在其中的隊列稱為循環(huán)隊列（CircularQueue)。在循環(huán)隊列中進(jìn)行出隊、入隊操作時，頭尾指針仍要加1，朝前移動。只不過當(dāng)頭尾指針指向數(shù)組上界（QueueSize-1）時，其加1操作的結(jié)果是指向數(shù)組的下界0。

顯然，因為循環(huán)隊列元素的空間可以被利用，除非數(shù)組空間真的被隊列元素全部占用，否則不會上溢。因此，除一些簡單的應(yīng)用外，真正實(shí)用的順序隊列是循環(huán)隊列。

012345Q.rearQ.frontJ4J5J6012345Q.rearQ.frontJ3J8J7J3J4J5012345Q.rearQ.front初始狀態(tài)J3,J4,J5出隊J6,J7,J8入隊如何判斷隊空隊滿現(xiàn)象？隊空：Q.front==Q.rear隊滿：Q.front==Q.rear解決方案：1.另外設(shè)一個標(biāo)志以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：Q.front==Q.rear

隊滿：(Q.rear+1)%M==Q.front即隊列頭指針在隊列尾指針的下一位置（指環(huán)狀的下一位置）上012345Q.rearQ.frontJ4J5J6012345Q.rearQ.frontJ3J7J3J4J5012345Q.rearQ.front當(dāng)前狀態(tài)J3,J4,J5出隊J6,J7入隊隊空：Q.front==Q.rear隊滿：(Q.rear+1)%M==Q.front解決方案：少用一個元素空間：012345Q.rearQ.front初始狀態(tài)J0,J1,J2,J3,J4,J5入隊J0,J1,J2出隊隊空：Q.front=Q.rear隊滿：Q.front=(Q.rear+1)%MAXQSIZE入隊:1)隊列不滿2)Q.rear=(Q.rear+1)%MAXQSIZE出隊:1)隊列不空2)Q.front=(Q.front+1)%MAXQSIZE求隊長:(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE循環(huán)隊列#defineMAXQSIZE100//最大隊列長度

typedefstruct{QElemType*base;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向//隊列尾元素的下一個位置

}SqQueue;循環(huán)隊列——順序映象

StatusInitQueue(SqQueue&Q){//構(gòu)造一個空隊列QQ.base=(QElemType*)malloc

(MAXQSIZE*sizeof(QElemType));

if(!Q.base)exit(OVERFLOW);//存儲分配失敗

Q.front=Q.rear=0;

returnOK;

}StatusEnQueue(SqQueue&Q,ElemTypee){//插入元素e為Q的新的隊尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;//隊列滿

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;

returnOK;}

StatusDeQueue(SqQueue&Q,ElemType&e){

//若隊列不空，則刪除Q的隊頭元素，//用e返回其值，并返回OK;否則返回ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];

Q.front=(Q.front+1)%MAXQSIZE;

returnOK;}第1行11第2行121第3行1331第4行1464