數(shù)據(jù)結(jié)構(gòu)課件隊(duì)列

4.7隊(duì)列隊(duì)列的例子：日常生活中隊(duì)列很常見。如，我們經(jīng)常排隊(duì)購物或購票，排隊(duì)是體現(xiàn)了“先來先服務(wù)”（即“先進(jìn)先出”）的原則。買完東西的人總是從隊(duì)列的隊(duì)頭離開，而新來的人總是從隊(duì)尾進(jìn)入該隊(duì)列。計(jì)算機(jī)系統(tǒng)中輸入輸出緩沖區(qū)的結(jié)構(gòu)也是隊(duì)列的應(yīng)用。例如：打印文件時(shí)，在主機(jī)和打印機(jī)之間設(shè)置一個(gè)緩沖區(qū)。緩沖區(qū)中數(shù)據(jù)的邏輯結(jié)構(gòu)即為一個(gè)隊(duì)列，遵循“先進(jìn)先出”的原則。4.7.1隊(duì)列的定義及其運(yùn)算1．隊(duì)列的定義

隊(duì)列（queue）也是一種操作受限的線性表。其限制表現(xiàn)在：只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除。只允許進(jìn)行插入的一端稱為隊(duì)尾（rear），只允許進(jìn)行刪除的一端稱為隊(duì)頭或隊(duì)首(front)。隊(duì)列的插入操作通常稱為進(jìn)隊(duì)，而隊(duì)列的刪除操作則稱為出隊(duì)。當(dāng)隊(duì)列中無數(shù)據(jù)元素時(shí)，稱為空隊(duì)。隊(duì)列是按照先進(jìn)先出（FIFO，firstinfirstout）的原則組織數(shù)據(jù)的，因此，隊(duì)列也被稱為“先進(jìn)先出”表。例：隊(duì)列q=(a1，a2，a3，…，an)，則進(jìn)隊(duì)的順序?yàn)閍1，a2，a3，…，an，隊(duì)頭元素為a1，隊(duì)尾元素為an。進(jìn)隊(duì)出隊(duì)a1a2a3aianfrontrear隊(duì)列的示意圖……

下圖是一個(gè)隊(duì)列的示意圖，通常用指針front指示隊(duì)頭的位置，用指針rear指向隊(duì)尾。4.7.1隊(duì)列的定義及其運(yùn)算2．隊(duì)列的基本運(yùn)算(1)InitQueue(Q)初始化：初始化一個(gè)新的隊(duì)列，即置為空。(2)ClearQueue(Q)清空隊(duì)列：清除隊(duì)列中所有元素，并置為空。(3)EmptyQueue(Q)隊(duì)列的空判斷：若隊(duì)列Q為空，則返回true；否則，返回false。(4)PeekQueue(Q)讀取隊(duì)頭元素：若隊(duì)列Q不空，則返回隊(duì)頭元素。但未刪除隊(duì)頭元素，故隊(duì)頭指針不變。(5)EnQueue(Q,item)進(jìn)隊(duì)：在隊(duì)列Q的尾部插入元素item，使元素item成為新的隊(duì)尾。(6)OutQueue(Q)出隊(duì)：若隊(duì)列Q不空，則返回隊(duì)頭元素，并從隊(duì)頭刪除該元素，隊(duì)頭指針指向原隊(duì)頭的后繼元素。隊(duì)列是一種特殊的線性表，因此隊(duì)列可采用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)，也可以使用鏈接存儲(chǔ)結(jié)構(gòu)存儲(chǔ)。4.7.3隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)1．順序隊(duì)列的數(shù)組表示

