第3章棧和隊列3.1棧3.2隊列3.3棧與隊列的應用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棧棧的抽象數據類型ADTStack{

Data數據項列表top：棧頂位置

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

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

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

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

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

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

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

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

voidClear(){top=-1;}//Cleartop=-1012341001234壓入10top=0102501234壓入25top=110255001234壓入50top=2102501234彈出50top=11001234彈出25top=0圖3.2出棧和入棧操作以及棧頂的變化3.1棧——棧的實現鏈式棧（LinkedStack）鏈式棧（鏈棧）鏈式存儲的棧用單鏈表來實現鏈棧，因此其結點結構與單鏈表的結構相同鏈式棧無棧滿問題，空間可擴充鏈式棧的棧頂在鏈頭top圖3.3鏈棧a1a2a3a4

3.1棧——棧的實現鏈式棧類的定義classStackNode{DataTypedata; //結點數據 StackNode*next; //結點鏈指針 public:friendclassLinkStack；StackNode(DataTyped=nulldata){data=d;next=NULL;}};//StackNodeclassLinkStack{StackNode*top;//棧頂指針public:LinkStack(){top=newStackNode();top->next=NULL;}//創建頭結點voidPush(DataTypedata);3.1棧——棧的實現DataTypePop();DataTypeGetTop();voidClear(){top->next=NULL;}boolIsEmpty(){returntop->next==NULL;}};//LinkStack3.1棧——棧的實現類中操作算法的描述入棧操作

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

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

intfact(intw){

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

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

longFib(intn){

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

elsereturnFib(n-1)+Fib(n-2);}3.1棧——棧與遞歸解決問題漢諾塔問題迷宮問題皇后問題背包問題3.1棧——棧與遞歸遞歸算法的設計遞歸三要素定義出口，即定義一個最小規模的問題，并給出其解；把一個大的問題劃分成同類型的規模較小的子問題；把子問題的解合成為原問題的解。遞歸的實現建立遞歸工作棧3.1棧——棧與遞歸漢諾塔（TowerofHanoi）問題漢諾塔問題來自一個古老的傳說：在世界剛被創建的時候有一座鉆石寶塔（塔A），其上有64個金盤。所有盤子按從大到小的次序從塔底堆放至塔頂。緊挨著這座塔有另外兩座鉆石寶塔（塔B和塔C）。從世界創始之日起，婆羅門的牧師們就一直在試圖把塔A上的盤子移動到塔C上去，其間借助于塔B的幫助。由于盤子非常重，因此，每次只能移動一個盤子。另外，任何時候都不能把一個盤子放在比它小的盤子上面。按照這個傳說，當牧師們完成他們的任務之后，世界末日也就到了。需要移動的次數為264-13.1棧——棧與遞歸漢諾塔解決方法n=1時，直接把圓盤從塔A移到塔C；n>1時，先把塔A上的n-1個圓盤移到塔B，然后將n號盤從塔A移到塔C，再將n-1個圓盤從塔B移到塔C。即把求解n個圓盤的Hanoi問題轉化為求解n-1個圓盤的Hanoi問題，依次類推，直至轉化成只有一個圓盤的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棧——棧與遞歸遞歸過程和運行時棧遞歸函數的運行軌跡描述方法1）寫出函數當前調用層執行的各語句，并用箭頭表示語句的執行次序；2）對函數的每個遞歸調用，寫出相應的函數調用，從調用處畫一條箭頭指向被調用函數入口，表示調用路線，從被調用函數末尾處畫一條箭頭指向調用語句的下面，表示返回路線；3）在返回路線上標出本層調用所得的函數值。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棧——棧與遞歸遞歸函數的內部執行過程當一個函數在運行期間調用另一個函數時，在運行被調用函數之前，系統需要將實參和返回值地址等數據傳遞給被調函數，當函數調用時，這些數據與局部變量一起構成一條“工作記錄”，被壓入系統提供的棧（運行時棧）。當被調函數返回時，按照返回地址執行調用函數中下一條指令，同時釋放棧中相應的工作記錄。3.1棧——棧與遞歸主程序Callproc1rproc1proc2proc3sCallproc2tCallproc3rst系統運行時棧局部變量返回地址實際參數工作記錄3.1棧——棧與遞歸遞歸調用的內部執行過程運行開始時，首先為遞歸調用建立一個系統運行時棧；每次執行遞歸調用之前，把遞歸函數的值參和局部變量的當前值以及調用后的返回地址等組成的工作記錄壓入棧中；每次遞歸調用結束后，將棧頂元素出棧，使相應的值參和局部變量恢復為調用前的值，然后轉向返回地址指定的位置繼續執行。3.1棧——棧與遞歸n=3時漢諾塔遞歸算法的部分執行過程

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棧——棧與遞歸遞歸總結遞歸是重要的設計和編程工具，使許多算法變得簡單，易于設計和實現。

－－－－優點遞歸使算法的時間復雜度和空間復雜度同時增大，有時會導致效率急劇惡化，或者溢出系統棧。

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

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

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

front

==rear3.2隊列——隊列的實現循環隊列類的操作算法描述構造函數，初始化一個空隊列

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

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

NNdiv8Nmod8

13481684

168210

2125

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

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棧與隊列的應用中綴表達式的計算中綴表達式的計算次序根據運算符優先級由高到低的順序進行運算有括號出現時先算括號內的，后算括號外的，多層括號，由內向外進行乘方連續出現時先算最右面的計算方法1按中綴表達式的順序計算（本書）計算方法2先將中綴表達式轉換為后綴表達式再進行后綴表達式求值3.3棧與隊列的應用計算方法1根據上述三條運算規則，在運算的每一步中，對任意相繼出現的運算符1和2，都要比較優先關系運算符間的優先關系見下表

21

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

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

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

3）if1>2，則退棧、計算，結果壓入OPND棧；重復，直至讀入字符和OPTR的棧頂元素均為‘#’，此時OPND的棧頂即為計算結果3.3棧與隊列的應用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棧與隊列的應用算法描述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棧與隊列的應用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棧與隊列的應用計算方法2——將中綴表達式轉換成后綴表達式設置一個棧，棧底元素為表達式起始符‘#’；依次讀入中綴表達式的每一字符，是操作數則直接輸出，是運算符則要判斷（設棧頂元素為1，當前讀入的運算符為2）：1）if1<2，則2入棧，讀入下一字符；2）if1>2，

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

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

入口出口3.3棧與隊列的應用基本思想從入口出發，沿某一方向向前探索若當前位置“可通”，則納入路徑，繼續前進；若當前位置“不可通”，則換方向繼續探索;若四周“均無通路”，則沿原路退回到前一位置，換方向繼續探索3.3棧與隊列的應用迷宮求解問題的遞歸算法算法中用到的數據結構intMaze[m+2][p+2]：表示迷宮m表示行數，p表示列數第0、m+1行，第0、p+1列是迷宮的圍墻Maze[i][j]=1時，表示該位置是墻壁，不能通行Maze[i][j]=0時，表示該位置是通路intmark[m+2][p+2]：標志矩陣初始為0，當某一位置[i][j]走過時，置mark[i][j]=13.3棧與隊列的應用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]當前位置[i,j]E(東)[i,j+1]S(南)[i+1,j]3.3棧與隊列的應用遞歸函數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)