大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第三章：棧和隊(duì)列-第三節(jié)-隊(duì)列（一）

第三節(jié)隊(duì)列（一）一、隊(duì)列的定義及其運(yùn)算1、隊(duì)列的定義隊(duì)列（Oueue）是一種操作受限的線性表，它只允許在表的一端進(jìn)行元素插入，而在另一端進(jìn)行元素刪除。允許插入的一端稱為隊(duì)尾（rear），允許刪除的一端稱為隊(duì)頭（front）。新插入的結(jié)點(diǎn)只能添加到隊(duì)尾，被刪除的只能是排在隊(duì)頭的結(jié)點(diǎn)，因此，隊(duì)列又稱為先進(jìn)先出(FirstInFirstOut)的線性表，簡(jiǎn)稱為FIFO表。【真題選解】某隊(duì)列初始為空，若它的輸入序列為（a，b，c，d），它的輸出序列應(yīng)為（）。A．a(chǎn)，b，c，dB．d，c，b，aC．a(chǎn)，c，b，dD．d，a，c，b隱藏答案【答案】A【解析】隊(duì)列的出隊(duì)序列一定與入隊(duì)序列完全一樣。2、隊(duì)列的基本運(yùn)算(1)置空隊(duì)列InitQueue(Q)，構(gòu)造一個(gè)空隊(duì)列。(2)判隊(duì)空QueueEmpty(Q)，若Q為空隊(duì)列，則返回TRUE，否則返回FALSE。(3)入隊(duì)列En(jueue(Q，x)，若隊(duì)列不滿，則將數(shù)據(jù)x插入到Q的隊(duì)尾。(4)出隊(duì)列DeQueue(Q)，若隊(duì)列不空，則刪除隊(duì)頭元素，并返回該元素。(5)取隊(duì)頭GetFront(Q)，若隊(duì)列不空，則返回隊(duì)頭元素。二、順序循環(huán)隊(duì)列1、順序隊(duì)列的概念隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)列。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)是利用一塊連續(xù)的存儲(chǔ)單元存放隊(duì)列中的元素的，設(shè)置兩個(gè)指針front和rear分別指示隊(duì)頭和隊(duì)尾元素在表中的位置?！纠吭O(shè)有一順序隊(duì)列Q，容量為5，初始狀態(tài)時(shí)Q.front=Q.rear=0，畫(huà)出做完下列操作后隊(duì)列及其頭尾指針的狀態(tài)變化情況，若不能入隊(duì)，請(qǐng)簡(jiǎn)述其理。（1）d，e，b入隊(duì)（2）d，e出隊(duì)（3）i，j入隊(duì)（4）b出隊(duì)（5）n，o，p入隊(duì)【解答】隊(duì)列及其頭尾指針的狀態(tài)變化情況如圖所示第（5）步操作無(wú)法進(jìn)行，因隊(duì)列已滿，再有元素入隊(duì)，就會(huì)溢出，發(fā)生假溢。2、順序循環(huán)隊(duì)為了解決順序隊(duì)的"假溢"問(wèn)題采用循環(huán)隊(duì)。約定循環(huán)隊(duì)的隊(duì)頭指針指向隊(duì)頭元素在數(shù)組中實(shí)際位置的前一個(gè)位置，隊(duì)尾指針指示隊(duì)尾元素在數(shù)組中的實(shí)際位置。其次再約定隊(duì)頭指針指示的結(jié)點(diǎn)不用于存儲(chǔ)隊(duì)列元素，只起標(biāo)志作用。這樣當(dāng)隊(duì)尾指針"繞一圈"后趕上隊(duì)頭指針時(shí)視為隊(duì)滿?！纠吭O(shè)Q是一個(gè)有11個(gè)元素存儲(chǔ)空間的順序循環(huán)隊(duì)列，初始狀態(tài)Q．front=Q．rear=0，寫(xiě)出下列操作后頭、尾指針的變化情況，若不能入隊(duì)，請(qǐng)說(shuō)明理由。d，e，b，g，h入隊(duì)；d，e出隊(duì)；i，j，k，l，m入隊(duì)；b出隊(duì)；n，o，p，q，r入隊(duì)【解答】注意：p入隊(duì)以后，隊(duì)列就滿了，不能再入隊(duì)了，此時(shí)隊(duì)列中的元素個(gè)數(shù)為10個(gè)（數(shù)組長(zhǎng)度是11）總結(jié)：隊(duì)中元素個(gè)數(shù)：

