數(shù)據(jù)結(jié)構(gòu)案例教程（CC++版）第2版 課件 第3章 操作受限的線性表：棧和隊(duì)列

第3章操作受限的線性表：棧和隊(duì)列導(dǎo)學(xué)問(wèn)題1：數(shù)制轉(zhuǎn)換問(wèn)題【問(wèn)題描述】

已知十進(jìn)制數(shù)n，試將其轉(zhuǎn)換成對(duì)應(yīng)的八進(jìn)制數(shù)?！痉治觥恳詎=1269為例

計(jì)算過(guò)程中，取余數(shù)的順序正好與計(jì)算產(chǎn)生余數(shù)的順序相反的，因此可將每次產(chǎn)生的余數(shù)依次保存起來(lái)，轉(zhuǎn)換結(jié)束后，再按保存的逆序取出余數(shù)打印即可。

顯然，保存的余數(shù)應(yīng)該具備“后進(jìn)先出”的特點(diǎn)，可用棧作為數(shù)據(jù)結(jié)構(gòu)。導(dǎo)學(xué)問(wèn)題2：銀行排隊(duì)問(wèn)題【問(wèn)題描述】

請(qǐng)?jiān)O(shè)計(jì)一個(gè)簡(jiǎn)單的模擬銀行排隊(duì)系統(tǒng)，要求程序具有三項(xiàng)菜單：1）取號(hào)。選擇該菜單后，為客戶產(chǎn)生一個(gè)排隊(duì)號(hào)。2）叫號(hào)。選擇該菜單后，顯示可服務(wù)的客戶排隊(duì)號(hào)。3）退出系統(tǒng)。【分析】

銀行排隊(duì)問(wèn)題屬于典型的先來(lái)先服務(wù)，因此需要將產(chǎn)生的排隊(duì)號(hào)存放在具有“先進(jìn)先出”特性的數(shù)據(jù)結(jié)構(gòu)中，隊(duì)列結(jié)構(gòu)可以滿足要求。

3.1棧3.1.1知識(shí)學(xué)習(xí)棧：限定僅在表尾進(jìn)行插入和刪除操作的線性表?？諚＃翰缓魏螖?shù)據(jù)元素的棧。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。（a1,a2,……,an）棧頂棧底abc入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖3.1棧棧的操作特性：后進(jìn)先出abc入棧出棧棧底棧頂插入：入棧、進(jìn)棧、壓棧刪除：出棧、彈棧棧頂3.1棧棧的示意圖例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：3.1棧例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂情況2：3.1棧出棧序列：b棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對(duì)表插入和刪除操作的位置進(jìn)行了限制，并沒(méi)有限定插入和刪除操作進(jìn)行的時(shí)間。情況2：例：有三個(gè)元素按a、b、c的次序依次進(jìn)棧，且每個(gè)元素只允許進(jìn)一次棧，則可能的出棧序列有多少種？3.1棧如何改造數(shù)組實(shí)現(xiàn)棧的順序存儲(chǔ)？

012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。

top棧的順序存儲(chǔ)結(jié)構(gòu)及基本操作出棧：top減1進(jìn)棧：top加1棧空：top=-1

012345678a1topa2topa3top棧滿：top=MaxSize-1棧的順序存儲(chǔ)及基本操作constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; inttop;}SeqStack;順序棧的類型定義voidInitStack(SeqStack&S){S.top=-1;}順序棧的實(shí)現(xiàn)——初始化voidPush(SeqStack&S,ElemTypex){if(S.top==MAXSIZE-1){cout<<"棧已滿"<<endl;exit(1);}

S.top++;

S.data[S.top]=x;}順序棧的實(shí)現(xiàn)——入棧ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"棧已空"<<endl;exit(1);}

ElemTypex=S.data[S.top];

