數(shù)據(jù)結(jié)構(gòu)與算法-第三章-清華大學(xué)出版社-趙玉蘭

第3章棧和隊列3.1棧3.2隊列3.3棧與隊列的應(yīng)用3.1棧——ADT棧棧（Stack）只允許在表的一端進行插入和刪除的線性表允許插入和刪除的一端稱為棧頂（top），另一端稱為棧底（bottom）不含元素的棧稱為空棧插入：進棧，入棧刪除：出棧，退棧特點后進先出（LIFO）先進后出（FILO）3.1棧——ADT棧問題有三個元素按a1,a2,a3的次序依次進棧，其出棧次序有幾種可能？出棧次序：a1，a2，a3

a1，a3，a2

a2，a1，a3

a2，a3，a1

a3，a2，a1注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。3.1棧——ADT棧棧的抽象數(shù)據(jù)類型ADTStack{

Data數(shù)據(jù)項列表top：棧頂位置

OperationsConstructorProcess：創(chuàng)建一個空棧IsEmptyProcess：判斷棧是否為空Output：如果棧為空，則返回true，否則返回falseGetTopProcess：取棧頂元素Output：返回棧頂元素3.1棧——ADT棧LengthProcess：求棧中元素個數(shù)Output：返回棧中元素的個數(shù)PushInput：要添加的數(shù)據(jù)元素Process：向棧中添加元素x，即進棧PopProcess：刪除棧頂元素，即出棧Output：返回棧頂元素ClearProcess：刪除棧中所有元素并置新的棧頂}//Stack3.1棧——棧的實現(xiàn)順序棧順序棧的定義如何改造數(shù)組實現(xiàn)棧的順序存儲？

0123456②附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top①確定用數(shù)組的哪一端表示棧底。a1a2a33.1棧——棧的實現(xiàn)順序棧的基本操作出棧：先出棧top再減1進棧：top先加1再進棧棧空：top==-1

012345678a1topa2topa3top棧滿：top==MaxStackSize-1toptop3.1棧——棧的實現(xiàn)constintMaxStackSize=50;//棧中能容納最大元素個數(shù)classSeqStack{DataTypeStackList[MaxStackSize];inttop;public:Stack();//構(gòu)造函數(shù)，初始化topboolIsEmpty();//判斷棧的狀態(tài)是否為空boolIsFull();DataTypeGetTop();//取棧頂元素voidPush(constDataTypex);//入棧DataTypePop();//出棧voidClear();//棧清空};//SeqStack3.1棧——棧的實現(xiàn)順序棧的操作的實現(xiàn)構(gòu)造函數(shù)，初始化一個空棧Stack(){StackList=newDataType[MaxStackSize];top=-1;}//Stack3.1棧——棧的實現(xiàn)判斷棧是否為空boolIsEmpty(){if(top==-1)returntrue;elsereturnfalse;}//IsEmpty3.1棧——棧的實現(xiàn)判斷棧是否已滿

boolIsFull(){if(top==MaxStackSize-1)returntrue;elsereturnfalse;}//IsFull3.1棧——棧的實現(xiàn)取棧頂元素

DataTypeGetTop(){if(IsEmpty()){cout<<”棧空！”<<endl;returnnulldata;}returnStackList[top];}3.1棧——棧的實現(xiàn)向棧頂壓入元素

