零基礎(chǔ)學(xué)數(shù)據(jù)結(jié)構(gòu)光盤文件第5章隊列

第5章隊列

與棧一樣，隊列也是一種操作受限的線性表。隊列在操作系統(tǒng)和事務(wù)管理等軟件設(shè)計中應(yīng)用廣泛，如鍵盤輸入緩沖區(qū)問題就是利用隊列的思想實現(xiàn)的。本章重點和難點：

1、隊列的順序表示與實現(xiàn)

2、隊列的鏈式表示與實現(xiàn)5.1隊列的定義與抽象數(shù)據(jù)類型

隊列只允許在表的一端進行插入操作，在表的另一端進行刪除操作。5.1.1什么是隊列隊列（queue）是一種先進先出（firstinfirstout，縮寫為FIFO）的線性表，它只允許在表的一端進行插入，另一端刪除元素。這與我們?nèi)粘Ｉ钪械呐抨犑且恢碌?，最早進入隊列的元素最早離開。在隊列中，允許插入的一端稱為隊頭（front），允許刪除的一端稱為隊尾（rear）。5.1隊列的定義與抽象數(shù)據(jù)類型

假設(shè)隊列為q=（a1，a2，…，ai，…，an），那么a1為隊頭元素，an為隊尾元素。進入隊列時，是按照a1，a2，…，an的順序進入的，退出隊列時也是按照這個順序退出的。也就是說，當(dāng)先進入隊列的元素都退出之后，后進入隊列的元素才能退出。即只有當(dāng)a1，a2，…，an-1都退出隊列以后，an才能退出隊列。5.1隊列的定義與抽象數(shù)據(jù)類型5.1.2隊列的抽象數(shù)據(jù)類型

1．?dāng)?shù)據(jù)對象集合隊列的數(shù)據(jù)對象集合為{a1，a2，…，an}，每個元素都具有相同的數(shù)據(jù)類型DataType。隊列中的數(shù)據(jù)元素之間也是一對一的關(guān)系。除了第一個元素a1外，每一個元素有且只有一個直接前驅(qū)元素，除了最后一個元素an外，每一個元素有且只有一個直接后繼元素。5.1隊列的定義與抽象數(shù)據(jù)類型2．基本操作集合（1）InitQueue(&Q)：初始化操作，建立一個空隊列Q。（2）QueueEmpty(Q)：若Q為空隊列，返回1，否則返回0。（3）EnQueue(&Q,e)：插入元素e到隊列Q的隊尾。（4）DeQueue(&Q,&e)：刪除Q的隊首元素，并用e返回其值。（5）Gethead(Q,&e)：用e返回Q的隊首元素。（6）ClearQueue(&Q)：將隊列Q清空。5.2隊列的順序存儲及實現(xiàn)5.2.1順序隊列的表示順序隊列通常采用一維數(shù)組依次存放從隊頭到隊尾的元素。同時，使用兩個指針分別指示數(shù)組中存放的第一個元素和最后一個元素的位置。其中，指向第一個元素的指針被稱為隊頭指針front，指向最后一個元素的指針被稱為隊尾指針rear。元素a、b、c、d、e、f、g依次進入隊列后的狀態(tài)如圖5.2所示。元素a存放在數(shù)組下標為0的存儲單元中，g存放在下標為6的存儲單元中，隊頭指針front指向第一個元素a，隊尾指針rear指向最后一個元素g的下一位置。5.2隊列的順序存儲及實現(xiàn)

在使用隊列前，先初始化隊列，此時，隊列為空，隊頭指針front和隊尾指針rear都指向隊列的第一個位置，即front=rear=0，如圖5.3所示。每一個元素進入隊列，隊尾指針rear就會增1，若元素a、b、c依次進入空隊列，front指向第一個元素，rear指向下標為3的存儲單元，如圖5.4所示。5.2隊列的順序存儲及實現(xiàn)當(dāng)一個元素出隊列時，隊頭指針front增1，隊頭元素即a出隊后，front向后移動一個位置，指向下一個位置，rear不變，如圖5.5所示。5.2隊列的順序存儲及實現(xiàn)5.2.2順序隊列的“假溢出”在對順序隊列進行插入和刪除操作的過程中，可能會出現(xiàn)“假溢出”現(xiàn)象。經(jīng)過多次插入和刪除操作后，實際上隊列還有存儲空間，但是又無法向隊列中插入元素，我們將這種溢出稱為“假溢出”。例如，在圖5.2所示的隊列中插入3個元素h、i、j，然后刪除2個元素a，b之后，就會出現(xiàn)如圖5.6所示的情況。當(dāng)插入元素j后，隊尾指針rear將越出數(shù)組的下界而造成“假溢出”。5.2隊列的順序存儲及實現(xiàn)5.2.3順序循環(huán)隊列的表示