S.top--; returnx;}順序棧的實(shí)現(xiàn)——出棧ElemTypePop(SeqStack&S){if(S.top==-1){cout<<"棧已空"<<endl;exit(1);}

returnS.data[S.top];}順序棧的實(shí)現(xiàn)——取棧頂元素boolStackEmpty(SeqStack&S){ returnS.top==-1;}順序棧的實(shí)現(xiàn)——判斷?？誦oolStackEmpty(SeqStack&S){ returnS.top==MAXSIZE-1;}順序棧的實(shí)現(xiàn)——判斷棧滿heada1a2an∧ai鏈棧需要加頭結(jié)點(diǎn)嗎？如何改造鏈表實(shí)現(xiàn)棧的鏈接存儲(chǔ)？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設(shè)頭結(jié)點(diǎn)。棧的鏈?zhǔn)酱鎯?chǔ)及基本操作棧頂棧底鏈棧：棧的鏈接存儲(chǔ)結(jié)構(gòu)topanan-1a1∧兩種示意圖在內(nèi)存中對(duì)應(yīng)同一種狀態(tài)topa1an-1an∧棧頂棧底棧的鏈?zhǔn)酱鎯?chǔ)及基本操作typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}*LinkStack;鏈棧的類型定義voidInitStack(LinkStack&S){ S=NULL;}鏈棧的實(shí)現(xiàn)——初始化算法描述：voidPush(LinkStack&S,ElemTypex){LinkStackp=newNode;

p->data=x;

p->next=S;

S=p;}Sanan-1a1∧xpS鏈棧的實(shí)現(xiàn)——入棧算法描述：ElemTypePop(LinkStack&S){

if(S==NULL)

{cout<<"棧已空";exit(1);}

ElemTypex=S->data;//暫存棧頂元素

LinkStackp=S;

S=S->next;//刪除棧頂結(jié)點(diǎn)

deletep;

returnx;}Sanan-1a1∧Sp

鏈棧的實(shí)現(xiàn)——出棧ElemTypeTop(LinkStack&S){ if(S==NULL) {cout<<"棧已空";exit(1);} returnS->data;}鏈棧的實(shí)現(xiàn)——取棧頂元素boolStackEmpty(LinkStack&S){ returnS==NULL;}鏈棧的實(shí)現(xiàn)——判斷?？誺oidDestroyListStack(LinkStack&S){LinkStackp;

while(S)

{

p=S;

S=S->next;

deletep;

}}鏈棧的實(shí)現(xiàn)——銷毀順序棧和鏈棧的比較時(shí)間性能：相同，都是常數(shù)時(shí)間O(1)?？臻g性能：順序棧：有元素個(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)銷。總之，當(dāng)棧的使用過(guò)程中元素個(gè)數(shù)變化較大時(shí)，用鏈棧是適宜的，反之，應(yīng)該采用順序棧。3.1.2知識(shí)應(yīng)用——導(dǎo)學(xué)問(wèn)題1voidconversion(intn){SeqStackS;InitStack(S);while(n){Push(S,n%8);n=n/8;}while(!StackEmpty(S))cout<<Pop(S);cout<<endl;}3.1.3知識(shí)拓展——算術(shù)表達(dá)式求值1、中綴表達(dá)式直接求值為實(shí)現(xiàn)算符優(yōu)先算法，可以使用兩個(gè)工作棧：

1）運(yùn)算符OPTR棧,用以寄存運(yùn)算符；2）操作數(shù)OPND棧,用以寄存操作數(shù)或運(yùn)算結(jié)果。算法步驟：參見(jiàn)教材3.1.3知識(shí)拓展——算術(shù)表達(dá)式求值2、利用后綴表達(dá)式求值

將中綴表達(dá)式變成等價(jià)的后綴表達(dá)式時(shí)，表達(dá)式中操作數(shù)次序不變，而操作符次序會(huì)發(fā)生變化，同時(shí)需要去掉圓括號(hào)。因此設(shè)置一個(gè)棧OPTR用以存放操作符。。算法步驟：參見(jiàn)教材3.1.3知識(shí)拓展——棧和遞歸求階乘的遞歸算法intFact(intn){if(n==0)return1;elsereturnn*Fact(n-1);}3.1.3知識(shí)拓展——棧和遞歸遞歸函數(shù)的內(nèi)部執(zhí)行過(guò)程⑴運(yùn)行開(kāi)始時(shí)，首先為遞歸調(diào)用建立一個(gè)工作棧，其結(jié)構(gòu)包括值參、局部變量和返回地址；⑵每次執(zhí)行遞歸調(diào)用之前，把遞歸函數(shù)的值參和局部變量的當(dāng)前值以及調(diào)用后的返回地址壓棧；⑶每次遞歸調(diào)用結(jié)束后，將棧頂元素出棧，使相應(yīng)的值參和局部變量恢復(fù)為調(diào)用前的值，然后轉(zhuǎn)向返回地址指定的位置繼續(xù)執(zhí)行。3.1.3知識(shí)拓展——棧和遞歸哪些問(wèn)題可以用遞歸解決大問(wèn)題可以分解為小問(wèn)題可以確定遞歸到何時(shí)終止3.2隊(duì)列3.2.1知識(shí)學(xué)習(xí)隊(duì)列的基本概念