與順序表、順序棧類似，隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)可以簡(jiǎn)稱為順序隊(duì)列，也就是利用一塊連續(xù)存儲(chǔ)空間依次存放隊(duì)列中的數(shù)據(jù)元素。一般情況下，我們使用一維數(shù)組來作為隊(duì)列的順序存儲(chǔ)空間，另外再設(shè)兩個(gè)具有指示作用的整型變量：一個(gè)指向隊(duì)頭元素的front，另一個(gè)指向隊(duì)尾元素的rear。對(duì)數(shù)組而言，front和rear分別為隊(duì)頭元素和隊(duì)尾元素的數(shù)組下標(biāo)值。用C或C++定義的順序存儲(chǔ)結(jié)構(gòu)的隊(duì)列如下：structQueue{ElemTypequeue[MaxSize];intfront;intrear;};當(dāng)插入新的數(shù)據(jù)元素時(shí)，隊(duì)尾指針rear＋1，而當(dāng)隊(duì)頭元素出隊(duì)列時(shí)，隊(duì)頭指針front＋1。隊(duì)列的存儲(chǔ)結(jié)構(gòu)（a）隊(duì)列中有一個(gè)元素A；（b）元素B、C、D、E進(jìn)隊(duì)后；（c）元素A、B、C出隊(duì)后；（d）所有元素出隊(duì)，隊(duì)為空后front=5（d）rear=4rear=4D（c）Efront=3

下圖給出了隊(duì)列中頭尾指針的變化狀態(tài)。front=0A（a）rear=0front=0ABE（b）rear=4CD不斷進(jìn)隊(duì)，不斷出隊(duì)的結(jié)果是：4.7.3隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)

整個(gè)隊(duì)列往一個(gè)方向移動(dòng)。結(jié)果使隊(duì)列前面空出許多單元，而隊(duì)尾已達(dá)存儲(chǔ)區(qū)的邊緣，也就是數(shù)組中queue[MaxSize－1]的位置。再往后就無法插入元素。顯然，這樣是很浪費(fèi)存儲(chǔ)空間的。解決的辦法是：將隊(duì)列頭尾相接，構(gòu)成一個(gè)環(huán)狀結(jié)構(gòu)，稱為循環(huán)隊(duì)列。循環(huán)隊(duì)列MaxSize-101rearfront循環(huán)隊(duì)列示意將順序隊(duì)列的存儲(chǔ)區(qū)假想為一個(gè)環(huán)狀的空間，如左圖所示。則queue[0]就接在queue[MaxSize-1]的后面。在循環(huán)隊(duì)列中，每插入一個(gè)新元素時(shí)，就把隊(duì)尾指針沿順時(shí)針方向移動(dòng)一個(gè)位置。rear=(rear+1)%MaxSize每刪除一個(gè)元素時(shí)，就把隊(duì)頭指針沿順時(shí)針方向移動(dòng)一個(gè)位置。front=(front+1)%MaxSize隊(duì)空情況：由圖可見：當(dāng)元素不斷出隊(duì)，只剩下一個(gè)元素時(shí)，front=rear，當(dāng)隊(duì)空時(shí)，front=(rear+1)%MaxSize012345frontrearABCDfrontrear012345Dfrontrear012345（a）隊(duì)非空時(shí)（b）隊(duì)中只剩一個(gè)元素時(shí)（c）隊(duì)空時(shí)隊(duì)滿情況：由圖可見：當(dāng)元素不斷進(jìn)隊(duì)，隊(duì)滿時(shí)，也有front=(rear+1)%MaxSize（a）隊(duì)非滿時(shí)（b）隊(duì)滿時(shí)front012345ABCDrearfrontrear012345ABCDEF隊(duì)空和隊(duì)滿的條件相同，就無法區(qū)分何時(shí)隊(duì)空，何時(shí)隊(duì)滿。解決這一問題的方法是：犧牲一個(gè)單元，不用于存放元素，讓隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置。隊(duì)空情況：可見：當(dāng)隊(duì)空時(shí)，front=rear012345frontrearABCDfrontrear012345Dfrontrear012345（a）隊(duì)非空時(shí)（b）隊(duì)中只剩一個(gè)元素時(shí)（c）隊(duì)空時(shí)犧牲一個(gè)單元，不用于存放元素，則整個(gè)隊(duì)列最多能存儲(chǔ)MaxSize-1個(gè)元素。隊(duì)頭指針front指向隊(duì)頭元素的前一個(gè)位置。當(dāng)元素不斷進(jìn)隊(duì)，隊(duì)滿時(shí)，front=(rear+1)%MaxSize，此條件仍與前面的隊(duì)滿條件相同。這樣，隊(duì)空和隊(duì)滿的條件不同，就可以區(qū)分這兩種情況。下面我們討論的順序隊(duì)列上的操作都是針對(duì)這種犧牲了一個(gè)單元的循環(huán)隊(duì)列而言。隊(duì)滿情況：（a）隊(duì)非滿時(shí)（b）隊(duì)滿時(shí)front012345ABCDrearfrontrear012345ABCDE2.順序隊(duì)列的操作實(shí)現(xiàn)（1）初始化隊(duì)列函數(shù)名：InitQueue

