數(shù)據(jù)結(jié)構(gòu)隊列演示文稿

數(shù)據(jù)結(jié)構(gòu)隊列演示文稿目前一頁\總數(shù)四十八頁\編于十四點數(shù)據(jù)結(jié)構(gòu)隊列目前二頁\總數(shù)四十八頁\編于十四點3.4.1隊列的概念一、什么是隊列隊列是限定僅能在表頭進行刪除、表尾進行插入的線性表。（a1,a2,...,ai-1,ai,ai+1,…,an）插入刪除目前三頁\總數(shù)四十八頁\編于十四點4）元素按a1,a2,a3,...,an

順序入隊，第一個入隊的元素為a1，最后一個入隊的元素是an，第一個出隊的元素為a1；

說明：1）表尾稱作隊尾，表頭稱為隊頭；2）a1為隊頭元素，an為隊尾元素；3）在表尾插入元素操作，稱為入隊操作；在表頭刪除元素的操作，稱為出隊操作；5）隊列具有先進先出的特點，又稱為先進先出表（FIFO表）。入隊列

a1a2a3an隊頭隊尾出隊列目前四頁\總數(shù)四十八頁\編于十四點自測題1一個隊列的入列序列是1,2,3,4，則隊列的輸出序列是（）。A.4,3,2,1B.1,2,3,4C.1,4,3,2D.3,2,4,1目前五頁\總數(shù)四十八頁\編于十四點二、隊列的抽象數(shù)據(jù)類型的定義InitQueue(&Q)結(jié)果:構(gòu)造一個空隊列Q。數(shù)據(jù)對象:D={ai|ai∈ElemSet，i=1,2,…,n}數(shù)據(jù)關(guān)系:R1={<ai-1,ai>}；約定a1為隊頭元素，an為隊尾元素?；静僮?ADTQueue{}ADTQueueDestroyQueue(&Q)結(jié)果:銷毀隊列Q。條件:隊列Q已存在。目前六頁\總數(shù)四十八頁\編于十四點

功能：若隊列不空，則刪除Q的隊頭元素，用e返回其值，并返回OK；否則，返回ERROR。隊列的基本操作：1）初始化操作InitQueue(&Q)功能：構(gòu)造一個空隊列Q；2）銷毀操作DestroyQueue(&Q)功能：銷毀已存在隊列Q；3）置空操作ClearQueue(&Q)功能：將隊列Q置為空隊列；4）判空操作QueueEmpty(Q)功能：若隊列Q為空，則返回True；否則，返回False；5）取隊頭元素操作GetHead(Q,&e)功能：取隊頭元素，并用e返回；6）入隊操作EnQueue(&Q,e)功能：將元素e插入Q的隊尾；7）出隊操作DeQueue(&Q,&e)目前七頁\總數(shù)四十八頁\編于十四點在隊列的順序存儲結(jié)構(gòu)中，用一組連續(xù)存儲單元依次存儲從隊頭到隊尾的數(shù)據(jù)元素.此外，還需附加兩個變量：3.4.3隊列的順序存儲和實現(xiàn)一、隊列的順序存儲結(jié)構(gòu)隊頭指針front：指示隊頭元素的位置；隊尾指針rear：指示隊尾元素的位置?？贞犃蠶.rearQ.front012345Q.rearQ.frontJ1J2J3J1,J2和J3相繼入隊Q.rearQ.frontJ3J1和J2相繼出隊J4、J5和J6相繼入隊之后,J3和J4出隊Q.rearQ.frontJ5J6問題：如何解決“假上溢”現(xiàn)象?目前八頁\總數(shù)四十八頁\編于十四點將順序隊列設(shè)想為首尾相連的環(huán)狀空間。當(dāng)Q.rear值超出隊列空間的最大位置時，令Q.rear=0，使隊列空間能“循環(huán)”使用。J6J4J5Q.rearQ.front312405543210Q.rearQ.frontJ6J5J41、循環(huán)隊列循環(huán)使用空間的隊列。目前九頁\總數(shù)四十八頁\編于十四點循環(huán)隊列操作示意圖目前十頁\總數(shù)四十八頁\編于十四點2）在（a)狀態(tài)下，J6、J7、J8依次入隊，隊列如圖（c），這時也有Q.front=Q.rear。540312J5Q.frontQ.rearJ4J3(a)Q.rear540312Q.frontJ5J6J7J8J3J4(c)隊滿2、隊空、隊滿的判別1）在（a）狀態(tài)下，J3、J4、J5依次出隊，隊列狀態(tài)如圖（b），這時有Q.front=Q.rear;僅憑Q.front=Q.rear是否成立，無法判斷隊列是空還是滿。Q.frontQ.rear540312J3J4J5(b)隊空目前十一頁\總數(shù)四十八頁\編于十四點2）少用一個存儲單元，即當(dāng)隊列達到圖(d)所示狀態(tài)時，就認為隊列已滿，這時的條件是Q.front=(Q.rear+1)%6。如何判斷循環(huán)隊列隊空、隊滿？

