第三章 棧和隊列

第三章棧和隊列1棧和隊列是重要的數(shù)據(jù)結構棧和隊列是線性表的子集（是插入和刪除受限的線性表）前言2【學習目標】

1.掌握棧和隊列這兩種抽象數(shù)據(jù)類型的特點，并能在相應的應用問題中正確選用它們。

2.熟練掌握棧類型的兩種實現(xiàn)方法。

3.熟練掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法。

4.理解遞歸算法執(zhí)行過程中棧的狀態(tài)變化過程。

【重點和難點】

棧和隊列是在程序設計中被廣泛使用的兩種線性數(shù)據(jù)結構，因此本章的學習重點在于掌握這兩種結構的特點，以便能在應用問題中正確使用。

3【學習指南】

在這一章中，主要是學習如何在求解應用問題中適當?shù)貞脳：完犃?，棧和隊列在兩種存儲結構中的實現(xiàn)都不難，但應該對它們了如指掌，特別要注意它們的基本操作實現(xiàn)時的一些特殊情況，如棧滿和?？?、隊滿和隊空的條件以及它們的描述方法。4【課前思考】

1.什么是線性結構？簡單地說，線性結構是一個數(shù)據(jù)元素的序列。

2.你見過餐館中一疊一疊的盤子嗎？如果它們是按1,2,…,n的次序往上疊的,那么使用時候的次序應是什么樣的？必然是依從上往下的次序，即n,…,2,1。它們遵循的是"后進先出"的規(guī)律，這正是本章要討論的"棧"的結構特點。

3.在日常生活中，為了維持正常的社會秩序而出現(xiàn)的常見現(xiàn)象是什么？是"排隊"。在計算機程序中，模擬排隊的數(shù)據(jù)結構是"隊列"。5棧必須按“后進先出”的規(guī)則進行操作隊列必須按“先進先出”的規(guī)則進行操作和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結構從“數(shù)據(jù)結構”的角度看:

它們都是線性結構，即數(shù)據(jù)元素之間的關系相同。

但它們是完全不同的數(shù)據(jù)類型。除了它們各自的基本操作集不同外，主要區(qū)別是對插入和刪除操作的"限定"。6通常稱，棧和隊列是限定插入和刪除只能在表的“端點”進行的線性表。

線性表棧隊列Insert(L,

i,x)Insert(S,n+1,x)Insert(Q,n+1,x)

1≤i≤n+1Delete(L,i)Delete(S,n)Delete(Q,1)

1≤i≤n棧和隊列是兩種常用的數(shù)據(jù)類型7

3.1

棧8

3.1.1棧的類型定義

棧（Stack）是限定只能在表的一端進行插入和刪除操作的線性表。在表中，允許插入和刪除的一端稱作“棧頂(top)”，不允許插入和刪除的一端稱作“棧底(bottom)"。9通常稱往棧頂插入元素的操作為"入棧"，稱刪除棧頂元素的操作為"出棧"。因為后入棧的元素先于先入棧的元素出棧，故被稱為是一種"后進先出"的結構，因此又稱LIFO（LastInFirstOut的縮寫）表。很多書上都以如下圖所示的鐵路調度站形象地表示棧的這個特點。

10棧的類型定義

ADTStack{

數(shù)據(jù)對象：

D＝{ai|ai

∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關系：

R1＝{<ai-1,ai>|ai-1,ai∈D,i=2,...,n}

約定an

端為棧頂，a1端為棧底?；静僮鳎?/p>

}ADTStack11InitStack(&S)DestroyStack(&S)ClearStack(&S)StackEmpty(S)StackLength(S)GetTop(S,&e)Push(&S,e)Pop(&S,&e)StackTravers(S,visit())12

InitStack(&S)

操作結果：構造一個空棧S。

DestroyStack(&S)

初始條件：棧S已存在。

操作結果：棧S被銷毀。13StackEmpty(S)

初始條件：棧S已存在。

操作結果：若棧S為空棧，則返回

TRUE，否則FALSE。

判定棧是否為空棧是棧在應用程序

中經(jīng)常使用的操作，通常以它作為循環(huán)結束的條件。14

StackLength(S)

初始條件：棧S已存在。

操作結果：返回S的元素個數(shù)，

即棧的長度。15GetTop(S,&e)

初始條件：棧S已存在且非空。

操作結果：用e返回S的棧頂元素,并

不將它從棧中刪除。

a1a2an……e16ClearStack(&S)

初始條件：棧S已存在。

操作結果：將

S清為空棧。

17Push(&S,e)

初始條件：棧S已存在。

操作結果：插入元素e為新的棧

頂元素。

a1a2ane……18Pop(&S,&e)

初始條件：棧S已存在且非空。

操作結果：刪除S的棧頂元素，

并用e返回其值。a1a2anan-1

……e19StackTraverse(S,visit())初始條件：棧S已存在且非空，visit()為元素的訪問函數(shù)。

操作結果：從棧底到棧頂依次對S的每個元素調用函數(shù)visit()，一旦

visit()失敗，則操作失敗。

這是對棧進行從棧底到棧頂?shù)摹氨闅v”操作，應用較多的場合是，輸出棧中所有數(shù)據(jù)元素。

