隊列的定義表示實現(xiàn)第一頁，共三十頁，編輯于2023年，星期五3.2隊列只能在表的一端進行插入運算，在表的另一端進行刪除運算的線性表。1.定義一、概念：例如：隊列Q=(a1,a2,a3,…，an)在隊尾插入元素稱為入隊；在隊首刪除元素稱為出隊。隊頭元素隊尾元素允許插入的一端為隊尾，允許刪除的一端為隊頭。2第二頁，共三十頁，編輯于2023年，星期五與線性表相同，仍為一對一關(guān)系。順序隊或鏈隊，以循環(huán)順序隊更常見。只能在隊首和隊尾運算，且訪問結(jié)點時依照先進先出（FIFO）的原則。關(guān)鍵是掌握入隊和出隊操作，具體實現(xiàn)依順序隊或鏈隊的不同而不同。3.存儲結(jié)構(gòu)：4.運算規(guī)則：5.實現(xiàn)方式：2.邏輯結(jié)構(gòu)：3第三頁，共三十頁，編輯于2023年，星期五二、隊列的抽象數(shù)據(jù)類型定義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端為隊列尾。基本操作：

}ADTStack4第四頁，共三十頁，編輯于2023年，星期五（1）初始化隊列InitQueue(&Q)（2）入隊EnQueue(&Q,e)（3）出隊DeQueue(&Q,&e)（4）獲取隊頭元素內(nèi)容GetHead(Q,&e)（5）判斷隊列是否為空QueueEmpty(Q)基本操作:建隊列、判斷隊列是否為空、入隊、出隊、讀隊頭元素值，等等。5第五頁，共三十頁，編輯于2023年，星期五鏈隊列類型定義：

typedefstruct{QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針

}LinkQueue;結(jié)點類型定義：

typedefstructQNode

{QElemType

data;//元素

structQNode

*next;

//指向下一結(jié)點的指針}

Qnode,*QueuePtr;關(guān)于整個鏈隊的總體描述鏈隊中任一結(jié)點的結(jié)構(gòu)三、隊列的表示和實現(xiàn)1.單鏈隊列//-----隊列的鏈式存儲結(jié)構(gòu)-----6第六頁，共三十頁，編輯于2023年，星期五a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊列為了操作方便，添加一個頭結(jié)點，令頭指針指向頭結(jié)點。Q.front==Q.rear7第七頁，共三十頁，編輯于2023年，星期五

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

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

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

Q.front->next=NULL;

returnOK;}//-----基本操作的算法描述-----建隊操作——構(gòu)造空隊列Q8第八頁，共三十頁，編輯于2023年，星期五Q(隊尾)(隊首)fronta1a2a3^rearp鏈隊會滿嗎？一般不會，因為刪除時有free動作。除非內(nèi)存不足！入隊（尾部插入）：rear->next=S;rear=S;出隊（頭部刪除）：p=front->next;

front->next=p->next;free(p);Se^鏈隊列的入隊和出隊操作9第九頁，共三十頁，編輯于2023年，星期五

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;}10第十頁，共三十頁，編輯于2023年，星期五

StatusDeQueue(LinkQueue&Q,QElemType&e){

//若隊列不空，則刪除Q的隊頭元素，

//用e返回其值，并返回OK；否則返回ERRORif(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;

//一定要考慮

free(p);returnOK;}11第十一頁，共三十頁，編輯于2023年，星期五隊列的順序存儲結(jié)構(gòu)如下圖所示：附設(shè)兩個指針front和rear分別指示隊列頭元素的位置和隊列尾元素的下一個位置約定：初始化建空隊列時，令front=rear=0；2.順序隊列12第十二頁，共三十頁，編輯于2023年，星期五（2）空隊列的特征？約定：front=rear問題：（1）怎樣實現(xiàn)入隊和出隊操作？核心語句如下：入隊(尾部插入)：Q[rear]=e;rear++;

出隊(頭部刪除)：e=Q[front];front++;

（3）隊列會滿嗎？極易裝滿！因為數(shù)組通常有長度限制，而其前端空間無法釋放。有假溢出現(xiàn)象。如圖：13第十三頁，共三十頁，編輯于2023年，星期五解決假溢出的途徑———采用循環(huán)隊列在順序隊中，當尾指針已經(jīng)到了數(shù)組的上界，不能再有入隊操作，但實際上數(shù)組中還有空位置，這就叫“假溢出”。討論：什么叫“假溢出”？如何解決？將存儲隊列元素的一維數(shù)組首尾相接，形成一個環(huán)狀。14第十四頁，共三十頁，編輯于2023年，星期五a3a2a10123N-1rearfront循環(huán)隊列（臆造）順序隊列a3a2a1frontrear