形參：順序隊(duì)列Q

返回值：無功能：置隊(duì)列為空。隊(duì)空的條件為front=rear，初始情況令它們都等于0，所以令front＝rear＝0（2）清空隊(duì)列函數(shù)名：ClearQueue

形參：順序隊(duì)列Q

返回值：無功能：對(duì)靜態(tài)順序隊(duì)列而言，此算法與初始化隊(duì)列完全相同。

2.順序隊(duì)列的操作實(shí)現(xiàn)（3）判別隊(duì)空函數(shù)名：EmptyQueue

形參：順序隊(duì)列Q

返回值：若隊(duì)空返回true，否則返回false

功能：判斷隊(duì)列Q是否為空，即判斷Q.front是否等于Q.rear（4）讀取隊(duì)首元素函數(shù)名：PeekQueue

形參：順序隊(duì)列Q

返回值：隊(duì)首元素的值功能：若隊(duì)非空，則返回隊(duì)首元素的值。因?yàn)閒ront指向隊(duì)首元素前一個(gè)的位置，所以隊(duì)首元素的下標(biāo)位置為：(Q.front+1)%MaxSize2.順序隊(duì)列的操作實(shí)現(xiàn)（5）元素進(jìn)隊(duì)函數(shù)名：EnQueue

形參：順序隊(duì)列Q，待進(jìn)隊(duì)元素item

返回值：無功能：若隊(duì)列未滿，先令隊(duì)尾指針加1，即令Q.rear=(Q.rear+1)%MaxSize，然后賦item的值到新的隊(duì)尾。（6）元素出隊(duì)函數(shù)名：OutQueue

形參：順序隊(duì)列Q

返回值：隊(duì)頭元素功能：若隊(duì)列未空，先令隊(duì)頭指針加1，即令Q.front=(Q.front+1)%MaxSize，然后返回原隊(duì)頭元素。4.7.4隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)回顧單鏈表、鏈棧的結(jié)點(diǎn)結(jié)構(gòu)，思考：鏈隊(duì)中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)是怎樣的？回顧單鏈表、鏈棧的表示，思考：鏈隊(duì)?wèi)?yīng)當(dāng)如何表示？1．鏈隊(duì)的表示用單鏈表表示的隊(duì)列簡(jiǎn)稱為鏈隊(duì)。單鏈表的表頭作為隊(duì)頭，表尾作為隊(duì)尾。故表頭作刪除操作，表尾作插入操作。鏈隊(duì)中每個(gè)結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表、鏈棧中的結(jié)點(diǎn)完全相同，為L(zhǎng)Node結(jié)構(gòu)類型，包括一個(gè)值域和一個(gè)指針域。在一個(gè)鏈隊(duì)中，需設(shè)定兩個(gè)指針分別指向隊(duì)頭和隊(duì)尾。隊(duì)首指針front指向隊(duì)首結(jié)點(diǎn)（即表頭結(jié)點(diǎn)）；隊(duì)尾指針rear指向隊(duì)尾結(jié)點(diǎn)（即表尾結(jié)點(diǎn)）。鏈隊(duì)用C或C++可表示為：

