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

第5章隊(duì)列

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

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

2、隊(duì)列的鏈?zhǔn)奖硎九c實(shí)現(xiàn)5.1隊(duì)列的定義與抽象數(shù)據(jù)類型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)

采用鏈?zhǔn)酱鎯?chǔ)的隊(duì)列被稱為鏈?zhǔn)疥?duì)列或鏈隊(duì)列。鏈?zhǔn)疥?duì)列在插入和刪除過(guò)程中，不需要移動(dòng)大量的元素，只需要改變指針的位置即可。5.3.1鏈?zhǔn)疥?duì)列的表示順序隊(duì)列在插入和刪除操作過(guò)程中需要移動(dòng)大量元素，這樣算法的效率會(huì)比較低，為了避免以上問(wèn)題，可采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示隊(duì)列。

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

一個(gè)不帶頭結(jié)點(diǎn)的鏈?zhǔn)疥?duì)列和帶頭結(jié)點(diǎn)的鏈隊(duì)列分別如圖5.12、圖5.13所示。5.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)

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

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

voidClearQueue(LinkQueue*LQ)/*清空隊(duì)列*/{while(LQ->front!=NULL){LQ->rear=LQ->front->next; /*隊(duì)尾指針指向隊(duì)頭指針指向的下一個(gè)結(jié)點(diǎn)*/free(LQ->front); /*釋放隊(duì)頭指針指向的結(jié)點(diǎn)*/LQ->front=LQ->rear;/*隊(duì)頭指針指向隊(duì)尾指針*/}}5.3隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及實(shí)現(xiàn)5.3.3鏈?zhǔn)疥?duì)列舉例

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

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

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

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