0123..N-115第十五頁，共三十頁，編輯于2023年，星期五新問題：在循環(huán)隊列中，隊空時front=rear；隊滿時也會有front=rear；判決條件將出現(xiàn)二義性！解決方案有二：①使用一個計數(shù)器記錄隊列中元素個數(shù)（即隊列長度）；②人為浪費一個單元，約定：隊列頭指針在隊列尾指針的下一位置上作為隊列呈“滿”狀態(tài)的標志。則隊滿特征可改為front=(rear+1)%N（N為最大隊列長度）；

實際中常選用方案2（人為浪費一個單元）16第十六頁，共三十頁，編輯于2023年，星期五建隊核心語句：Q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);

//分配空間關(guān)于整個順序隊的總體描述#defineMAXQSIZE100//最大隊列長度

typedefstruct{QElemType*base;//隊列的基址

intfront;//隊頭指針

intrear;//隊尾指針

}SqQueue//-----循環(huán)隊列——隊列的順序存儲結(jié)構(gòu)-----17第十七頁，共三十頁，編輯于2023年，星期五隊空條件:front=rear(初始化時：front=rear)隊滿條件：front=(rear+1)%N(N=MAXQSIZE)隊列長度：L=（N＋rear－front）%N

J2J3 J1J4

J5frontrear問3：在具有N個單元的循環(huán)隊列中，隊滿時共有多少個元素？N-1個6問1：左圖中隊列MAXQSIZEN=？問2：左圖中隊列長度L=？518第十八頁，共三十頁，編輯于2023年，星期五例1.一循環(huán)隊列如下圖所示，若先刪除4個元素，接著再插入4個元素，請問隊頭和隊尾指針分別指向哪個位置?J2J3 J1J4

J5front=1rear=0解：由圖可知，隊頭和隊尾指針的初態(tài)分別為front=1和rear=0。刪除4個元素后front=5；再插入4個元素后，rear=(0+4)%6=4

front=5J6J5J7J8J9rear=4rear=0front=519第十九頁，共三十頁，編輯于2023年，星期五例2.Q[0…10]是一個循環(huán)隊列，初始狀態(tài)為front=rear=0,畫出做完下列操作后隊列的頭尾指針的狀態(tài)變化情況，若不能入隊，請指出其元素，并說明理由。d,e,b,g,h入隊d,e出隊i,j,k,l,m入隊b出隊n,o,p入隊20第二十頁，共三十頁，編輯于2023年，星期五討論：循環(huán)隊列的基本操作如何實現(xiàn)？以建隊、入隊和出隊三種基本操作為例1）初始化一個空隊列算法要求：生成一空隊列算法操作：為隊列分配基本容量空間設(shè)置隊列為空隊列，其特征即：

front=rear=0（也可為任意單元，如1，2，…）21第二十一頁，共三十頁，編輯于2023年，星期五建隊的完整算法：StatusInitQueue(SqQueue&Q){

//初始化空循環(huán)隊列Q

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType）);//分配空間

if(!Q.base)

exit(OVERFLOW);

Q.front=Q.rear=0;

//置空隊列

returnOK;}//InitQueue;22第二十二頁，共三十頁，編輯于2023年，星期五算法說明：向循環(huán)隊列的隊尾插入一個元素分析：(1)插入前應(yīng)當先判斷隊列是否滿？

if((Q.rear+1)%MAXQSIZE)==Q.front)returnERROR;(2）插入動作

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;2）入隊操作隊列尺寸先存放元素，后移動隊尾指針23第二十三頁，共三十頁，編輯于2023年，星期五StatusEnQueue(SqQueue&Q,QElemTypee){//向循環(huán)隊列q的隊尾加入一個元素e

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

front)returnERROR;

//隊滿則上溢

Q.

base[Q.

rear]=e;//新元素e入隊

Q.rear=(Q.rear+1)%MAXQSIZE;//指針后移returnOK;}//EnQueue;入隊操作完整算法24第二十四頁，共三十頁，編輯于2023年，星期五3）出隊操作算法說明：刪除隊頭元素，返回其值e分析：（1）在刪除前應(yīng)當判斷隊列是否空？

if(Q.front==Q.rear)returnERROR;

（2）刪除動作分析：

前面約定指針front指向隊首元素的位置，故：

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;隊列尺寸先取出元素，后移動隊頭指針25第二十五頁，共三十頁，編輯于2023年，星期五StatusDeQueue(SqQueue&Q,QElemType&e){//若隊列不空，刪除循環(huán)隊列q的隊頭元素，//由e返回其值，并返回OKif(Q.

front==Q.

rear)returnERROR;//隊列空e=Q.

base[Q.front];

Q.

front=(Q.front+1)%MAXQSIZE;returnOK;}//DeQueue出隊操作完整算法26第二十六頁，共三十頁，編輯于2023年，星期五例3：編寫一個算法，利用棧和隊列的基本運算將指定隊列中的內(nèi)容進行逆轉(zhuǎn)。分析：假設(shè)為循環(huán)隊列。建立一個臨時棧temps，將指定隊列Q中的所有元素出隊并入棧到tem