第3章操作受限的線性表：棧和隊列導學問題1：數制轉換問題【問題描述】

已知十進制數n，試將其轉換成對應的八進制數。【分析】以n=1269為例

計算過程中，取余數的順序正好與計算產生余數的順序相反的，因此可將每次產生的余數依次保存起來，轉換結束后，再按保存的逆序取出余數打印即可。

顯然，保存的余數應該具備“后進先出”的特點，可用棧作為數據結構。導學問題2：銀行排隊問題【問題描述】

請設計一個簡單的模擬銀行排隊系統，要求程序具有三項菜單：1）取號。選擇該菜單后，為客戶產生一個排隊號。2）叫號。選擇該菜單后，顯示可服務的客戶排隊號。3）退出系統。【分析】

銀行排隊問題屬于典型的先來先服務，因此需要將產生的排隊號存放在具有“先進先出”特性的數據結構中，隊列結構可以滿足要求。

3.1棧3.1.1知識學習棧：限定僅在表尾進行插入和刪除操作的線性表。空棧：不含任何數據元素的棧。允許插入和刪除的一端稱為棧頂，另一端稱為棧底。（a1,a2,……,an）棧頂棧底abc入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖3.1棧棧的操作特性：后進先出abc入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂3.1棧棧的示意圖例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：3.1棧例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂情況2：3.1棧出棧序列：b棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。情況2：例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？3.1棧如何改造數組實現棧的順序存儲？

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

top棧的順序存儲結構及基本操作出棧：top減1進棧：top加1棧空：top=-1

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

S.top++;

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

ElemTypex=S.data[S.top];

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

returnS.data[S.top];}順序棧的實現——取棧頂元素boolStackEmpty(SeqStack&S){ returnS.top==-1;}順序棧的實現——判斷棧空boolStackEmpty(SeqStack&S){ returnS.top==MAXSIZE-1;}順序棧的實現——判斷棧滿heada1a2an∧ai鏈棧需要加頭結點嗎？如何改造鏈表實現棧的鏈接存儲？將哪一端作為棧頂？將鏈頭作為棧頂，方便操作。鏈棧不需要附設頭結點。棧的鏈式存儲及基本操作棧頂棧底鏈棧：棧的鏈接存儲結構topanan-1a1∧兩種示意圖在內存中對應同一種狀態topa1an-1an∧棧頂棧底棧的鏈式存儲及基本操作typedefintElemType;typedefstructNode{ ElemTypedata; structNode*next;}*LinkStack;鏈棧的類型定義voidInitStack(LinkStack&S){ S=NULL;}鏈棧的實現——初始化算法描述：voidPush(LinkStack&S,ElemTypex){LinkStackp=newNode;

p->data=x;

p->next=S;

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

if(S==NULL)

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

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

LinkStackp=S;

S=S->next;//刪除棧頂結點

deletep;

returnx;}Sanan-1a1∧Sp

鏈棧的實現——出棧ElemTypeTop(LinkStack&S){ if(S==NULL) {cout<<"棧已空";exit(1);} returnS->data;}鏈棧的實現——取棧頂元素boolStackEmpty(LinkStack&S){ returnS==NULL;}鏈棧的實現——判斷棧空voidDestroyListStack(LinkStack&S){LinkStackp;

while(S)

{

p=S;

S=S->next;

deletep;

}}鏈棧的實現——銷毀順序棧和鏈棧的比較時間性能：相同，都是常數時間O(1)。空間性能：順序棧：有元素個數的限制和空間浪費的問題。鏈棧：沒有棧滿的問題，只有當內存沒有可用空間時才會出現棧滿，但是每個元素都需要一個指針域，從而產生了結構性開銷。總之，當棧的使用過程中元素個數變化較大時，用鏈棧是適宜的，反之，應該采用順序棧。3.1.2知識應用——導學問題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知識拓展——算術表達式求值1、中綴表達式直接求值為實現算符優先算法，可以使用兩個工作棧：

1）運算符OPTR棧,用以寄存運算符；2）操作數OPND棧,用以寄存操作數或運算結果。算法步驟：參見教材3.1.3知識拓展——算術表達式求值2、利用后綴表達式求值

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

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

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

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

if(Q.front==Q.rear)

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

Q.r