voidPush(DataTypex){if(IsFull()){cout<<”棧滿！”<<endl;elseStackList[++top]=x;}//Push3.1棧——棧的實現(xiàn)刪除棧頂元素

DataTypePop(){if(IsEmpty()){cout<<”棧空！”<<endl;returnnulldata;}returnStackList[top--];}//Pop3.1棧——棧的實現(xiàn)清空棧

voidClear(){top=-1;}//Cleartop=-1012341001234壓入10top=0102501234壓入25top=110255001234壓入50top=2102501234彈出50top=11001234彈出25top=0圖3.2出棧和入棧操作以及棧頂?shù)淖兓?.1棧——棧的實現(xiàn)鏈?zhǔn)綏＃↙inkedStack）鏈?zhǔn)綏＃ㄦ湕＃╂準(zhǔn)酱鎯Φ臈Ｓ脝捂湵韥韺崿F(xiàn)鏈棧，因此其結(jié)點結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同鏈?zhǔn)綏o棧滿問題，空間可擴充鏈?zhǔn)綏５臈ｍ斣阪滎^top圖3.3鏈棧a1a2a3a4

3.1棧——棧的實現(xiàn)鏈?zhǔn)綏ｎ惖亩xclassStackNode{DataTypedata; //結(jié)點數(shù)據(jù) StackNode*next; //結(jié)點鏈指針 public:friendclassLinkStack；StackNode(DataTyped=nulldata){data=d;next=NULL;}};//StackNodeclassLinkStack{StackNode*top;//棧頂指針public:LinkStack(){top=newStackNode();top->next=NULL;}//創(chuàng)建頭結(jié)點voidPush(DataTypedata);3.1棧——棧的實現(xiàn)DataTypePop();DataTypeGetTop();voidClear(){top->next=NULL;}boolIsEmpty(){returntop->next==NULL;}};//LinkStack3.1棧——棧的實現(xiàn)類中操作算法的描述入棧操作

voidPush(DataTypeitem){p=newStackNode(item);p->next=top->next;top->next=p;}//Push3.1棧——棧的實現(xiàn)出棧操作DataTypepop(){if(top->next!=NULL){p=top->next;retvalue=p->data; //暫存棧頂數(shù)據(jù)top->next=p->next;//修改棧頂指針deletep;//釋放，返回數(shù)據(jù)returnretvalue;} else{//棧空的情況cout<<”thestackisempty!”<<endl;returnnulldata;}}//Pop3.1棧——棧的實現(xiàn)取棧頂元素操作

DataTypeGetTop(){if(top->next!=NULL)returntop->next->data;else{//棧空的情況cout<<”thestackisempty!”<<endl;returnnulldata;}}//GetTop3.1棧——棧的實現(xiàn)順序棧和鏈棧的比較時間復(fù)雜度：相同，都是常數(shù)時間O(1)空間性能：順序棧：有元素個數(shù)的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當(dāng)內(nèi)存沒有可用空間時才會出現(xiàn)棧滿，但是每個元素都需要一個指針域，從而產(chǎn)生了結(jié)構(gòu)性開銷。定義順序棧時，應(yīng)該知道所需的最大棧長度。如果事先無法預(yù)知棧的最大長度，可以采用鏈?zhǔn)綏！?.1棧——棧與遞歸遞歸是在計算機科學(xué)和數(shù)學(xué)中一種解決問題的極其重要的方法。在數(shù)據(jù)結(jié)構(gòu)中，可以用它來設(shè)計簡單、易于理解的算法，特別是在一些具有遞歸定義的結(jié)構(gòu)上設(shè)計算法。3.1棧——棧與遞歸遞歸的概念遞歸子程序（或函數(shù)）直接調(diào)用自己或通過一系列調(diào)用語句間接調(diào)用自己遞歸是一種描述問題和解決問題的基本方法遞歸的基本思想問題分解：把一個不能或不好解決的大問題轉(zhuǎn)化為一個或幾個同類型的小問題，再把這些小問題進一步分解成更小的小問題，直至每個小問題都可以直接解決。3.1棧——棧與遞歸描述問題例如，求階乘計算階乘的遞歸算法

intfact(intw){

if(w==0)return(1);

elset=fact(w-1);returnw*t;}3.1棧——棧與遞歸例如，計算斐波那契數(shù)列計算斐波那契數(shù)列的遞歸算法

longFib(intn){

if(n==0||n==1)returnn;

elsereturnFib(n-1)+Fib(n-2);}3.1棧——棧與遞歸解決問題漢諾塔問題迷宮問題皇后問題背包問題3.1棧——棧與遞歸遞歸算法的設(shè)計遞歸三要素定義出口，即定義一個最小規(guī)模的問題，并給出其解；把一個大的問題劃分成同類型的規(guī)模較小的子問題；把子問題的解合成為原問題的解。遞歸的實現(xiàn)建立遞歸工作棧3.1棧——棧與遞歸漢諾塔（TowerofHanoi）問題漢諾塔問題來自一個古老的傳說：在世界剛被創(chuàng)建的時候有一座鉆石寶塔（塔A），其上有64個金盤。所有盤子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩座鉆石寶塔（塔B和塔C）。從世界創(chuàng)始之日起，婆羅門的牧師們就一直在試圖把塔A上的盤子移動到塔C上去，其間借助于塔B的幫助。由于盤子非常重，因此，每次只能移動一個盤子。另外，任何時候都不能把一個盤子放在比它小的盤子上面。按照這個傳說，當(dāng)牧師們完成他們的任務(wù)之后，世界末日也就到了。需要移動的次數(shù)為264-13.1棧——棧與遞歸漢諾塔解決方法n=1時，直接把圓盤從塔A移到塔C；n>1時，先把塔A上的n-1個圓盤移到塔B，然后將n號盤從塔A移到塔C，再將n-1個圓盤從塔B移到塔C。即把求解n個圓盤的Hanoi問題轉(zhuǎn)化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉(zhuǎn)化成只有一個圓盤的Hanoi問題。3.1棧——棧與遞歸3.1棧——棧與遞歸解決漢諾塔問題的算法

main(){intn;cout<<"Inputnumberofdisks”;cin>>n;hanoi(n,'A','B','C');}voidhanoi(intn,charx,chary,charz){if(n==1)move(1,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}3.1棧——棧與遞歸遞歸過程和運行時棧遞歸函數(shù)的運行軌跡描述方法1）寫出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語句，并用箭頭表示語句的執(zhí)行次序；2）對函數(shù)的每個遞歸調(diào)用，寫出相應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫一條箭頭指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫一條箭頭指向調(diào)用語句的下面，表示返回路線；3）在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。3.1棧——棧與遞歸n=3時漢諾塔遞歸算法的運行軌跡Hanoi(3,A,B,C）Move(A,3,C)Hanoi(2,A,C,B）Hanoi(2,A,C,B）Hanoi(3,A,B,C）Hanoi(1,A,B,C）遞歸第三層遞歸第二層遞歸第一層Move(A,1,C)Hanoi(1,C,A,B）Move(C,1,B)Hanoi(1,B,C,A）Move(B,1,A)Hanoi(1,A,B,C）Move(A,1,C)Hanoi(1,A,B,C）Move(A,2,B)Hanoi(1,C,A,B）Hanoi(2,B,A,C）Hanoi(1,B,C,A）Move(B,2,C)Hanoi(1,A,B,C）Hanoi(2,B,A,C）(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)3.1棧——棧與遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過程當(dāng)一個函數(shù)在運行期間調(diào)用另一個函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)需要將實參和返回值地址等數(shù)據(jù)傳遞給被調(diào)函數(shù)，當(dāng)函數(shù)調(diào)用時，這些數(shù)據(jù)與局部變量一起構(gòu)成一條“工作記錄”，被壓入系統(tǒng)提供的棧（運行時棧）。當(dāng)被調(diào)函數(shù)返回時，按照返回地址執(zhí)行調(diào)用函數(shù)中下一條指令，同時釋放棧中相應(yīng)的工作記錄。3.1棧——棧與遞歸主程序Callproc1rproc1proc2proc3sCallproc2tCallproc3rst系統(tǒng)運行時棧局部變量返回地址實際參數(shù)工作記錄3.1棧——棧與遞歸遞歸調(diào)用的內(nèi)部執(zhí)行過程運行開始時，首先為遞歸調(diào)用建立一個系統(tǒng)運行時棧；每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址等組成的工作記錄壓入棧中；每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。3.1棧——棧與遞歸n=3時漢諾塔遞歸算法的部分執(zhí)行過程

main(){hanoi(3,'A','B','C');}voidhanoi(intn,charx,chary,charz){if(n==1)move(1,x,z);else{hanoi(n-1,x,z,y);move(n,x,z);hanoi(n-1,y,x,z);}}0123456789ABC321返回地址zyxn3ABC01CAB82ACB61ABC6123.1棧——棧與遞歸遞歸總結(jié)遞歸是重要的設(shè)計和編程工具，使許多算法變得簡單，易于設(shè)計和實現(xiàn)。

－－－－優(yōu)點遞歸使算法的時間復(fù)雜度和空間復(fù)雜度同時增大，有時會導(dǎo)致效率急劇惡化，或者溢出系統(tǒng)棧。

－－－－缺點使用遞歸時應(yīng)該權(quán)衡效率和設(shè)計的關(guān)系。在有足夠的空間并且時間要求不高的情況下可以使用遞歸。3.2隊列——ADT定義定義隊列（Queue）是只允許在表的一端進行刪除，而在另一端進行插入的線性表。允許刪除的一端叫做隊頭（front）允許插入的一端叫做隊尾（rear）特點先進先出（FIFO，F(xiàn)irstInFirstOut）a1a2a3……………….an

入隊出隊frontrear3.2隊列——ADT定義ADT隊列的定義ADTQueue{Data數(shù)據(jù)項列表front：隊列中第一個元素的位置rear：隊列中最后一個元素的位置OperationsConstructorProcess：初始化隊首和隊尾IsEmptyProcess：判斷是否為空隊列Output：若隊列空，返回true，否則返回false3.2隊列——ADT定義LengthProcess：求隊列中元素個數(shù)Output：返回隊列的元素個數(shù)FrontProcess：取出隊頭元素Output：返回隊頭元素EnterInput：要進入隊列的元素Process：在隊尾插入新的元素LeaveProcess：刪除隊頭元素Output：返回隊頭元素ClearQueueProcess：刪除隊列中所有元素并設(shè)置初始狀態(tài)}//Queue3.2隊列——隊列的實現(xiàn)順序隊列順序隊列的定義constintMaxQSize=50;classSeqQueue{intfront,rear;DataTypeQueueList[MaxQSize];public:SeqQueue();//構(gòu)造函數(shù),初始化數(shù)據(jù)成員voidEnter(DataTypeitem);DataTypeLeave();voidClear();DataTypeFront();intLength();boolIsEmpty();boolIsFull();};//SeqQueue3.2隊列——隊列的實現(xiàn)順序隊列的進隊和出隊設(shè)兩個指針front和rear（初始front＝rear＝0）front指向隊頭元素，出隊時先取出，再front+1rear指向隊尾元素的下一個位置，進隊時先將新元素加入，再rear+1隊空條件：front==rear，此時不能出隊隊滿條件：rear==MaxQSize，此時不能進隊3.2隊列——隊列的實現(xiàn)存在問題rear==MaxQSize時，再有元素進隊發(fā)生溢出當(dāng)front==0——真溢出當(dāng)front0——假溢出解決假溢出的方案固定隊頭，出隊時，剩余元素均向前移動固定隊尾，入隊時，剩余元素均向前移動循環(huán)隊列：把隊列設(shè)想成環(huán)形，讓0接在

MaxQSize-1后——更好3.2隊列——隊列的實現(xiàn)循環(huán)隊列也是隊列的順序存儲結(jié)構(gòu)實現(xiàn)利用“模”運算入隊QueueList[rear]=item;rear=(rear+1)%MaxQSize;出隊item=QueueList[front];front=(front+1)%MaxQSize;01frontrear…...…...MaxQSize-13.2隊列——隊列的實現(xiàn)仍然存在問題如何判斷隊列是“空”還是“滿”？隊空：front==rear隊滿：front==rear3.2隊列——隊列的實現(xiàn)三種處理方法給隊列設(shè)一個標(biāo)志位以區(qū)別隊列是空還是滿給隊列增加一個統(tǒng)計元素個數(shù)的變量count，當(dāng)count=MaxQSize時隊滿；count=0時隊空少用一個變量，約定rear+1等于front（從后面趕上隊頭指針）為隊滿的情況隊滿條件：(rear+1)%MaxQSize==front隊空條件：

front

==rear3.2隊列——隊列的實現(xiàn)循環(huán)隊列類的操作算法描述構(gòu)造函數(shù)，初始化一個空隊列

SeqQueue(){front=rear=0;}//SeqQueue入隊操作voidEnter(DataTypeitem){if((rear+1)%MaxQSize==front)//判斷是否隊滿cout<<”隊列已滿，不能入隊！”<<endl;elseQueueList[rear]=item;rear=(rear+1)%MaxQSize;}//Enter3.2隊列——隊列的實現(xiàn)出隊操作DataTypeLeave(){if(front==rear){//判斷是否隊空cout<<”隊列已空，不能出隊”<<endl;returnnulldata;}e=QueueList[front]);front=(front+1)%MaxQSize;returne;}//Leave清空隊列voidClearQueue(){rear=front;}//ClearQueue3.2隊列——隊列的實現(xiàn)判斷隊列是否為空boolIsEmpty(){if(rear==front)returntrue;elsereturnfalse;}//IsEmpty判斷隊列是否已滿boolIsFull(){if((rear+1)%MaxQSize==front)returntrue;elsereturnfalse;}//IsFull3.2隊列——隊列的實現(xiàn)鏈隊列隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)用單鏈表來實現(xiàn)鏈隊列設(shè)置一個隊頭指針front：在鏈頭設(shè)置一個隊尾指針rear：在鏈尾鏈隊列無隊滿問題隊空條件：front->next==NULLfront圖3.13鏈隊列a1a2a3a4

rear3.2隊列——隊列的實現(xiàn)鏈隊列描述classQNode{//鏈隊結(jié)點的類DataTypedata;QNode*next;public:QNode(DataTypeitem=nulldata){data=item;next=NULL;}friendclassLinkQueue;};//QNode3.2隊列——隊列的實現(xiàn)classLinkQueue{QNnode*front,*rear;public:LinkQueue(){rear=front=newQNode();}voidEnter(DataTypeitem);DataTypeLeave(); DataTypeFront(); voidClear(){front->next=rear->next=NULL;}boolIsEmpty(){returnfront–>next==NULL;} };//LinkQueue3.2隊列——隊列的實現(xiàn)鏈隊列基本操作的算法描述入隊操作voidEnter(DataTypeitem){rear->next=newQNode(item);rear=rear->next;}//Enter3.2隊列——隊列的實現(xiàn)出隊操作DataTypeLeave(){if(!IsEmpty()){//判隊不空p=front->next; DataTyperetvalue=p->data; //保存隊頭的值front->next=p->next;deletep;if(front->next==NULL)//刪除隊列中唯一結(jié)點后，重新設(shè)置rearrear=front;returnretvalue; }else{cout<<”隊列空!”<<endl;returnnulldata;}}//Leave3.2隊列——隊列的實現(xiàn)取隊頭元素DataTypeFront(){if(!IsEmpty()) returnfront->next->data; else{cout<<”隊列空，無隊頭元素！”<<endl;returnnulldata;}}//Front3.2隊列——隊列的實現(xiàn)優(yōu)先級隊列主要有插入和刪除操作插入操作：與普通隊列相同刪除操作：優(yōu)先級高的元素先被刪除，同一優(yōu)先級的元素按其到達先后進行處理實際應(yīng)用中經(jīng)常用到，例如操作系統(tǒng)中的進程優(yōu)先級隊列優(yōu)先級隊列的ADT與普通隊列的ADT相似，只是刪除操作與普通隊列不同3.3棧與隊列的應(yīng)用棧的應(yīng)用應(yīng)用1：數(shù)制轉(zhuǎn)換問題將十進制數(shù)N轉(zhuǎn)換為r進制的數(shù)轉(zhuǎn)換方法：輾轉(zhuǎn)相除法例，N=3467，r=8（1348）10=（2504）8

NNdiv8Nmod8

13481684

168210

2125

202計算順序輸出順序3.3棧與隊列的應(yīng)用所轉(zhuǎn)換的8進制數(shù)按低位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計算過程相反，因此轉(zhuǎn)換過程中每得到一位8進制數(shù)則進棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想當(dāng)N>0時重復(fù)（1），（2）（1）若N≠0，則將N%r壓入棧s中，執(zhí)行（2）；若N＝0，將棧s的內(nèi)容依次出棧，算法結(jié)束。（2）用N/r代替N3.3棧與隊列的應(yīng)用算法描述voidconversion(intN，intr){SeqStacks;intx;while(N){s.Push(N%r);N=N/r;}while(!s.IsEmpty()){x=s.Pop();cout<<x;}//while}//conversion3.3棧與隊列的應(yīng)用應(yīng)用2：表達式求值表達式表達式由操作數(shù)（operand）、運算符（operator）和分界符（delimiter）組成操作數(shù)：變量或常數(shù)運算符：算術(shù)運算符、關(guān)系運算符、邏輯運算符分界符：括號表達式的表示方法前綴表達式中綴表達式后綴表達式3.3棧與隊列的應(yīng)用后綴表達式（逆波蘭式）求值后綴表達式不含括號運算符放在兩個操作數(shù)后面例中綴表達式2+(3*8–4)/5后綴表達式238*4-5/+所有的求值計算皆按運算符出現(xiàn)的順序，嚴格從左向右進行比中綴表達式的計算簡單3.3棧與隊列的應(yīng)用算法思想設(shè)一個棧；順序掃描后綴表達式的每一項，根據(jù)其類型做如下處理：如果該項是操作數(shù)，則將其壓入棧頂；如果該項是運算符<op>，則連續(xù)從棧頂退出兩個操作數(shù)x和y，形成運算指令x<op>y，并將結(jié)果重新壓入棧頂。表達式所有項掃描并處理完后（以符號“=”為結(jié)束），棧頂存放的就是計算結(jié)果。3.3棧與隊列的應(yīng)用棧輸入操作序列

ABCD+EF/PushABCDCDPushPushPop,Pop,PushPushPop,Pop,PushB(CD)Pop,Pop,PushA+B(CD)EFE/FPushPushPop,Pop,PushPop,Pop,PushA+B(C-D)E/F3.3棧與隊列的應(yīng)用中綴表達式的計算中綴表達式的計算次序根據(jù)運算符優(yōu)先級由高到低的順序進行運算有括號出現(xiàn)時先算括號內(nèi)的，后算括號外的，多層括號，由內(nèi)向外進行乘方連續(xù)出現(xiàn)時先算最右面的計算方法1按中綴表達式的順序計算（本書）計算方法2先將中綴表達式轉(zhuǎn)換為后綴表達式再進行后綴表達式求值3.3棧與隊列的應(yīng)用計算方法1根據(jù)上述三條運算規(guī)則，在運算的每一步中，對任意相繼出現(xiàn)的運算符1和2，都要比較優(yōu)先關(guān)系運算符間的優(yōu)先關(guān)系見下表

21

*/+－()#*/+－（）#>>>><>>>>>><>><<>><>><<>><>><<<<<=>>>>>><<<<<=3.3棧與隊列的應(yīng)用算法思想設(shè)定兩棧：操作數(shù)棧OPND，運算符棧OPTR棧初始化：設(shè)操作數(shù)棧OPND為空；運算符棧OPTR的棧底元素為表達式起始符‘#’；依次讀入字符：是操作數(shù)則入OPND棧，是運算符則要判斷（設(shè)OPTR的棧頂元素為1，當(dāng)前讀入的運算符為2）：

1）if1<2，將2壓入OPTR棧；

2）if1==2且不為‘#’，退括號（彈出左括號）；

3）if1>2，則退棧、計算，結(jié)果壓入OPND棧；重復(fù)，直至讀入字符和OPTR的棧頂元素均為‘#’，此時OPND的棧頂即為計算結(jié)果3.3棧與隊列的應(yīng)用OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,’3’)

#*(7-2)#3#Push(optr,’*’)#,*3(7-2)#Push(optr,’(’)#,*,(37-2)#Push(opnd,’7’)#,*,(3,7-2)#Push(optr,’-’)#,*,(,-3,72)#Push(opnd,’2’)#,*,(,-3,7,2)#Operate(7-2)#,*,(3,5)#Pop(optr)#,*3,5#Operate(3*5)#15#GetTop(opnd)3.3棧與隊列的應(yīng)用算法描述voidEvaluateExpression(OperandType&result){//s1為操作對象棧，s2為運算符棧，OP為運算符集合SeqStacks1,s2;s2.Push(’#’);c=getchar();while((c!=‘#’)&&(s2.GetTop()!=‘#’)){if(!In(c,OP){s1.Push(c);c=getchar();}3.3棧與隊列的應(yīng)用elseswitch(compare(s2.GetTop(),c)){case‘<’:s2.Push(c);c=getchar();break;case‘=’:s2.Pop();c=getchar();break;case‘>’:{temat=s2.Pop();b=s1.Pop();a=s1.Pop();result=Operate(a,temat,b);s1.Push(result);

c=getchar();break;}}//switch}//whileresult=s1.GetTop();}//EvaluateExpression3.3棧與隊列的應(yīng)用計算方法2——將中綴表達式轉(zhuǎn)換成后綴表達式設(shè)置一個棧，棧底元素為表達式起始符‘#’；依次讀入中綴表達式的每一字符，是操作數(shù)則直接輸出，是運算符則要判斷（設(shè)棧頂元素為1，當(dāng)前讀入的運算符為2）：1）if1<2，則2入棧，讀入下一字符；2）if1>2，

則退棧，并輸出；3）if1==2且不為‘#’，

則退棧，但不輸出，若退出的是’(‘則讀入下一字符；重復(fù)，直至讀入字符和棧頂元素均為‘#’，算法結(jié)束，此時輸出序列即為后綴表達式3.3棧與隊列的應(yīng)用應(yīng)用3：迷宮求解問題

入口出口3.3棧與隊列的應(yīng)用基本思想從入口出發(fā)，沿某一方向向前探索若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進；若當(dāng)前位置“不可通”，則換方向繼續(xù)探索;若四周“均無通路”，則沿原路退回到前一位置，換方向繼續(xù)探索3.3棧與隊列的應(yīng)用迷宮求解問題的遞歸算法算法中用到的數(shù)據(jù)結(jié)構(gòu)intMaze[m+2][p+2]：表示迷宮m表示行數(shù)，p表示列數(shù)第0、m+1行，第0、p+1列是迷宮的圍墻Maze[i][j]=1時，表示該位置是墻壁，不能通行Maze[i][j]=0時，表示該位置是通路intmark[m+2][p+2]：標(biāo)志矩陣初始為0，當(dāng)某一位置[i][j]走過時，置mark[i][j]=13.3棧與隊列的應(yīng)用offsetsmove[4]：表示方向Structoffsets{inta,b;char*d;}move[q].dmove[q].amove[q].bE(東)01S(南)10W(西)0-1N(北)-10N(北)[i-1,j]W(西)[i,j-1]當(dāng)前位置[i,j]E(東)[i,j+1]S(南)[i+1,j]3.3棧與隊列的應(yīng)用遞歸函數(shù)intSeekPath(intx,inty){inti,g,h;char*d;if(x==m&&y==p)return1;for(i=0;i<4;i++){g=x+move[i].a;h=y+move[i].b;d=move[i].dir;if(!Maze[g][h]&&!mark[g][h]){mark[g][h]=1;if(SeekPath(g,h)){

cout<<“(“<<g<<“,”<<h<<“),”<<“Direction”<<dir<<“,”;return1;}}}if(x==1&&y==1)