20順序棧3.1.2棧的表示和實現(xiàn)類似于線性表的順序映象實現(xiàn)，指向表尾的指針可以作為棧頂指針。//-----棧的順序存儲表示

-----#defineSTACK_INIT_SIZE100;#defineSTACKINCREMENT10;

typedef

struct{

SElemType*base;

SElemType*top;

int

stacksize;}SqStack;21實現(xiàn)：一維數(shù)組s[M]top123450進棧A棧滿BCDEF設數(shù)組維數(shù)為Mtop=base,?？?此時出棧,則下溢（underflow)top=M,棧滿,此時入棧,則上溢（overflow)toptoptoptoptop123450空棧topbasebasetop出棧toptop?？誦ase棧底指針base,始終指向棧底位置；棧頂指針top,其初值指向棧底，始終在棧頂元素的下一個位置123450ABtop22

StatusInitStack(SqStack&S){//構造一個空棧SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base;

S.stacksize=STACK_INIT_SIZE;returnOK;}23

StatusPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){//棧滿，追加存儲空間

S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*

sizeof(SElemType));if(!S.base)exit(OVERFLOW);//存儲分配失敗

S.top=S.base+S.stacksize;

S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK;}24StatusPop(SqStack&S,SElemType&e){//若棧不空，則刪除S的棧頂元素，

//用e返回其值，并返回OK；

//否則返回ERRORif(S.top==S.base)returnERROR;e=*--S.top;returnOK;}25在一個程序中同時使用兩個棧：0M-1棧1底棧1頂棧2底棧2頂263.2棧的應用舉例由于棧的操作具有后進先出的固有特性，致使棧成為程序設計中的有用工具。凡應用問題求解的過程具有"后進先出"的天然特性的話，則求解的算法中也必然需要利用"棧"。27棧的應用舉例例一、數(shù)制轉換例二、括號匹配的檢驗例三、行編輯程序問題例四、迷宮求解例五、表達式求值例六、實現(xiàn)遞歸28例一、數(shù)制轉換

十進制數(shù)N和其他d進制數(shù)的轉換是

計算機實現(xiàn)計算的基本問題，其解決方

法很多，其中一個簡單算法基于下列原

理：

N=(Ndivd)×d+Nmodd

(其中：div為整除運算，mod為求余運算)29

NNdiv8Nmod8

13481684

168210

2125

202計算順序輸出順序例如：（1348)10=(2504)8，

其運算過程如下：30voidconversion(){

InitStack(S);//構造空棧

scanf("%d",&N);//輸入一個十進制數(shù)

while(N){Push(S,N%8);//"余數(shù)"入棧

N=N/8;

//非零"商"繼續(xù)運算

}while(!StackEmpty(S)){

//和"求余"所得相逆的順序輸出八進制的各位數(shù)

Pop(S,&e);

printf("%d",e);}}//conversion31例二、括號匹配的檢驗假設在表達式中［］（））或［（［］［］）］等為正確的格式，［（］）或（［]（）或（（）））均為不正確的格式。則檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。32

即后出現(xiàn)的"左括弧"，它等待與其匹配的"右括弧"出現(xiàn)的"急迫"心情要比先出現(xiàn)的左括弧高。換句話說，對"左括弧"來說，后出現(xiàn)的比先出現(xiàn)的"優(yōu)先"等待檢驗，對"右括弧"來說，每個出現(xiàn)的右括弧要去找在它之前"最后"出現(xiàn)的那個左括弧去匹配。顯然，必須將先后出現(xiàn)的左括弧依次保存，為了反映這個優(yōu)先程度，保存左括弧的結構用棧最合適。這樣對出現(xiàn)的右括弧來說，只要"棧頂元素"相匹配即可。如果在棧頂?shù)哪莻€左括弧正好和它匹配，就可將它從棧頂刪除。

33分析可能出現(xiàn)的不匹配的情況:到來的右括弧并非是所“期待”的；例如：考慮下列括號序列：