？Q.rear540312Q.frontJ5J6J7J3J4（d）兩種方法：1）另設(shè)一個標(biāo)志位以區(qū)分隊空、隊滿。目前十二頁\總數(shù)四十八頁\編于十四點自測題2循環(huán)隊列的優(yōu)點是什么，如何判斷“空”和“滿”。【解答】循環(huán)隊列解決了常規(guī)用0--m-1的數(shù)組表示隊列時出現(xiàn)的“假溢出”（即隊列未滿但不能入隊）。在循環(huán)隊列中，我們?nèi)杂藐狀^指針等于隊尾指針表示隊空，而用犧牲一個單元的辦法表示隊滿：即當(dāng)隊尾指針加1（取模）等于隊頭指針時，表示隊列滿。也有使用全部單元，通過設(shè)標(biāo)記來解決“空”和“滿”的。目前十三頁\總數(shù)四十八頁\編于十四點3、循環(huán)隊列的類型定義#defineMAXQSIZE100//最大隊列長度

typedefstruct{

QElemType*base;//初始化時動態(tài)分配存儲空間的基址

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

intrear;//隊尾指針，指向隊尾元素的下一個位置（隊列不空）}SqQueue;只是稱為指針，實現(xiàn)時不一定用指針變量目前十四頁\總數(shù)四十八頁\編于十四點設(shè)Q為SqQueue類型的變量，用于存儲隊列。設(shè)為隊列Q分配空間大小為MAXQSIZE=6。初始建隊時，令Q.front=Q.rear=0。Q.frontQ.rear540312Q.base目前十五頁\總數(shù)四十八頁\編于十四點二、循環(huán)隊列的基本操作算法1、初始化操作InitQueue_Sq(SqQueue&Q)參數(shù)：Q是存放隊列的結(jié)構(gòu)變量；功能：建一個空隊列Q。Q.frontQ.rear540312Q.base#defineMAXQSIZE100//最大隊列長度

typedefstruct{

QElemType*base;//基址

intfront;//指向隊頭元素

intrear;//指向隊尾元素的下一個位置}SqQueue;目前十六頁\總數(shù)四十八頁\編于十四點StatusInitQueue_Sq(SqQueue&Q){

//構(gòu)造一個空隊列Q

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

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

Q.front=Q.rear=0;

returnOK;

}Q.frontQ.rear540312Q.base#defineMAXQSIZE100//最大隊列長度

typedefstruct{

QElemType*base;//基址

intfront;//指向隊頭元素

intrear;//指向隊尾元素的下一個位置}SqQueue;目前十七頁\總數(shù)四十八頁\編于十四點intQueueLength_Sq(SqQueueQ){

return（Q.rear–Q.front+MAXQSIZE）%MAXQSIZE;

}2、計算隊列長度操作QueueLength_Sq(SqQueueQ)參數(shù)：Q是存放隊列的結(jié)構(gòu)變量；功能：計算隊列的長度。Q.rear540312Q.frontJ5J6J7J3J4Q.rear目前十八頁\總數(shù)四十八頁\編于十四點3）修改隊尾指針，使隊尾指針指向隊尾元素的下一個位置。Q.frontQ.rear540312J1J3J2元素e入隊前Q.frontQ.rear540312J1J3J2e元素e入隊后3、入隊操作EnQueue_Sq(SqQueue&Q,QElemTypee)功能：將元素e插入隊尾。主要步驟：1）Q是否已滿，若滿，返回ERROR；否則轉(zhuǎn)2）；2）將元素e寫入隊尾；目前十九頁\總數(shù)四十八頁\編于十四點StatusEnQueue_Sq(SqQueue&Q,QElemTypee){

}if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;//隊列滿Q.base[Q.rear]=e;//將元素e插入隊尾Q.rear=(Q.rear+1)%MAXQSIZE;//修改隊尾指針returnOK;目前二十頁\總數(shù)四十八頁\編于十四點自測題3循環(huán)隊列存儲在數(shù)組A[0..m]中，則入隊時的操作為（）。A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)modmD.rear=(rear+1)mod(m+1)目前二十一頁\總數(shù)四十八頁\編于十四點3）修改隊頭指針，刪除隊頭元素。Q.frontQ.rear540312J1J3J2出隊操作前Q.frontQ.rear540312J1J3J2出隊操作后eJ14、出隊操作DeQueue_Sq(SqQueue&Q,QElemType&e)功能：刪除隊頭元素，用e返回其值。主要步驟：1）Q是否為空，若空，返回ERROR；否則，轉(zhuǎn)2）；2）將隊頭元素賦值給e；目前二十二頁\總數(shù)四十八頁\編于十四點StatusDeQueue_Sq(SqQueue&Q,QElemType&e){

}if(Q.rear==Q.front)returnERROR;//隊列空e=Q.base[Q.front];//將隊頭元素賦給eQ.front=(Q.front+1)%MAXQSIZE;//修改隊頭指針returnOK;目前二十三頁\總數(shù)四十八頁\編于十四點一、什么是鏈隊列用鏈表存儲的隊列。為便于操作，一個鏈隊列需要分別指示隊頭和隊尾的兩個指針。