隊(duì)列：只允許在一端進(jìn)行插入操作，而另一端進(jìn)行刪除操作的線性表。隊(duì)尾隊(duì)頭a1a2a3入隊(duì)出隊(duì)隊(duì)列的操作特性：先進(jìn)先出constMAXSIZE=100;typedefintElemType;typedefstruct{ ElemTypedata[MAXSIZE]; intfront; intrear;}SeqQueue;隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（1）循環(huán)隊(duì)列的初始化voidInitQueue(SeqQueue&Q){Q.front=Q.rear=0;}（2）循環(huán)隊(duì)列的入隊(duì)操作voidEnQueue(SeqQueue&Q,ElemTypex){if((Q.rear+1)%MAXSIZE==Q.front) {cout<<"隊(duì)列已滿"<<endl;exit(1);}Q.rear=(Q.rear+1)%MAXSIZE; Q.data[Q.rear]=x;

}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（3）循環(huán)隊(duì)列的出隊(duì)操作ElemTypeDeQueue(SeqQueue&Q){if(Q.front==Q.rear) {cout<<"隊(duì)列已空"<<endl;exit(1);} Q.front=(Q.front+1)%MAXSIZE; ElemTypex=Q.data[Q.front];returnx;}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）（4）判斷循環(huán)隊(duì)列是否為空的操作boolQueueEmpty(SeqQueue&Q){ returnQ.front==Q.rear;}（5）判斷循環(huán)隊(duì)列是否為滿的操作boolQueueFull(SeqQueue&Q){ return(Q.rear+1)%MAXSIZE==Q.front;}隊(duì)列的順序存儲(chǔ)及基本操作（循環(huán)隊(duì)列）鏈隊(duì)列：隊(duì)列的鏈接存儲(chǔ)結(jié)構(gòu)隊(duì)頭指針即為鏈表的頭指針heada1a2an∧如何改造單鏈表實(shí)現(xiàn)隊(duì)列的鏈接存儲(chǔ)？rearfront隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）非空鏈隊(duì)列fronta1a2an∧rear空鏈隊(duì)列front∧rear隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}Node;typedefstruct{ Node*front; Node*rear;}LinkQueue;隊(duì)列的鏈?zhǔn)酱鎯?chǔ)及基本操作（鏈隊(duì)列）voidInitQueue(LinkQueue&Q){Q.front=Q.rear=newNode; Q.front->next=NULL;}front∧rear鏈隊(duì)列的操作——初始化xpfronta1an∧rearrearfrontxp∧∧rearrear算法描述：p->next=NULL;rear->next=p;rear=p;有了頭結(jié)點(diǎn)兩種情況下的處理是一致的。鏈隊(duì)列的操作——入隊(duì)∧voidEnQueue(LinkQueue&Q,ElemTypex){

Node*p=newNode;//產(chǎn)生新結(jié)點(diǎn)p p->data=x; p->next=NULL; Q.rear->next=p;//將結(jié)點(diǎn)p插入到隊(duì)尾 Q.rear=p; }鏈隊(duì)列的操作——入隊(duì)fronta1a2an∧rearp算法描述：p=front->next;front->next=p->next;鏈隊(duì)列的操作——出隊(duì)fronta1a2an∧rearp考慮邊界情況：隊(duì)列中只有一個(gè)元素？fronta1p∧rear∧rear僅1個(gè)元素的隊(duì)列判斷：if(rear==p)rear=front;如何判斷邊界情況？鏈隊(duì)列的操作——出隊(duì)ElemTypeDeQueue(LinkQueue&Q){

if(Q.front==Q.rear)

{cout<<"隊(duì)列已空"<<endl;exit(1);} Node*p=Q.front->next; ElemTypex=p->data; Q.front->next=p->next; if(Q.rear==p)

Q.r