[([][])]12345678到來的是“不速之客”；直到結束，也沒有到來所“期待”的括弧。34這三種情況對應到棧的操作即為：

1．和棧頂?shù)淖罄ɑ〔幌嗥ヅ洌?/p>

2．棧中并沒有左括弧等在哪里；

3．棧中還有左括弧沒有等到和它 相匹配的右括弧。35算法的設計思想：1）凡出現(xiàn)左括弧，則進棧；2）凡出現(xiàn)右括弧，首先檢查棧是否空

若?？眨瑒t表明該“右括弧”多余，

否則和棧頂元素比較，

若相匹配，則“左括弧出?！保?/p>

否則表明不匹配。3）表達式檢驗結束時，

若?？眨瑒t表明表達式中匹配正確，

否則表明“左括弧”有余。36Statusmatching(charexp[]){

intstate=1;while(i<=Length(exp)&&state){switchexp[i]{case'('||'['

:{Push(S,exp[i]);i++;break;}case')'

:{if(！StackEmpty(S)&&GetTop(S)=‘(’

){Pop(S,e);i++;}else{state=0;}break;}case‘]'

:{if(！StackEmpty(S)&&GetTop(S)=‘['）

{Pop(S,e);i++;}else{state=0;}break;}}if(StackEmpty(S)&&state)returnOK;…...37例三、行編輯程序問題如何實現(xiàn)？“每接受一個字符即存入存儲器”?并不恰當！38設立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū),并假設“#”為退格符，“@”為退行符。在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。合理的作法是：39假設從終端接受了這樣兩行字符：

whli##ilr#e（s#*s)

outcha@putchar(*s=#++);則實際有效的是下列兩行：

while(*s)

putchar(*s++);40可設這個輸入緩沖區(qū)為一個棧結構，每當從終端接受了一個字符之后先作如下判斷：

1、既不是退格也不是退行符，則將該字符壓入棧頂；

2、如果是一個退格符，則從棧頂刪去一個字符；

3、如果是一個退行符，則將字符棧清為空棧。41

while(ch!=EOF&&ch!='\n'){ switch(ch){case‘#’:Pop(S,c);break;//棧非空，退棧

case'@':ClearStack(S);break;//重置S為空棧

default:Push(S,ch);break;//未考慮棧滿

}

ch=getchar();//從終端接收下一個字符

}ClearStack(S);//重置S為空棧if(ch!=EOF)ch=getchar();}

ch=getchar();

ClearStack(S);//重置S為空棧

while(ch!=EOF){//EOF為全文結束符將從棧底到棧頂?shù)淖址麄魉椭琳{用過程的數(shù)據(jù)區(qū)；42例四、迷宮求解通常用的是“窮舉求解”的方法43

為了保證在任何位置上都能沿原路退回,需要用一個“后進先出”的結構即棧來保存從入口到當前位置的路徑。并且在走出出口之后,棧中保存的正是一條從入口到出口的路徑所謂“下一位置”指的是“當前位置”四周四個方向（東、南、西、北）上相鄰的方塊。假設以棧S記錄“當前路徑”，則棧頂中存放的是“當前路徑上最后一個通道塊”。

“納入路徑”的操作即為“當前位置入棧；

“從當前路徑上刪除前一通道塊”的操作即為"出棧"。44迷宮路徑算法的基本思想：若當前位置“可通”,則納入路徑，繼續(xù)前進;若當前位置“不可通”,則后退,換方向繼續(xù)探索;若四周“均無通路”,則將當前位置從路徑中刪除出去。45設定當前位置的初值為入口位置；

do｛

若當前位置可通，則｛將當前位置插入棧頂；

若該位置是出口位置，則算法結束；

否則切換當前位置的東鄰方塊為新的當前位置；

}

否則

{

若棧不空且棧頂位置尚有其他方向未被探索，求迷宮中一條從入口到出口的路徑的算法：46

則設定新的當前位置為:沿順時針方向轉找到的棧頂位置的下一相鄰塊；

若棧不空但棧頂位置的四周均不可通，則{刪去棧頂位置；//從路徑中刪去該通道塊

若棧不空，則重新測試新的棧頂位置，直至找到一個可通的相鄰塊或出棧至棧空；

}

}

}while(棧不空)；若?？?，則表明迷宮沒有通路。47例五、表達式求值任何一個表達式都是由操作數(shù)(operand)、運算符(operator)和界限符(delimiter)組成。

操作數(shù)可以是常數(shù)也可以是被說明為變量或常量的標識符；

運算符可以分為算術運算符、關系運算符和邏輯運算符等三類；

基本界限符有左右括弧和表達式結束符等。48

限于二元運算符的表達式定義:

Exp=S1OPS2

操作數(shù):變量、常量、表達式運算符:算術運算符、關系運算符、邏輯運算符界限符：括號、結束符表達式求值49

表達式的三種標識方法：設Exp=S1+OP+S2則稱OP+S1+S2為前綴表示法

S1+OP+S2為中綴表示法

S1+S2+OP為后綴表示法50算術四則運算的規(guī)則：先乘除，后加減從左算到右先括號內，后括號外運算符和界限符通稱為算符。兩個算符和之間的優(yōu)先關系：，的優(yōu)先權低于；，的優(yōu)先權等于；，的優(yōu)先權高于。51規(guī)則注意：＋、-、×、/為時，優(yōu)先權均低于“（”，但均高于“）”；時，令，“#”是表達式的結束符；表中的“（”與“）”相遇時，括號內的運算完成；當“#”遇到“#”時，表達式求值完成當輸入的運算符優(yōu)先權高于棧頂運算符時，運算符入棧52中綴表達式求值基本算法思想：置操作數(shù)棧為空棧，表達式起始符“#”為運算符棧底元素；依次讀入表達式中每個字符，若是操作數(shù)則進OPND棧，若是運算符棧則和OPTR棧的棧頂運算符比較優(yōu)先權后作相應操作，直至整個表達式求值完畢（即OPTR棧的的棧頂元素和當前讀入的字符均為“#”）。定義兩個工作棧：一個為OPTR，寄存運算符；一個為OPND，寄存操作數(shù)或運算結果。53例：3*(7–2)

OPTR棧OPND棧輸入操作1# 3*(7–2)# PUSH(OPND,‘3’)2#3*(7–2)#PUSH(OPTR,‘*’)3#*3(7–2)#PUSH(OPTR,‘(’)4#*(37–2)#PUSH(OPND,‘7’)5#*(37–2)#PUSH(OPTR,‘–’)6#*(–372)#PHSH(OPND,‘2’)7#*(–372)#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR)9#*35#operate(‘3’,‘*’,‘5’)10#15#returnGetTop(OPND)54OperandType

EvaluateExpression(){//設OPTR和OPND分別為運算符棧和運算數(shù)棧//OP為運算符集合。

InitStack(OPTR);Push(OPTR,'#');

initStack(OPND);c=getchar();

while(c!='#'||GetTop(OPTR)!='#'){if(!In(c,OP))//不是運算符則進棧

{Push((OPND,c);c=getchar();}else

}//whilereturnGetTop(OPND);}//EvaluateExpression……55switch(precede(GetTop(OPTR),c){case'<'://棧頂元素優(yōu)先權低

Push(OPTR,c);c=getchar();break;case'='://脫括號并接收下一字符

Pop(OPTR,x);c=getchar();break;case'>'://退棧并將運算結果入棧

Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b));break;}//switch56

OPTR為運算符的集合，若ch是運算符，則函數(shù)IN(ch,OP)的值為“TRUE”。若c(棧頂運算符)的優(yōu)先性高于棧頂運算符，則函數(shù)precede(GetTop（OPTR),c)值為“>"?！?/p>

算法的時間復雜度為O(n)，其中n為表達式字符串的長度。57

ADTQueue{

數(shù)據(jù)對象：

D＝{ai|ai∈ElemSet,i=1,2,...,n,n≥0}

數(shù)據(jù)關系：

R1＝{<ai-1,ai>|ai-1,ai

∈D,i=2,...,n}

約定其中a1

端為隊列頭，an

端為隊列尾基本操作：3.4隊列的類型定義}

ADTQueue58隊列的基本操作：

InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)QueueLength(Q)GetHead(Q,&e)ClearQueue(&Q)DeQueue(&Q,&e)EnQueue(&Q,e)QueueTravers(Q,visit())59InitQueue(&Q)