1．順序循環(huán)隊列為了充分利用存儲空間，消除這種“假溢出”現(xiàn)象，當(dāng)隊尾指針rear和隊頭指針front到達存儲空間的最大值（假定隊列的存儲空間為QueueSize）的時候，讓隊尾指針和隊頭指針轉(zhuǎn)化為0，這樣就可以將元素插入到隊列還沒有利用的存儲單元中。例如，在圖5.6中，插入元素j之后，rear將變?yōu)?，可以繼續(xù)將元素插入到下標為0的存儲單元中。這樣就把順序隊列使用的存儲空間構(gòu)造成一個邏輯上首尾相連的循環(huán)隊列。5.2隊列的順序存儲及實現(xiàn)

當(dāng)隊尾指針rear達到最大值QueueSize-1時，前提是隊列中還有存儲空間，若要插入元素，就要把隊尾指針rear變?yōu)?；當(dāng)隊頭指針front達到最大值QueueSize-1時，若要將隊頭元素出隊，要讓隊頭指針front變?yōu)?。這可通過取余操作實現(xiàn)隊列的首尾相連。例如，假設(shè)QueueSize=10，當(dāng)隊尾指針rear=9時，若要將新元素入隊，則先令rear=（rear+1）%10=0，然后將元素存入隊列的第0號單元，通過取余操作實現(xiàn)了隊列的邏輯上的首尾相連。5.2隊列的順序存儲及實現(xiàn)2．順序循環(huán)隊列的隊空和隊滿判斷但是，在順序循環(huán)隊列在隊空和隊滿的情況下，隊頭指針front和隊尾指針rear同時都會指向同一個位置，即front==rear，如圖5.7所示。即隊列為空時，有front=0，rear=0，因此front==rear。隊滿時也有front=0，rear=0，因此front==rear。5.2隊列的順序存儲及實現(xiàn)為了區(qū)分這隊空還是隊滿，通常有兩個方法：（1）增加一個標志位。設(shè)這個標志位為flag，初始時，有flag=0；當(dāng)入隊列成功，則flag=1；出隊列成功，有flag=0。則隊列為空的判斷條件為：front==rear&&flag==0，隊列滿的判斷條件為：front==rear&&flag==1。（2）少用一個存儲單元。隊空的判斷條件為front==rear，隊滿的判斷條件為front==(rear+1)%QueueSize。那么，入隊的操作語句為：rear=（rear+1）%QueueSize，Q[rear]=x。出隊的操作語句為：front=（front+1）%QueueSize。少用一個存儲單元的順序循環(huán)隊列隊滿情況如圖5.8所示。5.2隊列的順序存儲及實現(xiàn)

順序循環(huán)隊列類型描述如下：

#defineQueueSize60 /*隊列的容量*/typedefstructSqueue{DataTypequeue[QueueSize];intfront,rear; /*隊頭指針和隊尾指針*/}SeqQueue;

其中，queue用來存儲隊列中的元素，front和rear分別表示隊頭指針和隊尾指針，取值范圍為0~QueueSize。5.2隊列的順序存儲及實現(xiàn)

順序循環(huán)隊列的主要操作說明如下：（1）初始化時，設(shè)置SQ.front=SQ.rear=0。（2）循環(huán)隊列隊空的條件為SQ.front==SQ.rear，隊滿的條件為SQ.front==（SQ.rear+1）%QueueSize。（3）入隊操作：先判斷隊列是否已滿，若隊列未滿，則將元素值e存入隊尾指針指向的存儲單元，然后將隊尾指針加1后取模。（4）出隊操作：先判斷隊列是否為空，若隊列不空，則先把隊頭指針指向的元素值賦給e，即取出隊頭元素，然后將隊頭指針加1后取模。（5）循環(huán)隊列的長度為（SQ.rear+QueueSize-SQ.front）%QueueSize。5.2隊列的順序存儲及實現(xiàn)