J1∧Q.frontQ.rearJ2∧空鏈隊列Q.frontQ.rear∧頭結(jié)點3.4.2鏈隊列——隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)和實現(xiàn)鏈隊列的表頭結(jié)點Q.front==Q.rear目前二十四頁\總數(shù)四十八頁\編于十四點二、鏈隊列的類型定義typedefstructQNode{//鏈隊列結(jié)點的類型定義

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{

//鏈隊列表頭結(jié)點的類型定義

QueuePtrfront;//隊頭指針，指向鏈表的頭結(jié)點

QueuePtr

rear;//隊尾指針，指向隊尾結(jié)點}LinkQueue;//將頭尾指針封裝在一起的鏈隊J1∧Q.frontQ.rearJ2∧目前二十五頁\總數(shù)四十八頁\編于十四點三、鏈隊列基本操作算法1、初始化操作InitQueue_L(LinkQueue&Q):創(chuàng)建空的鏈隊列。

Q.frontQ.reartypedefstructQNode{//鏈隊列結(jié)點的類型定義

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//鏈隊列表頭結(jié)點的類型定義

QueuePtrfront;//隊頭指針，指向鏈表的頭結(jié)點

QueuePtr

rear;//隊尾指針，指向隊尾結(jié)點}LinkQueue;∧目前二十六頁\總數(shù)四十八頁\編于十四點if(!Q.front)exit(OVERFLOW)；Q.front

->next=NULL；returnOK；StatusInitQueue_L(LinkQueue&Q){}Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode))；//申請頭結(jié)點Q.frontQ.reartypedefstructQNode{//鏈隊列結(jié)點的類型定義

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//鏈隊列表頭結(jié)點的類型定義

QueuePtrfront;//隊頭指針，指向鏈表的頭結(jié)點

QueuePtr

rear;//隊尾指針，指向隊尾結(jié)點}LinkQueue;∧目前二十七頁\總數(shù)四十八頁\編于十四點Q.frontQ.rear

銷毀后J1∧Q.frontQ.rearJ2∧

銷毀前2、銷毀操作DestroyQueue_L(LinkQueue&Q)：回收空間。

typedefstructQNode{//鏈隊列結(jié)點的類型定義

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//鏈隊列表頭結(jié)點的類型定義

QueuePtrfront;//隊頭指針，指向鏈表的頭結(jié)點

QueuePtr

rear;//隊尾指針，指向隊尾結(jié)點}LinkQueue;∧∧目前二十八頁\總數(shù)四十八頁\編于十四點StatusDestroyQueue_L(LinkQueue&Q){

}while(Q.front){

}//while

Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;returnOK;Q.frontQ.rear

銷毀后J1∧Q.frontQ.rearJ2∧

銷毀前∧∧目前二十九頁\總數(shù)四十八頁\編于十四點3、入隊操作EnQueue_L(LinkQueue&Q,QElemTypee)Q.front∧J1∧Q.reare∧J1typedefstructQNode{//鏈隊列結(jié)點的類型定義

QElemTypedata;

structQNode*next;}QNode,*QueuePtr;typedefstruct{//鏈隊列表頭結(jié)點的類型定義

QueuePtrfront;//隊頭指針，指向鏈表的頭結(jié)點

QueuePtr

rear;//隊尾指針，指向隊尾結(jié)點}LinkQueue;目前三十頁\總數(shù)四十八頁\編于十四點p=(QueuePtr)malloc(sizeof(QNode))；if(!p)exit(OVERFLOW)；p->data=e；p->next=NULL；//申請新結(jié)點Q.rear->next=p；returnOK；StatusEnQueue_L(LinkQueue&Q，QElemTypee){}Q.rear

=p；//插入在隊尾Q.front∧J1∧Q.reare∧J1目前三十一頁\總數(shù)四十八頁\編于十四點zhoujin0xin

SQ.frontQ.rear

pe=p->data=zhou

pe=p->data=jin

pe=p->data=xinQ.rear04、離開隊列DeQueue_L(LinkQueue&Q，QElemType&e)

注意！目前三十二頁\總數(shù)四十八頁\編于十四點p=Q.front->next；e=p->data；//取第一個結(jié)點free(p)；returnOK；StatusDeQueue_L(LinkQueue&Q，QElemType&e){}Q.front->next=p->next；//刪除第一個結(jié)點if(Q.front==Q.rear)returnERROR；if(Q.rear==p)Q.rear=Q.front；//若需要刪除的隊頭結(jié)點就是尾結(jié)點J1∧Q.frontQ.rearJ2∧目前三十三頁\總數(shù)四十八頁\編于十四點自測題4用鏈接方式存儲的隊列，在進行刪除運算時（）。A.僅修改頭指針B.僅修改尾指針C.頭、尾指針都要修改D.頭、尾指針可能都要修改目前三十四頁\總數(shù)四十八頁\編于十四點算法設(shè)計題1假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點，不設(shè)頭指針，試設(shè)計相應(yīng)的入隊列和出隊列的算法?！璗ail隊頭隊尾目前三十五頁\總數(shù)四十八頁\編于十四點typedefstructLqueue{ElemTypedata;structLqueue*next;}Lqueue,*Queueptr;

voidQueueIn(Queueptrrear,ElemTypex){//入隊列

s=(Queueptr)malloc(sizeof(LQueue));s->data=x;s->next=rear->next;//元素插入隊尾

rear->next=s;rear=s;//求得新的隊尾}

…Tail隊頭隊尾目前三十六頁\總數(shù)四十八頁\編于十四點typedefstructLqueue{ElemTypedata;structLqueue*next;}Lqueue,*Queueptr;

…Tail隊頭隊尾ElemTypeQueueOut(Queueptrrear){//出隊列if(rear->next->next==rear)printf("隊列為空");else{p=rear->next;q=p->next;p->next=q->next;x=q->data;if(q==rear)rear=p;free(q);//刪除隊頭元素

return(x);}//else}

目前三十七頁\總數(shù)四十八頁\編于十四點算法設(shè)計題2要求完全利用循環(huán)隊列中的元素空間，設(shè)置一個標(biāo)志域tag，并以tag的值是0或１來區(qū)分尾指針和頭指針相同時的隊列狀態(tài)是“空”還是“不空”。請編寫與此結(jié)構(gòu)相對應(yīng)的入隊和出隊的算法。類型定義：typedefstruct{ElemTypedata[m];intrear,front;//隊尾和隊頭指針

inttag;//標(biāo)記,0為空,1為非空

}CycQueue;

目前三十八頁\總數(shù)四十八頁\編于十四點只設(shè)標(biāo)志的循環(huán)隊列的入隊voidQueueIn(CycQueuecq,ElemTypex){if(cq.tag==1&&cq.front==cq.rear){printf(“隊滿\n”);exit(0);}else{cq.rear=(cq.rear+1)%m;cq.data[cq.rear]=x;if(cq.tag==0)cq.tag=1;//由空變不空標(biāo)記

}//else}目前三十九頁\總數(shù)四十八頁\編于十四點只設(shè)標(biāo)志的循環(huán)隊列的出隊voidQueueOut(CycQueuecq);{if(cq.tag==0){printf(“隊空\n”);exit(0);}else{cq.front=(cq.front+1)%m;if(cq.front==cq.rear)cq.tag=0;//隊列由不空變空

}//else}目前四十頁\總數(shù)四十八頁\編于十四點算法設(shè)計3用棧模擬隊列請利用兩個棧S1和S2來模擬一個隊列。已知棧的三個運算定義如下：PUSH(ST,x):元素x入ST棧；POP(ST,x)：ST棧頂元素出棧，賦給變量x；Sempty(ST)：判ST棧是否為空。那么如何利用棧的運算來實現(xiàn)該隊列的三個運算：

enqueue:插入一個元素入隊列；dequeue:刪除一個元素出隊列；queue_empty：判隊列為空?！旧虾＝煌ù髮W(xué)1999二(12分)】【廈門大學(xué)2005六(15分)】目前四十一頁\總數(shù)四十八頁\編于十四點棧模擬隊列——入隊inttop1;∥top1是棧s1的棧頂指針，是全局變量intenqueue(stacks1,ElemTypex)∥用入棧模擬入隊{if(top1==n&&!Sempty(s2)){printf(“棧滿”);return(0);}∥s1滿s2非空,這時s1不能再入棧

if(top1==n&&Sempty(s2))∥s2空，將s1退棧,再壓棧到s2{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}push(s1,x);return(1);∥x入棧，實現(xiàn)了隊列元素的入隊}目前四十二頁\總數(shù)四十八頁\編于十四點棧模擬隊列——出隊voiddequeue(stacks2,s1)∥s2是輸出棧，將s2棧頂元素退棧，實現(xiàn)隊列元素的出隊{if(!Sempty(s2))∥棧s2不空，則直接出隊

{POP(s2,x);printf(“出隊元素為”,x);}elseif(Sempty(s1))∥處理s2空棧

{printf(“隊列空”);exit(0);}∥若輸入棧也空，則隊空

else∥先將棧s1倒入s2中，再出隊

{while(!Sempty(s1)){POP(s1,x);PUSH(s2,x);}POP(s2,x);∥s2退棧相當(dāng)隊列出隊

printf(“出隊元素”，x);}}∥結(jié)束算法dequue目前四十三頁\總數(shù)