數(shù)據(jù)結構課件隊列

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

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

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

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

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

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

形參：順序隊列Q

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

形參：順序隊列Q

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

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

形參：順序隊列Q

返回值：若隊空返回true，否則返回false

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

形參：順序隊列Q

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

形參：順序隊列Q，待進隊元素item

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

形參：順序隊列Q

返回值：隊頭元素功能：若隊列未空，先令隊頭指針加1，即令Q.front=(Q.front+1)%MaxSize，然后返回原隊頭元素。4.7.4隊列的鏈式存儲結構和操作實現(xiàn)回顧單鏈表、鏈棧的結點結構，思考：鏈隊中每個結點的結構是怎樣的？回顧單鏈表、鏈棧的表示，思考：鏈隊應當如何表示？1．鏈隊的表示用單鏈表表示的隊列簡稱為鏈隊。單鏈表的表頭作為隊頭，表尾作為隊尾。故表頭作刪除操作，表尾作插入操作。鏈隊中每個結點的結構與單鏈表、鏈棧中的結點完全相同，為LNode結構類型，包括一個值域和一個指針域。在一個鏈隊中，需設定兩個指針分別指向隊頭和隊尾。隊首指針front指向隊首結點（即表頭結點）；隊尾指針rear指向隊尾結點（即表尾結點）。鏈隊用C或C++可表示為：

structLinkQueue{LNode*front;//隊首指針

LNode*rear;//隊尾指針};

鏈隊示意圖∧frontrearArearfront∧…BCHA顯然，隊空時，front=rear=NULL鏈隊不存在隊滿的問題，也不需要循環(huán)。4.7.4隊列的鏈式存儲結構和操作實現(xiàn)2.鏈隊的操作實現(xiàn)（1）初始化隊函數(shù)名：InitQueue

形參：鏈隊HQ

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

形參：鏈隊HQ

返回值：無功能：從隊首（即表頭）開始，依次刪除各結點，并回收每個結點所占的空間，直至隊尾。最后置鏈隊為空。

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

形參：鏈隊HQ

返回值：若鏈隊為空返回true，否則返回false

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

形參：鏈隊HQ

返回值：隊首元素的值功能：若鏈隊非空，則返回隊首元素的值，即隊首指針所指向結點的data值。2.鏈隊的操作實現(xiàn)（5）元素進隊函數(shù)名：EnQueue

形參：鏈隊HQ，待進隊元素item

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

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

形參：鏈隊HQ

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

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

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

2)回收原隊首結點所占的空間，用delete語句。

編程任務——簡單編譯器

（括號配對檢查）問題描述：在程序調(diào)試時都有對源代碼編譯的過程，而判斷左右括號是否匹配也是其中的一個重要環(huán)節(jié)。設計程序對任意輸入的表達式進行檢查，判斷左右括號是否配對?；疽螅?/p>

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

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

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

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

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

GO

GO

GO

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