5.2.4順序循環(huán)隊列的基本運算順序循環(huán)隊列的基本運算算法實現(xiàn)如下（以下算法的實現(xiàn)保存在文件SeqQueue.h中）。（1）初始化隊列。

voidInitQueue(SeqQueue*SCQ)/*順序循環(huán)隊列的初始化*/{SCQ->front=SCQ->rear=0;}5.2隊列的順序存儲及實現(xiàn)（2）判斷隊列是否為空。若隊頭指針與隊尾指針相等，則隊列為空；否則隊列不為空。算法實現(xiàn)如下。intQueueEmpty(SeqQueueSCQ)/*判斷順序循環(huán)隊列是否為空，隊列為空返回1，否則返回0*/{if(SCQ.front==SCQ.rear) /*當(dāng)順序循環(huán)隊列為空時*/return1; /*返回1*/else /*否則*/return0; /*返回0*/}5.2隊列的順序存儲及實現(xiàn)（3）將元素e入隊。

intEnQueue(SeqQueue*SCQ,DataTypee){if(SCQ->front==(SCQ->rear+1)%QueueSize)/*在插入新的元素之前，判斷隊尾指針是否到達數(shù)組的最大值*/return0;SCQ->queue[SCQ->rear]=e;/*在隊尾插入元素e*/SCQ->rear=(SCQ->rear+1)%QueueSize; /*隊尾指針向后移動一個位置*/return1;}5.2隊列的順序存儲及實現(xiàn)（4）將隊頭元素出隊。intDeQueue(SeqQueue*SCQ,DataType*e){if(SCQ->front==SCQ->rear) /*在刪除元素之前，判斷順序循環(huán)隊列是否為空*/return0;else{*e=SCQ->queue[SCQ->front]; /*將要刪除的元素賦值給e*/SCQ->front=(SCQ->front+1)%QueueSize; /*將隊頭指針向后移動一個位置，指向新的隊頭*/return1;}}5.2隊列的順序存儲及實現(xiàn)（5）取隊頭元素。先判斷順序循環(huán)隊列是否為空，如果隊列為空，則返回0表示取隊頭元素失?。环駝t，把隊頭元素賦給e，并返回1表示取隊頭元素成功。

intGetHead(SeqQueueSCQ,DataType*e){if(SCQ.front==SCQ.rear) /*在取隊頭元素之前，判斷順序循環(huán)隊列是否為空*/return0;else{*e=SCQ.queue[SCQ.front]; /*將隊頭元素賦值給e，取出隊頭元素*/return1;}}5.2隊列的順序存儲及實現(xiàn)5.2.5順序循環(huán)隊列舉例

【例5_1】假設(shè)在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲。現(xiàn)要求寫一算法模擬上述舞伴配對問題。

【分析】先入隊的男士或女士先出隊配成舞伴。因此該問題具體有典型的先進先出特性，可用隊列作為算法的數(shù)據(jù)結(jié)構(gòu)。

5.3隊列的鏈式存儲及實現(xiàn)

采用鏈式存儲的隊列被稱為鏈式隊列或鏈隊列。鏈式隊列在插入和刪除過程中，不需要移動大量的元素，只需要改變指針的位置即可。5.3.1鏈式隊列的表示順序隊列在插入和刪除操作過程中需要移動大量元素，這樣算法的效率會比較低，為了避免以上問題，可采用鏈式存儲結(jié)構(gòu)表示隊列。

1．鏈式隊列鏈式隊列通常用鏈表實現(xiàn)。一個鏈隊列顯然需要兩個分別指示隊頭和隊尾的指針（分別稱為隊頭指針和隊尾指針）才能唯一確定。這里，與單鏈表一樣，為了操作上的方便，我們給鏈隊列添加一個頭結(jié)點，并令隊頭指針front指向頭結(jié)點，用隊尾指針rear指向最后一個結(jié)點。5.3隊列的鏈式存儲及實現(xiàn)