兩種情況合并為：（QueueSize+rear-front）%QueueSize；【真題選解】設(shè)循環(huán)隊(duì)列的容量為50(序號(hào)從0到49)，現(xiàn)經(jīng)過(guò)一系列的入隊(duì)和出隊(duì)運(yùn)算后，有①front=11，rear=29；②front=29，rear=11；在這兩種情況下，循環(huán)隊(duì)列中的元素個(gè)數(shù)分別是______和______。隱藏答案【解析】當(dāng)front=11，rear=29時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)=rear-front=29-11=18；當(dāng)front=29，rear=11時(shí)，循環(huán)隊(duì)列中的元素個(gè)數(shù)50-（front-rear）=50+rear-front=50+11-29=32?！敬鸢浮?8323、循環(huán)隊(duì)的順序存儲(chǔ)的類型定義#defineQueLleSize100typedefcharDataType；//假設(shè)數(shù)據(jù)為字符型typedefstruct{DataTypedata[QueueSize]；intfront，rear；}CirQueue；4、循環(huán)隊(duì)列基本運(yùn)算的各算法（1）置空隊(duì)列voidInitQueue(CirQueue*Q){Q->front=Q->rear=0;}（2）判隊(duì)空intQueueEmpty(CirQueue*Q){returnQ->rear==Q->front；}（3）判隊(duì)滿intQueueFull(CirQueue*Q){return(Q->rear+1)%QueueSize==Q->front;}(4)入隊(duì)列voidEnQueue(CirQueue*Q，DataTypex){//插入元素x為隊(duì)列Q新的隊(duì)尾元素if(QueueFull(Q))printf("Queueoverflow")；e1se{Q->data[Q->rear]=x；Q->ear=(Q->rear+1)％QueueSize；//循環(huán)意義下的加1}}（5）取隊(duì)頭元素DataTypeGetFront(CirQueue*Q){//獲取Q的隊(duì)頭元素值if(QueueEmpty(Q)){printf("Queueempty");exit(0)；｝elsereturnQ->data[Q->front]j｝（6）出隊(duì)列DataTypeDeQueue(CirQueue*Q){//刪除Q的隊(duì)頭元素，并返回其值DataTypex；if(QueueEmpty(Q)){printf("Queueempty")；exit(0)；}else{x=Q->data[Q->front];//保存待刪除元素值Q->front=(Q->front+1)％QueueSize；//頭指針加1returnx；//返回刪除元素值}}【例】設(shè)棧S=(1，2，3，4，5，6，7)，其中7為棧頂元素。請(qǐng)寫(xiě)出調(diào)用函數(shù)Algo(S)后棧S的狀態(tài)。其函數(shù)為：voidAlgo(SeqStackS){inti=l；CirQueueQ；SeqStackT;//定義一個(gè)循環(huán)隊(duì)列和一個(gè)棧InitQueue(&Q);Initstack(&T)；//初始化隊(duì)列和棧while(!StackEmpty(&S)){if(i％2!=0)Push(&T，Pop(&S))；//棧中序號(hào)為奇數(shù)的元素入T棧中//7、5、3、1順序入棧T。elseEnQueue(&Q，Pop(&S))；//序號(hào)為偶數(shù)的元素入隊(duì)列Q中//6、4、2順序入隊(duì)Q。i++；}while(!QueueEmpty(&Q))Push(&S，DeQueue(&Q))；//隊(duì)Q中6、4、2順序出隊(duì)并入棧Swhile(!StackEmpty(&T))Push(&S，Pop(&T));//隊(duì)棧T中按1、3、5、7順序出棧并入棧S}最后棧S中的元素為（6、4、2、1、3、5、7）。三、鏈隊(duì)1、鏈隊(duì)的定義隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)稱為鏈隊(duì)列。它是一種限制在表頭刪除和表尾插入操作的單鏈表。2、鏈隊(duì)的數(shù)據(jù)類型定義typedefstructqnode{DataTypedata;structqnode*next;｝QueueNode；typedefstruct{QueueNode*front；//隊(duì)頭指針QueueNode*rear；//隊(duì)尾指針｝LinkQueue；LinkQueueQ；3、鏈隊(duì)的基本運(yùn)算實(shí)現(xiàn)（1）構(gòu)造空隊(duì)列voidInitQueue(LinkQueue*Q){Q->front=(QueueNode*)malloc(sizeof(QueueNode))；//申請(qǐng)頭結(jié)點(diǎn)Q->rear=Q->front;//尾指針也指向頭結(jié)點(diǎn)Q->rear->next=NULL;)（2）判隊(duì)空intQueueEmpty(LinkQueue*Q){returnQ->rear==Q->front；//頭尾指針相等隊(duì)列為空)（3）入隊(duì)列voidEnQueue(LinkQueue*Q，DataTypex){//將元素x插入鏈隊(duì)列尾部QueueNode*p=(QueueNode*)malloc(Sizeof(QueueNode));//申請(qǐng)新結(jié)點(diǎn)p->data=x;p->next=NULL;Q->rear->next=p；//*p鏈到原隊(duì)尾結(jié)點(diǎn)之后Q->rear=p;//隊(duì)尾指針指向新的隊(duì)尾結(jié)點(diǎn)}（4）取隊(duì)頭元素DataTypeGetFront(LinkQueue*Q){//取鏈隊(duì)列的隊(duì)頭元素值if(QueueEmpty(Q))//判隊(duì)空{(diào)printf("Queueunderflow")；exit(0)；//出錯(cuò)退出處理}elsereturnQ->front->next->data；//返回原隊(duì)頭元素值)（5）出隊(duì)列鏈隊(duì)列的出隊(duì)操作有兩種不同情況要分別考慮。①當(dāng)隊(duì)列的長(zhǎng)度大于1時(shí)，則出隊(duì)操作只需要修改頭結(jié)點(diǎn)的指針域即可，尾指針不變,類似于單鏈表刪除首結(jié)點(diǎn)，操作步驟：s=Q->front->next；Q->fron->next=s->next；x=s->data；free(s)；returnx；//釋放隊(duì)頭結(jié)點(diǎn)，并返回其值②若列隊(duì)長(zhǎng)度等于l，則出隊(duì)時(shí)不僅要修改頭結(jié)點(diǎn)指針域，而且還需要修改尾指針。s=Q->front->next；Q->front->next=NULL；//修隊(duì)頭指針Q->rear=Q->front；//修改尾指針x=s->data；free(s)；returnx；//釋放隊(duì)頭結(jié)點(diǎn)，并返回其值為了方便，直接刪除頭結(jié)點(diǎn)，將原隊(duì)頭結(jié)點(diǎn)當(dāng)頭結(jié)點(diǎn)使，這樣算法就簡(jiǎn)單了。鏈隊(duì)列的出隊(duì)算法描述DataTypeDeQueue(LinkQueue*Q){//刪除鏈隊(duì)列的頭結(jié)點(diǎn)，并返回頭結(jié)點(diǎn)的元素值QueueNode*P；if(QueueEmpty(Q)){printf("Queueunderflow")；exit(0)；//出錯(cuò)退出處理}else{p=Q->front；//p指向頭結(jié)點(diǎn)Q->front=Q->front->next;//頭指針指向原隊(duì)頭結(jié)點(diǎn)free(p)；//刪除釋放原頭結(jié)點(diǎn)return(Q->front->data);//返回原隊(duì)頭結(jié)點(diǎn)的數(shù)據(jù)值}}【真題選解】算法f31的功能是清空帶頭結(jié)點(diǎn)的鏈隊(duì)列Q.請(qǐng)?jiān)诳杖碧幪钊牒线m的內(nèi)容,使其成為一個(gè)完整的算法.typedefstructnode{DataTypedata；structnode*next；}QueueNode；typedefstruct{QueueNode*front；//隊(duì)頭指針QueueNode*rear；//隊(duì)尾指針}LinkQueue；voidf31(LinkQueue*Q){QueueNode*p,*s；p=(1)；while(p！=NULL){s=p；p=p->next;free(s);}________(2)=NULL;Q->rear=_______(3)_______；}(1)__________________________________________(2)__________________________________________(3)__________________________________________隱藏答案【解析】算法f31的功能是清空帶頭結(jié)點(diǎn)的鏈隊(duì)列Q，就是要?jiǎng)h除除了頭結(jié)點(diǎn)以外的所有結(jié)點(diǎn)，指針p負(fù)責(zé)掃描整個(gè)隊(duì)列，所以第（1）空應(yīng)該填Q->front->next。通過(guò)執(zhí)行while循環(huán)，刪除了除了頭結(jié)點(diǎn)以外的所有結(jié)點(diǎn)，最后要將頭結(jié)點(diǎn)的指針域填上NULL，隊(duì)尾指針指向頭結(jié)點(diǎn)。所以，第（2）空應(yīng)該填Q->front->next，第（3）空填Q->front。【答案】（1）Q->front->next（2）Q->front->next（3）Q->front4、循環(huán)鏈隊(duì)列循環(huán)鏈隊(duì)列的類型定義typedefstructqueuenode{DataTypedata；structqueuenode*next；}QueueNode；QuelaeNode*rear；（1）初始化空隊(duì)列QueueNode*InitQueue(QueueNode*rear){tear=(QueueNode*)malloc(sizeof(QueueNode))；//申請(qǐng)頭結(jié)點(diǎn)rear->next=rear；returnrear；}（2）入隊(duì)列voidEnQueue(QueueNode*rear，Datatypex){QueueNode*s=(QueueNode*)malloc(sizeof(QueueNode))；//申請(qǐng)新結(jié)點(diǎn)s->data=x：s->next=rear->next；rear->next=s；rear=s；}當(dāng)前講授（3）出隊(duì)列DataTypeDelQueue(QueueNode*rear){QueueNode*s，*t；DataTy