structLinkQueue{LNode*front;//隊(duì)首指針

LNode*rear;//隊(duì)尾指針};

鏈隊(duì)示意圖∧frontrearArearfront∧…BCHA顯然，隊(duì)空時(shí)，front=rear=NULL鏈隊(duì)不存在隊(duì)滿的問題，也不需要循環(huán)。4.7.4隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和操作實(shí)現(xiàn)2.鏈隊(duì)的操作實(shí)現(xiàn)（1）初始化隊(duì)函數(shù)名：InitQueue

形參：鏈隊(duì)HQ

返回值：無功能：置鏈隊(duì)為空，即令HQ.front＝HQ.rear＝NULL（2）清空隊(duì)函數(shù)名：ClearQueue

形參：鏈隊(duì)HQ

返回值：無功能：從隊(duì)首（即表頭）開始，依次刪除各結(jié)點(diǎn)，并回收每個(gè)結(jié)點(diǎn)所占的空間，直至隊(duì)尾。最后置鏈隊(duì)為空。

2.鏈隊(duì)的操作實(shí)現(xiàn)（3）判別隊(duì)空函數(shù)名：EmptyQueue

形參：鏈隊(duì)HQ

返回值：若鏈隊(duì)為空返回true，否則返回false

功能：判斷鏈隊(duì)是否為空，即判斷隊(duì)首指針HQ.front或隊(duì)尾指針HQ.rear是否為NULL。這兩個(gè)指針任何一個(gè)為空時(shí)，另一個(gè)必定也為空。（4）讀取隊(duì)首元素函數(shù)名：PeekQueue

形參：鏈隊(duì)HQ

返回值：隊(duì)首元素的值功能：若鏈隊(duì)非空，則返回隊(duì)首元素的值，即隊(duì)首指針?biāo)赶蚪Y(jié)點(diǎn)的data值。2.鏈隊(duì)的操作實(shí)現(xiàn)（5）元素進(jìn)隊(duì)函數(shù)名：EnQueue

形參：鏈隊(duì)HQ，待進(jìn)隊(duì)元素item

返回值：無功能：把新元素item插入到隊(duì)尾，即單鏈表的表尾。分兩步：1)為新元素分配內(nèi)存空間；

2)把新元素插入到隊(duì)尾：若原鏈隊(duì)為空，則插入后只有一個(gè)結(jié)點(diǎn)，隊(duì)首和隊(duì)尾指針都指向該點(diǎn)，即HQ.front=HQ.rear=newptr;若原鏈隊(duì)非空，則修改隊(duì)尾指針。先將新結(jié)點(diǎn)插入到隊(duì)尾：HQ.rear->next=newptr;然后修改得到新的隊(duì)尾指針：HQ.rear=newptr;2.鏈隊(duì)的操作實(shí)現(xiàn)（6）元素出隊(duì)函數(shù)名：OutQueue

形參：鏈隊(duì)HQ

返回值：隊(duì)首元素功能：若鏈隊(duì)非空，先取出隊(duì)首元素和隊(duì)首指針暫存，然后修改隊(duì)首指針，刪除鏈隊(duì)的隊(duì)首結(jié)點(diǎn)。刪除分兩步：

1)修改隊(duì)首指針：HQ.front=HQ.front->next;

若新的HQ.front等于NULL，表示隊(duì)空，則HQ.rear也需為空，令其也等于NULL。

2)回收原隊(duì)首結(jié)點(diǎn)所占的空間，用delete語句。

編程任務(wù)——簡(jiǎn)單編譯器

（括號(hào)配對(duì)檢查）問題描述：在程序調(diào)試時(shí)都有對(duì)源代碼編譯的過程，而判斷左右括號(hào)是否匹配也是其中的一個(gè)重要環(huán)節(jié)。設(shè)計(jì)程序?qū)θ我廨斎氲谋磉_(dá)式進(jìn)行檢查，判斷左右括號(hào)是否配對(duì)。基本要求：

利用棧來實(shí)現(xiàn)算法。以圓括號(hào)為例來判斷輸入的表達(dá)式中左右括號(hào)是否匹配。編程任務(wù)——簡(jiǎn)單編譯器

（括號(hào)配對(duì)檢查）算法基本思想：由鍵盤輸入一個(gè)表達(dá)式保存在一個(gè)字符數(shù)組中。

依次讀取數(shù)組中每個(gè)字符，若遇到’(‘，則將其進(jìn)棧；若遇到’)’，則出棧一個(gè)元素。當(dāng)所有字符都讀取完后，再根據(jù)棧是否空進(jìn)行判斷。