操作結果：構造一個空隊列Q。

DestroyQueue(&Q)

初始條件：隊列Q已存在。

操作結果：隊列Q被銷毀，不再存在。

60QueueEmpty(Q)

初始條件:隊列Q已存在。

操作結果:若Q為空隊列,則返回TRUE，

否則返回FALSE。QueueLength(Q)

初始條件:隊列Q已存在。

操作結果:返回Q的元素個數(shù)，即隊列

的長度。61

GetHead(Q,&e)

初始條件：Q為非空隊列。

操作結果：用e返回Q的隊頭元素。a1a2an……62

ClearQueue(&Q)

初始條件：隊列Q已存在。

操作結果：將Q清為空隊列。63EnQueue(&Q,e)

初始條件:隊列Q已存在。

操作結果:插入元素e為Q的新的隊尾元素。a1a2ane……64

DeQueue(&Q,&e)

初始條件：Q為非空隊列。

操作結果：刪除Q的隊頭元素，并用e返

回其值。a1a2an……653.5隊列類型的實現(xiàn)鏈隊列——鏈式映象循環(huán)隊列——順序映象66

typedef

struct

QNode{//結點類型

QElemTypedata;

struct

QNode*next;}QNode,*QueuePtr;鏈隊列——鏈式映象67typedef