一個不帶頭結(jié)點的鏈式隊列和帶頭結(jié)點的鏈隊列分別如圖5.12、圖5.13所示。5.3隊列的鏈式存儲及實現(xiàn)

對于帶頭結(jié)點的鏈式隊列，當(dāng)隊列為空時，隊頭指針front和隊尾指針rear都指向頭結(jié)點。如圖5.14所示。鏈式隊列中，插入和刪除操作只需要移動隊頭指針和隊尾指針，這兩種操作的指針變化如圖5.15、圖5.16和圖5.17所示。圖5.15表示在隊列中插入元素a的情況，圖5.16表示隊列中插入了元素a，b，c之后的情況，圖5.17表示元素a出隊列的情況。5.3隊列的鏈式存儲及實現(xiàn)鏈式隊列的類型描述如下：/*結(jié)點類型定義*/typedefstructQNode{DataTypedata;structQNode*next;}LQNode,*QueuePtr;/*隊列類型定義*/typedefstruct{QueuePtrfront;QueuePtrrear;}LinkQueue;5.3隊列的鏈式存儲及實現(xiàn)2．鏈式循環(huán)隊列將鏈式隊列的首尾相連就構(gòu)成了鏈式循環(huán)隊列。在鏈式循環(huán)隊列中，可以只設(shè)置隊尾指針，如圖5.18所示。當(dāng)隊列為空時，如圖5.19所示，隊列LQ為空的判斷條件為LQ.rear->next==LQ.rear。5.3隊列的鏈式存儲及實現(xiàn)5.3.2鏈式隊列的基本運算鏈式隊列的基本運算算法實現(xiàn)如下。（1）初始化隊列。voidInitQueue(LinkQueue*LQ)/*初始化鏈式隊列*/{LQ->front=LQ->rear=(LQNode*)malloc(sizeof(LQNode));if(LQ->front==NULL)exit(-1);LQ->front->next=NULL; /*把頭結(jié)點的指針域置為為0*/}5.3隊列的鏈式存儲及實現(xiàn)（2）判斷隊列是否為空。intQueueEmpty(LinkQueueLQ)/*判斷鏈式隊列是否為空，隊列為空返回1，否則返回0*/{if(LQ.rear->next==NULL)/*當(dāng)鏈式隊列為空時*/return1; /*返回1*/else /*否則*/return0; /*返回0*/}5.3隊列的鏈式存儲及實現(xiàn)

（3）將元素e入隊。先為新結(jié)點申請一個空間，然后將e賦給數(shù)據(jù)域，并使原隊尾元素結(jié)點的指針域指向新結(jié)點，隊尾指針指向新結(jié)點，從而將結(jié)點加入隊列中。操作過程如圖5.20所示。將元素e入隊的算法實現(xiàn)如下。intEnQueue(LinkQueue*LQ,DataTypee)/*將元素e插入到鏈式隊列LQ中，插入成功返回1*/{LQNode*s;s=(LQNode*)malloc(sizeof(LQNode)); if(!s)exit(-1); /*如果申請空間失敗，則退出并返回參數(shù)-1*/s->data=e; /*將元素值賦值給結(jié)點的數(shù)據(jù)域*/s->next=NULL;/*將結(jié)點的指針域置為空*/LQ->rear->next=s; /*將原來隊列的隊尾指針指向s*/LQ->rear=s; /*將隊尾指針指向s*/return1;}5.3隊列的鏈式存儲及實現(xiàn)5.3隊列的鏈式存儲及實現(xiàn)（4）將隊頭元素出隊。intDeQueue(LinkQueue*LQ,DataType*e){LQNode*s;if(LQ->front==LQ->rear)/*判斷鏈式隊列是否為空*/return0;else{s=LQ->front->next; /*使指針s指向隊頭元素的指針*/*e=s->data; /*將要刪除的隊頭元素賦給e*/LQ->front->next=s->next;/*使頭結(jié)點指針指向s的下一個結(jié)點*/if(LQ->rear==s)LQ->rear=LQ->front; /*如果要刪除的結(jié)點是隊尾，則使隊尾指針指向隊頭指針*/free(s); /*釋放指針s指向的結(jié)點空間*/return1;}}5.3隊列的鏈式存儲及實現(xiàn)（5）取隊頭元素。intGetHead(LinkQueueLQ,DataType*e){LQNode*s;if(LQ.front==LQ.rear)/*在取隊頭元素之前，判斷鏈式隊列是否為空*/return0;else{s=LQ.front->next;/*將指針p指向隊列的第一個元素即隊頭元素*/*e=s->data; /*將隊頭元素賦給e，取出隊頭元素*/return1;}}（6）清空隊列。

