數(shù)據(jù)結(jié)構(gòu)與算法3

第3章棧和隊(duì)列

（4課時(shí)）棧是一種插入和刪除操作都只能在表的同一端進(jìn)行的線性表。允許進(jìn)行插入和刪除操作的一端叫做棧頂(Top)，也稱為表尾；另一端叫做棧底(Bottom)，也稱為表頭。當(dāng)棧中沒(méi)有元素時(shí)稱為空棧。向棧中插入元素的操作稱為進(jìn)?；蛉霔?push)，從棧中刪除元素的操作稱為退?；虺鰲?pop)。3.1棧及其抽象數(shù)據(jù)類(lèi)型3.1棧及其抽象數(shù)據(jù)類(lèi)型3.1.1棧的基本概念3.1.2棧的抽象數(shù)據(jù)類(lèi)型設(shè)棧S=(e1，e2，…，en)，則e1稱為棧底元素，en為棧頂元素，圖3-1是棧的示意圖。棧中元素是以e1，e2，…，en的順序進(jìn)棧，而出棧的順序卻是en,…,e2,e1。也就是說(shuō)棧是按照“先進(jìn)后出”(FILO，F(xiàn)irstInLastOut）或“后進(jìn)先出”(LIFO，LastInFirstOut）的原則組織數(shù)據(jù)的。所以，棧也被稱為后進(jìn)先出LIFO、先進(jìn)后出FILO線性表或下推表。3.1棧及其抽象數(shù)據(jù)類(lèi)型3.1.1棧的基本概念圖3-1棧的示意圖創(chuàng)建一個(gè)空棧刪除一個(gè)棧判斷棧是否為空判斷棧是否為滿棧頂插入一個(gè)元素求棧頂元素的值刪除棧頂?shù)囊粋€(gè)元素輸出棧3.1棧及其抽象數(shù)據(jù)類(lèi)型棧一般需要進(jìn)行下面的基本操作棧的抽象數(shù)據(jù)類(lèi)型Stack定義如下：ADTStack{數(shù)據(jù)對(duì)象D={ei|ei∈T,i=1,2,…,n，n≥0}數(shù)據(jù)關(guān)系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)：從棧頂刪除一個(gè)元素，并將該元素的值放入x中 voidOutPut()：輸出棧}ADTStack3.1棧及其抽象數(shù)據(jù)類(lèi)型3.1.2棧的抽象數(shù)據(jù)類(lèi)型3.2棧的表示及實(shí)現(xiàn)棧是一種線性表，因此，將線性表的順序和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)應(yīng)用于棧時(shí)，就建立了順序棧和鏈?zhǔn)綏?。下面分別介紹棧的順序表示及實(shí)現(xiàn)和鏈?zhǔn)奖硎炯皩?shí)現(xiàn)，以及棧的簡(jiǎn)單應(yīng)用。3.2棧的表示及實(shí)現(xiàn)3.2.1棧的順序表示及實(shí)現(xiàn)3.2.3棧的鏈?zhǔn)奖硎炯皩?shí)現(xiàn)3.2.2順序棧代碼復(fù)用實(shí)例3.2棧的表示及實(shí)現(xiàn)采用順序存儲(chǔ)結(jié)構(gòu)表示的棧稱為順序棧。順序棧需要分配一塊連續(xù)的存儲(chǔ)區(qū)域來(lái)存放棧中的元素。順序?？梢杂靡痪S數(shù)組實(shí)現(xiàn)。因?yàn)闂５孜恢檬枪潭ú蛔兊?，所以可把棧底設(shè)置在一維數(shù)組的任意一端。棧頂位置隨著進(jìn)棧和出棧操作不斷變化，因此用一個(gè)變量來(lái)指示當(dāng)前棧頂位置。3.2.1棧的順序表示及實(shí)現(xiàn)3.2棧的表示及實(shí)現(xiàn)由于一個(gè)?？赡苡衝個(gè)數(shù)據(jù)元素，也可能是空棧。所以，在順序棧類(lèi)模板的數(shù)據(jù)成員中，除了用來(lái)實(shí)現(xiàn)順序棧的動(dòng)態(tài)數(shù)組element，還有兩個(gè)int型數(shù)據(jù)成員MaxSize和top。MaxSize用來(lái)標(biāo)識(shí)棧的最大長(zhǎng)度，top用來(lái)標(biāo)識(shí)當(dāng)前順序棧的棧頂。順序棧的Create創(chuàng)建操作和Destroy刪除操作，使用的是類(lèi)的構(gòu)造函數(shù)和析構(gòu)函數(shù)來(lái)實(shí)現(xiàn)的。使用構(gòu)造函數(shù)LinearStack(intLSMaxSize)創(chuàng)建一個(gè)空棧時(shí)，首先根據(jù)參數(shù)LSMaxSize，為棧申請(qǐng)一個(gè)用指針element指向的長(zhǎng)度為L(zhǎng)SMaxSize*sizeof(T)個(gè)字節(jié)的連續(xù)空間，然后將棧頂top賦值為-1，表示空棧。析構(gòu)函數(shù)~LinearStack()負(fù)責(zé)回收申請(qǐng)的棧空間。3.2.1棧的順序表示及實(shí)現(xiàn)3.2棧的表示及實(shí)現(xiàn)假設(shè)一個(gè)空的順序棧，元素A、B、C、D、E、F依次進(jìn)棧；然后元素再出棧，則該順序棧的進(jìn)棧和出棧動(dòng)態(tài)變化如圖3-2所示。(a)空棧(b)插入元素A后(c)插入元素B、C、D、E、F后(d)兩個(gè)元素出棧后(e)所有元素出棧后圖3-2順序棧的動(dòng)態(tài)變化示意圖3.2.1棧的順序表示及實(shí)現(xiàn)3.2棧的表示及實(shí)現(xiàn)當(dāng)棧中已有MaxSize個(gè)元素時(shí)，如果再進(jìn)行進(jìn)棧操作，則會(huì)產(chǎn)生溢出，此時(shí)稱為上溢（Overflow）；而對(duì)空棧進(jìn)行出棧操作時(shí)也會(huì)產(chǎn)生溢出，此時(shí)稱為下溢（Underflow）。因此，在進(jìn)行進(jìn)?；虺鰲２僮鲿r(shí)，應(yīng)首先檢查棧是否為滿(IsFull)或是否為空(IsEmpty)。 IsEmpty()的算法是：

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

returntop==MaxSize;

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

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

returnfalse;else{

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

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

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

ADTQueue{

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

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

基本操作P：

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

Destroy()：刪除隊(duì)列

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

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

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

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