隊(duì)列的定義表示實(shí)現(xiàn)

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

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

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

端為隊(duì)列頭，an端為隊(duì)列尾?；静僮鳎?/p>

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

typedefstruct{QueuePtrfront;//隊(duì)頭指針

QueuePtrrear;//隊(duì)尾指針

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

typedefstructQNode

{QElemType

data;//元素

structQNode

*next;

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

Qnode,*QueuePtr;關(guān)于整個(gè)鏈隊(duì)的總體描述鏈隊(duì)中任一結(jié)點(diǎn)的結(jié)構(gòu)三、隊(duì)列的表示和實(shí)現(xiàn)1.單鏈隊(duì)列//-----隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)-----6第6頁，共30頁，2023年，2月20日，星期四a1∧an…Q.frontQ.rearQ.frontQ.rear∧空隊(duì)列為了操作方便，添加一個(gè)頭結(jié)點(diǎn)，令頭指針指向頭結(jié)點(diǎn)。Q.front==Q.rear7第7頁，共30頁，2023年，2月20日，星期四

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

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

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

Q.front->next=NULL;

returnOK;}//-----基本操作的算法描述-----建隊(duì)操作——構(gòu)造空隊(duì)列Q8第8頁，共30頁，2023年，2月20日，星期四Q(隊(duì)尾)(隊(duì)首)fronta1a2a3^rearp鏈隊(duì)會(huì)滿嗎？一般不會(huì)，因?yàn)閯h除時(shí)有free動(dòng)作。除非內(nèi)存不足！入隊(duì)（尾部插入）：rear->next=S;rear=S;出隊(duì)（頭部刪除）：p=front->next;

front->next=p->next;free(p);Se^鏈隊(duì)列的入隊(duì)和出隊(duì)操作9第9頁，共30頁，2023年，2月20日，星期四

StatusEnQueue(LinkQueue&Q,QElemTypee){

//插入元素e為Q的新的隊(duì)尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲(chǔ)分配失敗

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}10第10頁，共30頁，2023年，2月20日，星期四

StatusDeQueue(LinkQueue&Q,QElemType&e){

//若隊(duì)列不空，則刪除Q的隊(duì)頭元素，

//用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第11頁，共30頁，2023年，2月20日，星期四隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)如下圖所示：附設(shè)兩個(gè)指針front和rear分別指示隊(duì)列頭元素的位置和隊(duì)列尾元素的下一個(gè)位置約定：初始化建空隊(duì)列時(shí)，令front=rear=0；2.順序隊(duì)列12第12頁，共30頁，2023年，2月20日，星期四（2）空隊(duì)列的特征？約定：front=rear問題：（1）怎樣實(shí)現(xiàn)入隊(duì)和出隊(duì)操作？核心語句如下：入隊(duì)(尾部插入)：Q[rear]=e;rear++;

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

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

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

實(shí)際中常選用方案2（人為浪費(fèi)一個(gè)單元）16第16頁，共30頁，2023年，2月20日，星期四建隊(duì)核心語句：Q.base=(QElemType*)malloc(sizeof(QElemType）*MAXQSIZE);

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

typedefstruct{QElemType*base;//隊(duì)列的基址

intfront;//隊(duì)頭指針

intrear;//隊(duì)尾指針

}SqQueue//-----循環(huán)隊(duì)列——隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)-----17第17頁，共30頁，2023年，2月20日，星期四隊(duì)空條件:front=rear(初始化時(shí)：front=rear)隊(duì)滿條件：front=(rear+1)%N(N=MAXQSIZE)隊(duì)列長度：L=（N＋rear－front）%N

J2J3 J1J4

J5frontrear問3：在具有N個(gè)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有多少個(gè)元素？N-1個(gè)6問1：左圖中隊(duì)列MAXQSIZEN=？問2：左圖中隊(duì)列長度L=？518第18頁，共30頁，2023年，2月20日，星期四例1.一循環(huán)隊(duì)列如下圖所示，若先刪除4個(gè)元素，接著再插入4個(gè)元素，請(qǐng)問隊(duì)頭和隊(duì)尾指針分別指向哪個(gè)位置?J2J3 J1J4

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

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

front=rear=0（也可為任意單元，如1，2，…）21第21頁，共30頁，2023年，2月20日，星期四建隊(duì)的完整算法：StatusInitQueue(SqQueue&Q){

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

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

if(!Q.base)

exit(OVERFLOW);

Q.front=Q.rear=0;

//置空隊(duì)列

returnOK;}//InitQueue;22第22頁，共30頁，2023年，2月20日，星期四算法說明：向循環(huán)隊(duì)列的隊(duì)尾插入一個(gè)元素分析：(1)插入前應(yīng)當(dāng)先判斷隊(duì)列是否滿？

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

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;2）入隊(duì)操作隊(duì)列尺寸先存放元素，后移動(dòng)隊(duì)尾指針23第23頁，共30頁，2023年，2月20日，星期四StatusEnQueue(SqQueue&Q,QElemTypee){//向循環(huán)隊(duì)列q的隊(duì)尾加入一個(gè)元素e

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

front)returnERROR;

//隊(duì)滿則上溢

Q.

base[Q.

rear]=e;//新元素e入隊(duì)

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

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

（2）刪除動(dòng)作分析：

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

e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;隊(duì)列尺寸先取出元素，后移動(dòng)隊(duì)頭指針25第25頁，共30頁，2023年，2月20日，星期四StatusDeQueue(SqQueue&Q,QElemType&e){//若隊(duì)列不空，刪除循環(huán)隊(duì)列q的隊(duì)頭元素，//由e返回其值，并返回OKif(Q.

front==Q.

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

base[Q.front];

Q.

front=(Q.front+1)%MAXQSIZE;returnOK;}//DeQueue出隊(duì)操作完整算法26第26頁，共30頁，2023年，2月20日，星期四例3：編寫一個(gè)算法，利用棧和隊(duì)列的基本運(yùn)算將指定隊(duì)列中的內(nèi)容進(jìn)行逆轉(zhuǎn)。分析：假設(shè)為循環(huán)隊(duì)列。建立一個(gè)臨時(shí)棧temps，將指定隊(duì)列Q中的所有元素出隊(duì)并入棧到temp