思考：出棧（Pop算法）時(shí)，當(dāng)top==-1時(shí)，將提示棧空，并exit(1)退出整個(gè)程序。那么如何正確判斷形如x*(y+z)))的表達(dá)式？編程任務(wù)——排隊(duì)看病系統(tǒng)要求實(shí)現(xiàn)的功能：病人到達(dá)，交病歷卡，取號(hào)入隊(duì)叫到號(hào)時(shí)，取出病歷，患者就診不接受新病人，已排隊(duì)病人依次就診以上三種情況用輸入命令來模擬：命令“A”：病人到達(dá)命令“N”：護(hù)士讓下一位病人就診命令“Q”：剩余病人依次就診，然后結(jié)束本章小結(jié)

本章主要介紹了如下一些基本概念：棧：是一種操作受限的線性表。其限制是：只允許在一端進(jìn)行插入和刪除。只允許進(jìn)行插入和刪除的這一端稱為棧頂（top），另一端稱為棧底(bottom)。棧也被稱為“后進(jìn)先出”的線性表。棧的順序存儲(chǔ)結(jié)構(gòu)：利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)母鲾?shù)據(jù)元素，稱為棧的順序存儲(chǔ)結(jié)構(gòu)。棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元（可以是不連續(xù)的）存儲(chǔ)棧中的數(shù)據(jù)元素，這種結(jié)構(gòu)的棧簡(jiǎn)稱為鏈棧。在一個(gè)鏈棧中，棧底就是鏈表的最后一個(gè)結(jié)點(diǎn)，而棧頂總是鏈表的第一個(gè)結(jié)點(diǎn)。隊(duì)列：也是一種操作受限的線性表。其限制是：只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除。只允許進(jìn)行插入的一端稱為隊(duì)尾（rear），只允許進(jìn)行刪除的一端稱為隊(duì)頭(front)。隊(duì)列也被稱為“先進(jìn)先出”表。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)：利用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的數(shù)據(jù)元素，稱為隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)。隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)就是用一組任意的存儲(chǔ)單元（可以是不連續(xù)的）存儲(chǔ)隊(duì)列中的數(shù)據(jù)元素，這種結(jié)構(gòu)的隊(duì)列稱為鏈隊(duì)。在一個(gè)鏈隊(duì)中需設(shè)定兩個(gè)指針(隊(duì)首指針和隊(duì)尾指針)分別指向隊(duì)頭和隊(duì)尾。除上述基本概念以外，還應(yīng)該掌握：棧的基本操作（初始化、棧的空判斷、入棧、出棧、取棧頂元素、置棧空），這些操作的時(shí)間和空間復(fù)雜度均為O(1)。隊(duì)列的基本操作（初始化、隊(duì)列空判斷、入隊(duì)、出隊(duì)、取隊(duì)頭元素），這些操作的時(shí)間和空間復(fù)雜度均為O(1)。應(yīng)該掌握：棧的順序存儲(chǔ)結(jié)構(gòu)的表示棧的鏈接存儲(chǔ)結(jié)構(gòu)的表示隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)順序棧（入棧操作、出棧操作）鏈棧（入棧操作、出棧操作）順序隊(duì)列（入隊(duì)操作、出隊(duì)操作）鏈隊(duì)（入隊(duì)操作、出隊(duì)操作）棧應(yīng)用之一——算術(shù)表達(dá)式的計(jì)算GO

GO

GO

GO

測(cè)試題：假定利用數(shù)組a[N]順序存儲(chǔ)一個(gè)棧，用top表示棧頂指針，top==-1表示棧空，并已知棧未空，當(dāng)退棧并返回棧頂元素時(shí)所執(zhí)行的操作為________________。在一個(gè)鏈棧中，若棧頂指針等于NULL則為______________；在一個(gè)鏈隊(duì)中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)為______________或該隊(duì)______________。從一個(gè)順序循環(huán)隊(duì)列中刪除元素時(shí)，首先需要___________。假定利用數(shù)組a[N]循環(huán)順序存儲(chǔ)一個(gè)隊(duì)列，用f和r分別表示隊(duì)首和隊(duì)尾指針，并已知隊(duì)列未滿，當(dāng)元素x進(jìn)隊(duì)時(shí)所執(zhí)行的操作為_______________________。設(shè)元素1，2，3，4，5依次進(jìn)棧，若要在輸出端得到序列34251，則應(yīng)進(jìn)行的操作序列為push(S,1)，push(S,2)，____