voidClearQueue(LinkQueue*LQ)/*清空隊列*/{while(LQ->front!=NULL){LQ->rear=LQ->front->next; /*隊尾指針指向隊頭指針指向的下一個結(jié)點*/free(LQ->front); /*釋放隊頭指針指向的結(jié)點*/LQ->front=LQ->rear;/*隊頭指針指向隊尾指針*/}}5.3隊列的鏈式存儲及實現(xiàn)5.3.3鏈式隊列舉例

【例5_2】編寫一個算法，判斷任意給定的字符序列是否為回文。所謂回文是指一個字符序列以中間字符為基準兩邊字符完全相同，即順著看和倒著看是相同的字符序列。例如，字符序列“XYZMTATMZYX”為回文，而字符序列"XYZBZXY"不是回文。5.3隊列的鏈式存儲及實現(xiàn)5.4.1什么是雙端隊列雙端隊列是限定插入和刪除操作在表兩端進行的線性表。這兩端分別稱為端點1和端點2。雙端隊列可以在隊列的任何一端進行插入和刪除操作，而一般的隊列要求在一端插入元素，在另一端刪除元素。一個雙端隊列如圖5.22所示。5.4雙端隊列

在圖5.22中，可以在隊列的左端或右端插入元素，也可以在隊列的左端或右端刪除元素。其中，end1和end2分別是雙端隊列的指針。在實際應(yīng)用中，還有輸入受限和輸出受限的雙端隊列。所謂輸入受限的雙端隊列指的是只允許在隊列的一端插入元素，而兩端都能刪除元素的隊列。所謂輸出受限的雙端隊列指的是只允許在隊列的一端刪除元素，兩端都能輸入元素的隊列。5.4雙端隊列

5.4.2雙端隊列的應(yīng)用采用一個一維數(shù)組作為雙端隊列的數(shù)據(jù)存儲結(jié)構(gòu)，試編寫入隊算法和出隊算法。雙端隊列為空的狀態(tài)如圖5.23所示。在實際操作過程中，用循環(huán)隊列實現(xiàn)雙端隊列的操作是比較恰當(dāng)?shù)?。元素a，b，c依次進入左端的隊列，元素e，f依次進入右端的隊列，如圖5.24所示。5.4雙端隊列【例5_4】編寫算法，實現(xiàn)雙端隊列的入隊和出隊操作。求：（1）當(dāng)隊列滿時，最多只能有一個存儲空間為空；（2）在進行插入和刪除元素時，隊列中的其他元素不動。分析：設(shè)雙端隊列為Q，初始時，隊列為空，有Q.end1==Q.end2，隊滿的條件為（Q.end1-1+QueueSize）%QueueSize==Q.end2或（Q.end2+1+QueueSize）%QueueSize==Q.end1。對于左端的隊列，當(dāng)元素入隊時，需要執(zhí)行Q.end-1操作；當(dāng)元素出隊列時，需要執(zhí)行Q.end1+1操作。對于右端的隊列，當(dāng)元素入隊時，需要執(zhí)行Q.end2+1操作；當(dāng)元素出隊列時，需要執(zhí)行Q.end2-1操作。5.4雙端隊列

設(shè)停車場是一個可停放n輛汽車的狹長通道，且只有一個大門可供汽車進出。汽車在停車場內(nèi)按車輛到達時間的先后順序，依次由北向南排列（大門在最南端，最先到達的第一輛車停放在車場的最北端）。若停車場內(nèi)已經(jīng)停滿n輛車，那么后來的車只能在門外的