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

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

a1，a3，a2

a2，a1，a3

a2，a3，a1

a3，a2，a1注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。3.1?！狝DT棧棧的抽象數(shù)據(jù)類(lèi)型ADTStack{

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

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

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

top①確定用數(shù)組的哪一端表示棧底。a1a2a33.1?！獥５膶?shí)現(xiàn)順序棧的基本操作出棧：先出棧top再減1進(jìn)棧：top先加1再進(jìn)棧?？眨簍op==-1

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

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

DataTypeGetTop(){if(IsEmpty()){cout<<”?？眨　?lt;<endl;returnnulldata;}returnStackList[top];}3.1?！獥５膶?shí)現(xiàn)向棧頂壓入元素

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

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

voidClear(){top=-1;}//Cleartop=-1012341001234壓入10top=0102501234壓入25top=110255001234壓入50top=2102501234彈出50top=11001234彈出25top=0圖3.2出棧和入棧操作以及棧頂?shù)淖兓?.1?！獥５膶?shí)現(xiàn)鏈?zhǔn)綏＃↙inkedStack）鏈?zhǔn)綏＃ㄦ湕＃╂準(zhǔn)酱鎯?chǔ)的棧用單鏈表來(lái)實(shí)現(xiàn)鏈棧，因此其結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)構(gòu)相同鏈?zhǔn)綏o(wú)棧滿問(wèn)題，空間可擴(kuò)充鏈?zhǔn)綏５臈ｍ斣阪滎^top圖3.3鏈棧a1a2a3a4