struct{//鏈隊列類型

QueuePtrfront;//隊頭指針

QueuePtrrear;//隊尾指針}LinkQueue;a1∧anQ.frontQ.rearQ.frontQ.rear∧空隊列68

StatusInitQueue(LinkQueue&Q){//構造一個空隊列Q

Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode));if(!Q.front)exit(OVERFLOW);//存儲分配失敗

Q.front->next=NULL;returnOK;}69

StatusEnQueue(LinkQueue&Q,

QElemTypee){//插入元素e為Q的新的隊尾元素

p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(OVERFLOW);//存儲分配失敗

p->data=e;p->next=NULL;Q.rear->next=p;Q.rear=p;returnOK;}70

StatusDeQueue(LinkQueue&Q,

QElemType&e){//若隊列不空，則刪除Q的隊頭元素，//用e返回其值，并返回OK；否則返回ERRORif(Q.front==Q.rear)returnERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}71循環(huán)隊列——順序映象初始化建空隊列時，令front=rear=0，每當插入一個新的隊尾元素后，尾指針增1；每當刪除一個隊頭元素之后，頭指針front增1。因此，在非空隊列中，頭指針始終指向隊頭元素，而尾指針指向隊尾元素的"下一個"位置。如下圖所示。72實現(xiàn)：用一維數(shù)組實現(xiàn)sq[M]123450空隊列rear=0front=0J1J2J3rearrear123450J4,J5,J6入隊J4J5J6frontrearrear123450frontJ1,J1,J3入隊rear123450J1,J2,J3出隊J1J2J3frontfrontfront存在問題：當front=0,rear=M時再有元素入隊發(fā)生溢出——真溢出當front≠0,rear=M時再有元素入隊發(fā)生溢出——假溢出rear73解決方案隊首固定，每次出隊剩余元素向下移動——浪費時間循環(huán)隊列基本思想：把隊列設想成環(huán)形，讓sq[0]接在sq[M-1]之后，若rear+1==M,則令rear=0;實現(xiàn)：利用“模”運算入隊：base[rear]=x;rear=(rear+1)%M;出隊：x=base[front];front=(front+1)%M;隊滿、隊空判定條件74012345rearfrontJ5J6J7012345rearfrontJ4J9J8J4,J5,J6出隊J7,J8,J9入隊隊空：front==rear隊滿：front==rear解決方案：1.另外設一個標志位以區(qū)別隊空、隊滿2.少用一個元素空間：隊空：front==rear隊滿：(rear+1)%M==front3.使用一個計數(shù)器記錄隊列中元素的總數(shù)J5J6012345rearfront初始狀態(tài)J475循環(huán)隊列－隊列的順序表示和實現(xiàn)

#defineMAXQSIZE100//最大隊列長度

typedef

struct{

QElemType*base;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向

//隊列尾元素的下一個位置}SqQueue;76

StatusInitQueue(SqQueue&Q){//構造一個空隊列QQ.base=(QElemType*)malloc

(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存儲分配失敗

Q.front=Q.rear=0;returnOK;}第二種解決方案，占用一個元素空間77StatusEnQueue(SqQueue&Q,QElemTypee){//插入元素e為Q的新的隊尾元素

if((Q.rear+1)%MAXQSIZE==Q.front)

returnERROR;//隊列滿

Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;returnOK;}第二種解決方案，占用一個元素空間78

StatusDeQueue(SqQueue&Q,QElemType&e){//若隊列不空，則刪除Q的隊頭元素，

//用e返回其值，并返回OK;否則返回//ERRORif(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}第二種解決方案，占用一個元素空間79

#defineMAXQSIZE100//最大隊列長度

typedef

struct{

QElemType*base;//動態(tài)分配存儲空間

intfront;//頭指針，若隊列不空，

//指向隊列頭元素

intrear;//尾指針，若隊列不空，指向

//隊列尾元素的下一個位置}SqQueue;循環(huán)隊列——順序映象第一種解決方案：設標志

int

emptyflag;//隊列空的標志，空為180

StatusInitQueue(SqQueue&Q){//構造一個空