數(shù)據(jù)結構與算法3

第3章棧和隊列

（4課時）棧是一種插入和刪除操作都只能在表的同一端進行的線性表。允許進行插入和刪除操作的一端叫做棧頂(Top)，也稱為表尾；另一端叫做棧底(Bottom)，也稱為表頭。當棧中沒有元素時稱為空棧。向棧中插入元素的操作稱為進棧或入棧(push)，從棧中刪除元素的操作稱為退棧或出棧(pop)。3.1棧及其抽象數(shù)據(jù)類型3.1棧及其抽象數(shù)據(jù)類型3.1.1棧的基本概念3.1.2棧的抽象數(shù)據(jù)類型設棧S=(e1，e2，…，en)，則e1稱為棧底元素，en為棧頂元素，圖3-1是棧的示意圖。棧中元素是以e1，e2，…，en的順序進棧，而出棧的順序卻是en,…,e2,e1。也就是說棧是按照“先進后出”(FILO，F(xiàn)irstInLastOut）或“后進先出”(LIFO，LastInFirstOut）的原則組織數(shù)據(jù)的。所以，棧也被稱為后進先出LIFO、先進后出FILO線性表或下推表。3.1棧及其抽象數(shù)據(jù)類型3.1.1棧的基本概念圖3-1棧的示意圖創(chuàng)建一個空棧刪除一個棧判斷棧是否為空判斷棧是否為滿棧頂插入一個元素求棧頂元素的值刪除棧頂?shù)囊粋€元素輸出棧3.1棧及其抽象數(shù)據(jù)類型棧一般需要進行下面的基本操作棧的抽象數(shù)據(jù)類型Stack定義如下：ADTStack{數(shù)據(jù)對象D={ei|ei∈T,i=1,2,…,n，n≥0}數(shù)據(jù)關系R={<ei-1,ei>|ei-1，ei∈T,i=2,3,…,n}基本操作P：

Create()：創(chuàng)建空棧

Destroy()：刪除棧boolIsEmpty()：判斷棧是否為空，空返回true，非空返回false boolIsFull()：判斷棧是否為滿，滿返回true，不滿返回false boolPush(constT&x)：在棧頂插入元素x，返回插入后的棧

boolTop(T&x)： 求棧頂元素的值放入x中boolPop(T&x)：從棧頂刪除一個元素，并將該元素的值放入x中 voidOutPut()：輸出棧}ADTStack3.1棧及其抽象數(shù)據(jù)類型3.1.2棧的抽象數(shù)據(jù)類型3.2棧的表示及實現(xiàn)棧是一種線性表，因此，將線性表的順序和鏈式存儲結構應用于棧時，就建立了順序棧和鏈式棧。下面分別介紹棧的順序表示及實現(xiàn)和鏈式表示及實現(xiàn)，以及棧的簡單應用。3.2棧的表示及實現(xiàn)3.2.1棧的順序表示及實現(xiàn)3.2.3棧的鏈式表示及實現(xiàn)3.2.2順序棧代碼復用實例3.2棧的表示及實現(xiàn)采用順序存儲結構表示的棧稱為順序棧。順序棧需要分配一塊連續(xù)的存儲區(qū)域來存放棧中的元素。順序棧可以用一維數(shù)組實現(xiàn)。因為棧底位置是固定不變的，所以可把棧底設置在一維數(shù)組的任意一端。棧頂位置隨著進棧和出棧操作不斷變化，因此用一個變量來指示當前棧頂位置。3.2.1棧的順序表示及實現(xiàn)3.2棧的表示及實現(xiàn)由于一個?？赡苡衝個數(shù)據(jù)元素，也可能是空棧。所以，在順序棧類模板的數(shù)據(jù)成員中，除了用來實現(xiàn)順序棧的動態(tài)數(shù)組element，還有兩個int型數(shù)據(jù)成員MaxSize和top。MaxSize用來標識棧的最大長度，top用來標識當前順序棧的棧頂。順序棧的Create創(chuàng)建操作和Destroy刪除操作，使用的是類的構造函數(shù)和析構函數(shù)來實現(xiàn)的。使用構造函數(shù)LinearStack(intLSMaxSize)創(chuàng)建一個空棧時，首先根據(jù)參數(shù)LSMaxSize，為棧申請一個用指針element指向的長度為LSMaxSize*sizeof(T)個字節(jié)的連續(xù)空間，然后將棧頂top賦值為-1，表示空棧。析構函數(shù)~LinearStack()負責回收申請的棧空間。3.2.1棧的順序表示及實現(xiàn)3.2棧的表示及實現(xiàn)假設一個空的順序棧，元素A、B、C、D、E、F依次進棧；然后元素再出棧，則該順序棧的進棧和出棧動態(tài)變化如圖3-2所示。(a)空棧(b)插入元素A后(c)插入元素B、C、D、E、F后(d)兩個元素出棧后(e)所有元素出棧后圖3-2順序棧的動態(tài)變化示意圖3.2.1棧的順序表示及實現(xiàn)3.2棧的表示及實現(xiàn)當棧中已有MaxSize個元素時，如果再進行進棧操作，則會產(chǎn)生溢出，此時稱為上溢（Overflow）；而對空棧進行出棧操作時也會產(chǎn)生溢出，此時稱為下溢（Underflow）。因此，在進行進?；虺鰲２僮鲿r，應首先檢查棧是否為滿(IsFull)或是否為空(IsEmpty)。 IsEmpty()的算法是：

returntop==-1; IsFull()的算法是：

returntop==MaxSize;

實現(xiàn)求棧中元素的個數(shù)GetElementNumber()的算法是：

returntop+1;3.2.1棧的順序表示及實現(xiàn)3.2棧的表示及實現(xiàn)進棧操作Push(constT&x)是向棧頂插入一個值為x的元素，進棧操作算法是： if(IsFull()) returnfalse; else { top++; element[top]=x; returntrue; }3.2.1棧的順序表示及實現(xiàn)3.2棧的表示及實現(xiàn)出棧操作Pop(T&x)是將棧頂元素放到x中，然后，棧頂下移。出棧操作算法是：if(IsEmpty())

returnfalse;else{

x=element[top]; top--; returntrue;}上述算法都是在棧頂進行的，因此算法的復雜度為O(1)。3.2.1棧的順序表示及實現(xiàn)3.2棧的表示及實現(xiàn)【例3-1】將十進制數(shù)轉換為其他各種進制（如2、8、16）數(shù)。分析：將一個給定的十進制數(shù)n轉化成基數(shù)為base的進制數(shù)，可以采用“除基取余法”。由于該方法最早除得的余數(shù)最后使用，所以可以使用棧。將每一次除得的余數(shù)進棧，等到所有除法結束后，再將棧中元素依次出棧即可得到轉換后的結果。下面只需要基于LinearStack類模板生成數(shù)據(jù)類型為int類的模板類對象，就可以直接使用類中提供的相應成員函數(shù)解決問題了。3.2.2順序棧代碼復用實例把棧組織成一個單鏈表，即采用鏈接結構來表示棧，這樣的數(shù)據(jù)結構稱為鏈接棧。圖3-3鏈接棧示意圖棧的鏈式存儲結構一般是通過單鏈表來實現(xiàn)的。在單鏈表中，每一個結點表示棧中的一個元素。由于棧是在鏈表頭部進行插入和刪除操作，故鏈接棧不需要再設置表頭結點。棧頂指針top就是鏈接棧的頭指針，它可以唯一地確定一個棧。假設元素e1,e2,...,en依次進棧，則圖3-3是該鏈接棧的示意圖。3.2棧的表示及實現(xiàn)3.2.3棧的鏈式表示及實現(xiàn)圖3-3鏈接棧示意圖由于鏈接棧具有動態(tài)分配元素結點的特點，所以，在內(nèi)存足夠大的情況下，可以認為鏈接棧中最大元素的個數(shù)沒有限制。因此在下面的單向鏈接棧類模板描述中去掉了判斷棧滿的操作IsFull。其他基本操作與前面的順序棧基本操作的含義完全相同。下面將鏈接棧存儲結點的類模板命名為LinkNode，將單向鏈接棧的類模板命名為LinkStack。3.2棧的表示及實現(xiàn)3.2.3棧的鏈式表示及實現(xiàn)在對鏈接棧的基本操作中，使用較多的是進棧和出棧操作。進棧Push就是向鏈接棧的棧頂插入一個元素結點，先將待進棧結點的指針域指向原來的棧頂結點，然后將棧頂指針top修指向該結點，使進棧元素結點成為新的棧頂結點。出棧Pop就是從鏈接棧的棧頂刪除一個元素結點，先將棧頂元素取出放到x中，然后使棧頂指針top指向原棧頂結點的后繼結點，然后物理上刪除該結點。當top為空時，鏈接棧為空。刪除鏈接棧時使用析構函數(shù)~LinkStack來完成，~LinkStack的工作是將所有元素出棧。3.2棧的表示及實現(xiàn)3.2.3棧的鏈式表示及實現(xiàn)3.3隊列及其抽象數(shù)據(jù)類型3.3.1隊列的基本概念3.3.2隊列的抽象數(shù)據(jù)類型排隊是日常生活中最常見的現(xiàn)象，在車站買票、在銀行辦理業(yè)務等許多場合都需要排隊。排隊的特點是新來的人要站在在隊尾，而隊首的人先離開。這種“先來先服務”的辦事方式就可以抽象成隊列這種數(shù)據(jù)結構。隊列是一種只允許在表的一端進行插入操作，而在表的另一端進行刪除操作的線性表。隊列的插入操作也成為入隊，允許入隊的一端稱為隊尾（rear）；隊列的刪除操作也稱為出隊，允許出隊的一端稱為隊頭（front）。不含元素的隊列稱為空隊列。因此，隊列又稱為“先進先出”（FIFO，F(xiàn)irstInFirstOut）或“后進后出”（LILO，LastInLastOut）線性表。3.3隊列及其抽象數(shù)據(jù)類型3.3.1隊列的基本概念3.3隊列及其抽象數(shù)據(jù)類型3.3.1隊列的基本概念設隊列Q=(e1，e2，…，en)，隊列中的元素是按e1、e2、e3、…、en

的順序進入隊列，則e1為隊頭元素，en為隊尾元素。圖3-4是隊列的示意圖。在元素退出隊列時，只能按e1、e2、e3、…、en

的順序進行。圖3-4隊列的示意圖3.3隊列及其抽象數(shù)據(jù)類型隊列一般需要進行下面的基本操作：創(chuàng)建一個隊列刪除一個隊列判斷隊列是否為空判斷隊列是否為滿在隊尾插入一個元素取隊頭元素的值隊頭元素出隊輸出隊列3.3.1隊列的基本概念3.3隊列及其抽象數(shù)據(jù)類型根據(jù)3.3.1節(jié)對隊列及其基本操作的抽象，抽象數(shù)據(jù)類型中的元素類型用T來表示，則隊列的抽象數(shù)據(jù)類型Queue定義如下：

ADTQueue{

數(shù)據(jù)對象D={ei|ei∈T,i=1,2,…,n，n≥0}

數(shù)據(jù)關系R={<ei-1,ei>|ei-1，ei∈D,i=2,3,…,n}

基本操作P：

Create()：創(chuàng)建空隊列

Destroy()：刪除隊列

boolIsEmpty()：判斷隊列是否為空，空返回true，非空返回false boolIsFull()： 判斷隊列是否為滿，滿返回true，不滿返回false boolInsert(constT&x)：入隊，在隊列尾部插入元素x boolGetElement(T&x)：取隊頭元素的值放入x中

boolDelete(T&x)： 出隊，從隊頭刪除一個元素，并將該元素的值放入x中

voidOutPut()：輸出隊列 }ADTQueue3.3.2隊列的抽象數(shù)據(jù)類型3.4隊列的表示及實現(xiàn)隊列的表示與棧和一般線性表一樣，通常也可以采用順序表示和鏈式表示。本節(jié)分別介紹隊列的順序表示及實現(xiàn)和鏈式表示及實現(xiàn)的方法。3.4隊列的表示及實現(xiàn)3.4.1隊列的順序表示及實現(xiàn)3.4.2隊列的鏈式表示及實現(xiàn)3.4隊列的表示及實現(xiàn)采用順序存儲結構的隊列也稱為順序隊列。順序隊列通常用一個一維數(shù)組來存放隊列中的數(shù)據(jù)元素。此外，還需設置兩個整型變量front和rear，分別指示隊頭和隊尾，稱為頭指針和尾指針。為了運算的方便，在此約定，在非空隊列里，front始終指向隊頭元素，而rear始終指向隊尾元素的下一位置。初始化隊列時，front和rear均置為0。隊列元素的入隊和出隊操作是最基本的操作。順序隊列入隊時，將新元素插入到rear所指位置后，再將rear的值加1；順序隊列出隊時，刪除front所指位置的元素后，再將front的值加1并返回被刪元素?？梢?，隊列為空的條件是：front==rear3.4.1隊列的順序表示及實現(xiàn)3.4隊列的表示及實現(xiàn)3.4.1隊列的順序表示及實現(xiàn)圖3-5隊列變化示意圖3.4隊列的表示及實現(xiàn)在順序隊列中，同順序棧一樣，也存在隊列溢出的問題。當隊列滿時，再做入隊操作，這種現(xiàn)象稱為“上溢”。如在圖3-5(c)所示狀態(tài)下，再做入隊操作，就會產(chǎn)生“上溢”。當隊列空時，再做出隊操作，這種現(xiàn)象稱為“下溢”。如在圖3-5(e)所示狀態(tài)下，再做出隊操作，就會產(chǎn)生“下溢”。由于隊列經(jīng)常要做插入或刪除操作，front和rear會隨著插入或刪除操作進行變化。在圖3-5(d)所示狀態(tài)下，如果還有新元素請求入隊時，雖然隊列的實際可用空間沒有占滿，但由于尾指針已超越存儲空間的上界，也不能做入隊操作，這種現(xiàn)象稱為“假上溢”。3.4.1隊列的順序表示及實現(xiàn)3.4隊列的表示及實現(xiàn)為避免發(fā)生順序隊列的“假上溢”現(xiàn)象，充分利用隊列的存儲空間，可以將隊列將順序隊列存儲空間的最后一個位置和第一個位置邏輯上連接在一起。這樣的隊列稱“循環(huán)隊列”。假設當前循環(huán)隊列最多能容納MaxSize個元素，邏輯上的循環(huán)是通過頭、尾指針的加1操作實現(xiàn)的： front=(front+1)%(MaxSize-1） rear=(rear+1)%(MaxSize-1)在循環(huán)隊列中進行入隊、出隊操作時，頭、尾指針仍然加1，但當頭或尾指針已經(jīng)指向了存儲空間的上界時，通過上面邏輯上的循環(huán)方法，再加1的操作結果是指向下界0。3.4.1隊列的順序表示及實現(xiàn)3.4隊列的表示及實現(xiàn)3.4.1隊列的順序表示及實現(xiàn)圖3-6是對圖3-5中的隊列采用循環(huán)隊列后的示意圖。3.4隊列的表示及實現(xiàn)在圖3-6（d）狀態(tài)時，如果還有新元素請求入隊時，由于rear循環(huán)指向了0，所以能夠進行入隊操作，解決了“假上溢”的問題。但是，在隊列滿的3-5（c）狀態(tài)和隊列空的3-6(a)或3-6（e）狀態(tài)，都有相同的front==rear關系。因此，在循環(huán)隊列中，僅依據(jù)頭尾指針相等是無法判斷隊列是“空”還是“滿”。要解決判斷循環(huán)隊列是空還是滿的問題，可以采用兩種方法：（1）約定少用一個元素空間。入隊前，如果關系“(rear+1)%(MaxSize-1)==front”存在，就認為隊列已滿，再要插入就會發(fā)生溢出?？梢?，這種方法rear始終指向那個空閑的元素空間。（2）使用一個計數(shù)器size記錄當前隊列的實際長度。如果size=0，則當“front==rear”時，當前隊列是空隊列，可以進行入隊操作；否則，當前隊列滿，不能進行入隊操作。3.4.1隊列的順序表示及實現(xiàn)【例3-2】在屏幕上顯示楊輝三角。楊輝三角的特點是第n行有n個數(shù)，除了第一個數(shù)和最后一個數(shù)是1外，其他數(shù)是上一行中位其左右的兩個數(shù)之和。如圖3-7所示的是6行楊輝三角的情況。圖3-7楊輝三角分析：根據(jù)第i行和第i+1行的變換規(guī)律，可以用循環(huán)隊列來完成楊輝三角的顯示任務。具體方法將第1行的1入隊，然后循環(huán)進行如下操作：在輸出第i行時，計算第i+1行的數(shù)據(jù)并將他們依次入隊。為了便于計算，將隊列的最大容量設置為n+2，在相鄰的兩行元素之間加一標識‘0’來區(qū)別不同行的隊列元素。通過不斷地入隊和出隊，來完成楊輝三角的輸出。下面基于LinearStack類模板生成數(shù)據(jù)類型為int類的模板類對象，直接使用類中的相應成員函數(shù)解決這個問題。3.4隊列的表示及實現(xiàn)3.4.1隊列的順序表示及實現(xiàn)隊列的鏈式存儲結構是僅在表頭刪除結點和在表尾插入結點的單鏈表，也為鏈接隊列。因為需要在表頭進行刪除操作和在表尾進行插入操作，所以在鏈接隊列中，需要增加指向隊頭和隊尾的兩個指針front和rear。這樣，一個鏈接隊列就由一個頭指針front和一個尾指針rear唯一地確定了。圖3-8是存儲了n個元素的鏈接隊列的示意圖。3.4隊列的表示及實現(xiàn)3.4.2隊列的鏈式表示及實現(xiàn)圖3-8鏈接隊列示意圖3.5應用實例棧的實際應用相當廣泛，例如，除數(shù)制的轉換外，棧還可用于解決括號匹配檢查、行編輯處理和表達式求解、走迷宮，以及高級語言中函數(shù)的嵌套調(diào)用和遞歸的實現(xiàn)等問題。隊列在日常生活中應用也很多，特別是在計算機科學領域中所起的作用很大，例如，操作系統(tǒng)中各種資源請求排隊和各種緩沖區(qū)的先進先出管理，各種應用系統(tǒng)中的事件規(guī)劃和事件模擬，樹的層次遍歷和圖的廣度優(yōu)先遍歷等，都使用了隊列這樣的數(shù)據(jù)結構。3.5應用實例3.5.1棧的應用實例3.5.2隊列的應用實例【例3-3】計算機的編譯程序需要檢查一個表達式中括號是否匹配問題。如在C++語言中，表達式中允許使用兩種括號：圓括號和方括號。設計一種對C++語言的表達式中的括號是否匹配進行檢驗的算法。求解思路：括號匹配的處理過程與棧的特點相吻合，可以用棧來實現(xiàn)。具體算法是：從左向右掃描表達式，并設置一個棧，若是左括號則壓入棧中；若是右括號，如果它能與當前棧頂元素相匹配，則刪除棧頂元素，繼續(xù)下一次掃描，如果不能與棧頂元素匹配，則認為當前表達式括號匹配不正確而返回。下面采用鏈接棧來實現(xiàn)“檢查括號是否匹配”的問題，假設一個表達式的結束符為‘#’。3.5應用實例3.5.1棧的應用實例下面舉一個用隊列來解決的生活中常見的日程安排問題。【例3-4】運動會日程安排問題。設計一個算法，使運動會的日程最短，同時保證每個運動員參加的不同項目在時間安排上不會出現(xiàn)沖突。3.5應用實例3.5.2隊列的應用實例圖3-9項目時間沖突矩陣分析：問題實質是將項目分成幾個組，使參加每組中項目的運動員在時間上不會發(fā)生沖突；為了使運動會的日程最短，劃分的項目組數(shù)要最少。運動員項目在時間上的沖突關系可以用一個矩陣R來表示出來，如圖3-9所示。假設一名運動員報名參加項目1和項目3，則表示這兩個項目在時間上沖突，在圖3-9中的矩陣R的元素r1,3或r3,1的值就是1。如果沒有任何運動員同時參加項目1和項目3，則矩陣R的元素r1,3或r3,1的值就是0。3.5應用實例3.5.2隊列的應用實例具體實現(xiàn)方法：假設有n個項目，用一個二維數(shù)組R存放項目的沖突關系矩陣，用隊列Q來存放待分組的項目編號，初始時為0，1，2,…,n-1。用Group[]存放當前劃分到同一組的項目號，數(shù)組元素初始值都為0。用一維數(shù)組Result[n]來存放項目被劃分的組號，數(shù)組元素初始值都為0，如果項目i被劃分到第j組，則Result[i]=j。具體算法是采用循環(huán)篩選法,從第1個項目開始，凡與第1個項目無沖突的項目劃歸為一組，然后，在剩下的項目中進行類似操作劃分出第二組，依此類推，直到所有的項目都被劃分進組。3.5.2隊列的應用實例3.5應用實例針對圖3-9的運動會項目安排問題，程序的運行結果如下：

請輸入運動會項目數(shù)：4請輸入運動員時間沖突矩陣：0100，1010，0101，0010第1組同時比賽的項目包括：1號項目3號項目第2組同時比賽的項目包括：2號項目4號項目提示：這個問題的本質是一個無沖突子集的劃分問題。無沖突子集的劃分問題的形式化描述為：已知集合A={a1，a2，…，an}，對應于A上的關系有R={(ai，aj)|ai，aj∈A，i≠j，i，j=1，2，…，n}，其中ai與aj之間存在沖突關系?，F(xiàn)要求將A劃分成互不相交的子集A1，A2，…，Am(m≤n)，使任何子集上的數(shù)據(jù)元素均無沖突，同時要求劃分出的子集的個數(shù)盡可能少。實際應用中的無沖突子集的劃分問題都可以用上面的算法進行求解。3.5.2隊列的應用實例3.5應用實例本章小結本章主要介紹了棧和隊列的特點和抽象數(shù)據(jù)類型，并給出了實現(xiàn)順序棧、鏈接棧、順序隊列和鏈接隊列完整的C++程序代碼以及如何復用這些代碼解決實際應用問題的實例和方法。通過對本章的學習，讀者應對棧和隊列這兩種被廣泛用于日常生活和計算機領域的數(shù)據(jù)結構有一個全面的認識，掌握棧和隊列的順序結構及其鏈式結構的表示和實現(xiàn)方法，并通過一定的練習，能逐漸熟練地使用教材中的代碼解決實際問題。1．具有什么特征的數(shù)據(jù)結構被稱為棧和隊列？先進后出、棧頂、棧底、先進先出、隊頭、隊尾的概念是什么？2．簡述在順序棧的棧頂插入一個元素的操作過程。3.一個棧的輸入序列為1、2、3，試給出全部可能的出棧序列。4．循環(huán)隊列的優(yōu)點是什么？在循環(huán)隊列中，僅依據(jù)頭尾指針相等，無法判斷隊列是“空”還是“滿”。要解決這個問題，常用的兩種方法是什么？5.簡述在鏈接棧中插入一個元素的操作過程。6．請列舉出一些可以用棧和隊列表示的實際問題。習題3實習目的1.熟悉并掌握棧的定義及特點。2.熟悉并掌握順序棧和鏈接棧的描述方法和基本操作的實現(xiàn)。3.能夠使用棧解決實際應用問題。上機實習實習1棧的操作實習內(nèi)容1.用鏈接棧實現(xiàn)例【例3-1】將十進制數(shù)轉換為其他各種進制（如2、8、16）數(shù)的問題。2.針對【描述3-2】中輸出順序棧的運算是倒序輸出