3.1?！獥５膶?shí)現(xiàn)鏈?zhǔn)綏ｎ?lèi)的定義classStackNode{DataTypedata; //結(jié)點(diǎn)數(shù)據(jù) StackNode*next; //結(jié)點(diǎn)鏈指針 public:friendclassLinkStack；StackNode(DataTyped=nulldata){data=d;next=NULL;}};//StackNodeclassLinkStack{StackNode*top;//棧頂指針public:LinkStack(){top=newStackNode();top->next=NULL;}//創(chuàng)建頭結(jié)點(diǎn)voidPush(DataTypedata);3.1?！獥５膶?shí)現(xiàn)DataTypePop();DataTypeGetTop();voidClear(){top->next=NULL;}boolIsEmpty(){returntop->next==NULL;}};//LinkStack3.1?！獥５膶?shí)現(xiàn)類(lèi)中操作算法的描述入棧操作

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

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

intfact(intw){

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

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

longFib(intn){

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

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

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?！獥Ｅc遞歸遞歸過(guò)程和運(yùn)行時(shí)棧遞歸函數(shù)的運(yùn)行軌跡描述方法1）寫(xiě)出函數(shù)當(dāng)前調(diào)用層執(zhí)行的各語(yǔ)句，并用箭頭表示語(yǔ)句的執(zhí)行次序；2）對(duì)函數(shù)的每個(gè)遞歸調(diào)用，寫(xiě)出相應(yīng)的函數(shù)調(diào)用，從調(diào)用處畫(huà)一條箭頭指向被調(diào)用函數(shù)入口，表示調(diào)用路線，從被調(diào)用函數(shù)末尾處畫(huà)一條箭頭指向調(diào)用語(yǔ)句的下面，表示返回路線；3）在返回路線上標(biāo)出本層調(diào)用所得的函數(shù)值。3.1?！獥Ｅc遞歸n=3時(shí)漢諾塔遞歸算法的運(yùn)行軌跡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?！獥Ｅc遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程當(dāng)一個(gè)函數(shù)在運(yùn)行期間調(diào)用另一個(gè)函數(shù)時(shí)，在運(yùn)行被調(diào)用函數(shù)之前，系統(tǒng)需要將實(shí)參和返回值地址等數(shù)據(jù)傳遞給被調(diào)函數(shù)，當(dāng)函數(shù)調(diào)用時(shí)，這些數(shù)據(jù)與局部變量一起構(gòu)成一條“工作記錄”，被壓入系統(tǒng)提供的棧（運(yùn)行時(shí)棧）。當(dāng)被調(diào)函數(shù)返回時(shí)，按照返回地址執(zhí)行調(diào)用函數(shù)中下一條指令，同時(shí)釋放棧中相應(yīng)的工作記錄。3.1?！獥Ｅc遞歸主程序Callproc1rproc1proc2proc3sCallproc2tCallproc3rst系統(tǒng)運(yùn)行時(shí)棧局部變量返回地址實(shí)際參數(shù)工作記錄3.1棧——棧與遞歸遞歸調(diào)用的內(nèi)部執(zhí)行過(guò)程運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)系統(tǒng)運(yùn)行時(shí)棧；每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址等組成的工作記錄壓入棧中；每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。3.1?！獥Ｅc遞歸n=3時(shí)漢諾塔遞歸算法的部分執(zhí)行過(guò)程

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?！獥Ｅc遞歸遞歸總結(jié)遞歸是重要的設(shè)計(jì)和編程工具，使許多算法變得簡(jiǎn)單，易于設(shè)計(jì)和實(shí)現(xiàn)。

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

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

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

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

front

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

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

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

NNdiv8Nmod8

13481684

168210

2125

202計(jì)算順序輸出順序3.3棧與隊(duì)列的應(yīng)用所轉(zhuǎn)換的8進(jìn)制數(shù)按低位到高位的順序產(chǎn)生的，而通常的輸出是從高位到低位的，恰好與計(jì)算過(guò)程相反，因此轉(zhuǎn)換過(guò)程中每得到一位8進(jìn)制數(shù)則進(jìn)棧保存，轉(zhuǎn)換完畢后依次出棧則正好是轉(zhuǎn)換結(jié)果。算法思想當(dāng)N>0時(shí)重復(fù)（1），（2）（1）若N≠0，則將N%r壓入棧s中，執(zhí)行（2）；若N＝0，將棧s的內(nèi)容依次出棧，算法結(jié)束。（2）用N/r代替N3.3棧與隊(duì)列的應(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棧與隊(duì)列的應(yīng)用應(yīng)用2：表達(dá)式求值表達(dá)式表達(dá)式由操作數(shù)（operand）、運(yùn)算符（operator）和分界符（delimiter）組成操作數(shù)：變量或常數(shù)運(yùn)算符：算術(shù)運(yùn)算符、關(guān)系運(yùn)算符、邏輯運(yùn)算符分界符：括號(hào)表達(dá)式的表示方法前綴表達(dá)式中綴表達(dá)式后綴表達(dá)式3.3棧與隊(duì)列的應(yīng)用后綴表達(dá)式（逆波蘭式）求值后綴表達(dá)式不含括號(hào)運(yùn)算符放在兩個(gè)操作數(shù)后面例中綴表達(dá)式2+(3*8–4)/5后綴表達(dá)式238*4-5/+所有的求值計(jì)算皆按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右進(jìn)行比中綴表達(dá)式的計(jì)算簡(jiǎn)單3.3棧與隊(duì)列的應(yīng)用算法思想設(shè)一個(gè)棧；順序掃描后綴表達(dá)式的每一項(xiàng)，根據(jù)其類(lèi)型做如下處理：如果該項(xiàng)是操作數(shù)，則將其壓入棧頂；如果該項(xiàng)是運(yùn)算符<op>，則連續(xù)從棧頂退出兩個(gè)操作數(shù)x和y，形成運(yùn)算指令x<op>y，并將結(jié)果重新壓入棧頂。表達(dá)式所有項(xiàng)掃描并處理完后（以符號(hào)“=”為結(jié)束），棧頂存放的就是計(jì)算結(jié)果。3.3棧與隊(duì)列的應(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棧與隊(duì)列的應(yīng)用中綴表達(dá)式的計(jì)算中綴表達(dá)式的計(jì)算次序根據(jù)運(yùn)算符優(yōu)先級(jí)由高到低的順序進(jìn)行運(yùn)算有括號(hào)出現(xiàn)時(shí)先算括號(hào)內(nèi)的，后算括號(hào)外的，多層括號(hào)，由內(nèi)向外進(jìn)行乘方連續(xù)出現(xiàn)時(shí)先算最右面的計(jì)算方法1按中綴表達(dá)式的順序計(jì)算（本書(shū)）計(jì)算方法2先將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式再進(jìn)行后綴表達(dá)式求值3.3棧與隊(duì)列的應(yīng)用計(jì)算方法1根據(jù)上述三條運(yùn)算規(guī)則，在運(yùn)算的每一步中，對(duì)任意相繼出現(xiàn)的運(yùn)算符1和2，都要比較優(yōu)先關(guān)系運(yùn)算符間的優(yōu)先關(guān)系見(jiàn)下表

21

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

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

2）if1==2且不為‘#’，退括號(hào)（彈出左括號(hào)）；

3）if1>2，則退棧、計(jì)算，結(jié)果壓入OPND棧；重復(fù)，直至讀入字符和OPTR的棧頂元素均為‘#’，此時(shí)OPND的棧頂即為計(jì)算結(jié)果3.3棧與隊(duì)列的應(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棧與隊(duì)列的應(yīng)用算法描述voidEvaluateExpression(OperandType&result){//s1為操作對(duì)象棧，s2為運(yùn)算符棧，OP為運(yùn)算符集合SeqStacks1,s2;s2.Push(’#’);c=getchar();while((c!=‘#’)&&(s2.GetTop()!=‘#’)){if(!In(c,OP){s1.Push(c);c=getchar();}3.3棧與隊(duì)列的應(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棧與隊(duì)列的應(yīng)用計(jì)算方法2——將中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式設(shè)置一個(gè)棧，棧底元素為表達(dá)式起始符‘#’；依次讀入中綴表達(dá)式的每一字符，是操作數(shù)則直接輸出，是運(yùn)算符則要判斷（設(shè)棧頂元素為1，當(dāng)前讀入的運(yùn)算符為2）：1）if1<2，則2入棧，讀入下一字符；2）if1>2，

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

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

入口出口3.3棧與隊(duì)列的應(yīng)用基本思想從入口出發(fā)，沿某一方向向前探索若當(dāng)前位置“可通”，則納入路徑，繼續(xù)前進(jìn)；若當(dāng)前位置“不可通”，則換方向繼續(xù)探索;若四周“均無(wú)通路”，則沿原路退回到前一位置，換方向繼續(xù)探索3.3棧與隊(duì)列的應(yīng)用迷宮求解問(wèn)題的遞歸算法算法中用到的數(shù)據(jù)結(jié)構(gòu)intMaze[m+2][p+2]：表示迷宮m表示行數(shù)，p表示列數(shù)第0、m+1行，第0、p+1列是迷宮的圍墻Maze[i][j]=1時(shí)，表示該位置是墻壁，不能通行Maze[i][j]=0時(shí)，表示該位置是通路intmark[m+2][p+2]：標(biāo)志矩陣初始為0，當(dāng)某一位置[i][j]走過(guò)時(shí)，置mark[i][j]=13.3棧與隊(duì)列的應(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棧與隊(duì)列的應(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)