第3章 棧與隊列

1、棧和隊列是操作受限的線性表。棧：后進先出；隊列：先進先出。 線性表線性表 棧棧 隊列隊列Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊列是兩種常用的數(shù)據(jù)類型棧和隊列是兩種常用的數(shù)據(jù)類型3.1 棧棧3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 棧與遞歸實現(xiàn)棧與遞歸實現(xiàn)3.4 隊列隊列3.1.1 棧的抽象數(shù)據(jù)類型定義棧的抽象數(shù)據(jù)類型定義3.1.2 棧的表示與實現(xiàn)棧的表示與實現(xiàn)3.1 棧棧 ADT Stack 數(shù)據(jù)對象數(shù)據(jù)對象： D ai | ai

2、 ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定an 端為棧頂，a1 端為棧底。 基本操作：基本操作： ADT Stack3.1.1 棧的抽象數(shù)據(jù)類型定義棧的抽象數(shù)據(jù)類型定義InitStack(&S)DestroyStack(&S)StackEmpty(S)GetTop(S, &e)Push(&S, e)Pop(&S, &e) InitStack(&S) 操作結(jié)果：構(gòu)造一個空棧 S。 DestroyStack(&S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷毀。StackEmpty(S)初始條件：棧 S 已存在。

3、 操作結(jié)果：若棧 S 為空棧，則返回 TRUE，否則 FALE。 GetTop(S, &e) 初始條件：棧 S 已存在且非空。操作結(jié)果：用 e 返回 S 的棧頂元素。a1a2an Push(&S, e) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 e 為新的棧頂元素。a1a2ane Pop(&S, &e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。a1a2anan-1 3.1.2 棧的表示與實現(xiàn)棧的表示與實現(xiàn)1.順序棧順序棧2.鏈鏈 棧棧/- 順序棧的類型描述順序棧的類型描述 - #define STACK_INIT_SIZE 100; type

4、def int ElemType; typedef struct ElemType *data; int top; int stacksize; SqStack; 利用順序存儲方式實現(xiàn)的棧稱為順序棧。 通常將數(shù)組的0下標作為棧底，這樣空棧時棧頂指針top=-1；進棧時，棧頂指針加1，即top+；出棧時，棧頂指針減1，即top-。棧操作的示意圖如圖3-1所示。top=-1top1234567890（1）空棧atop=0top1234567890（2）1個元素edcbatop=4top1234567890（3）5個元素edcbatop=2top1234567890（4）3個元素圖3-1 棧頂指針t

5、op與棧中元素的關(guān)系 int InitStack (SqStack &S) / 構(gòu)造一個最大空間為 STACK_INIT_SIZE的空順序棧 S S.data = new ElemTypeSTACK_INIT_SIZE; if (!S.data) exit (OVERFLOW); /存儲分配失敗 S.top = -1; S.stacksize = STACK_INIT_SIZE; return OK; int Push (SqStack &S, ElemType e) / 若棧不滿，則將e插入棧頂 if (S.top = S.stacksize-1) /棧滿 return OVERFLOW;

6、S.data+S.top= e; return OK;int Pop (SqStack &S, ElemType &e) / 若棧不空，則刪除S的棧頂元素， / 用 e 返回其值，并返回OK； / 否則返回ERROR if (S.top = -1) return ERROR; e = S.dataS.top-; return OK;Elemtype GetTop (SqStack S) /棧已存在且不空，返回棧頂元素 if (S.top = -1) return ERROR; return S.dataS.top;int StackEmpty (SqStack S) /判棧是否為空棧 if (

7、S.top = -1) return OK; return ERROR; 需要注意的是，對順序棧，入棧時應(yīng)首先判斷棧是否滿了，棧滿的條件是S.top=S.stacksize-1。棧滿時，不能入棧，否則將出現(xiàn)空間溢出，引起錯誤，這種現(xiàn)象稱為上溢。解決的辦法是追加存儲空間。出棧和讀取棧頂元素時，應(yīng)先判斷棧是否為空，為空時不能操作，否則將產(chǎn)生錯誤，通常棧空作為控制轉(zhuǎn)移的條件。鏈棧鏈棧 用鏈式存儲結(jié)構(gòu)實現(xiàn)的棧稱為鏈棧。通常鏈棧用單鏈表表示，因此其結(jié)點結(jié)構(gòu)與單鏈表的結(jié)點結(jié)構(gòu)相同。在此用LinkStack表示，即有：typedef struct node ElemType data; struct nod

8、e *next; StackNode,*LinkStack;LinkList top;a1an-1an-2an棧頂棧底圖3-2 鏈棧示意圖 因為棧中的主要運算是在棧頂插入、刪除，顯然在鏈表的頭部做棧頂是最方便的，而且沒有必要象單鏈表那樣為了運算方便附加一個頭結(jié)點。如圖3-2： void InitStack (LinkStack &top) / 構(gòu)造一個空順序棧 ，棧頂指針top top=NULL; int Push (LinkStack &top, ElemType x) S=new StackNode; if (!S)exit(OVERFLOW); S-data=x;S-next=top;t

9、op=s; return OK;int Pop (LinkStack &top, ElemType &x) if (S.top = NULL) return ERROR; else x = top-data; p=top; top=top-next; delete p; return OK; int StackEmpty (ListStack S) /判棧是否為空棧 if (S.top = NULL) return OK; return ERROR;3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗括號匹配的檢驗3.2.3 表達式求值表達式求值3.2.4 命

10、題公式求值命題公式求值3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換 算法基于原理： N = (N div d)d + N mod d 例如：例如：（1348)10 = (2504)8 ，其運算過程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2計算順序計算順序輸出順序輸出順序void conversion () InitStack(S); scanf (%d,&N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conve

11、rsion3.2.2 括號匹配的檢驗括號匹配的檢驗假設(shè)在表達式中 （）或（ ）等為正確的格式， （ ）或（ ）或 ( )均為不正確的格式。則 檢驗括號是否匹配的方法可用“期待的急迫程度”這個概念來描述。分析可能出現(xiàn)的不匹配不匹配的情況: 到來的右括弧非是所“期待”的;例如：考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8 到來的是“不速之客”; 直到結(jié)束，也沒有到來所“期待”的括弧;算法的設(shè)計思想：算法的設(shè)計思想：1）凡出現(xiàn)左括弧左括弧，則進棧進棧；2）凡出現(xiàn)右括弧右括弧，首先檢查棧是否空 若?？諚？眨瑒t表明該“右括弧右括弧”多余多余 否則和棧頂元素和棧頂元素比較， 若相匹配相匹配，

12、則“左括弧出棧左括弧出棧” 否則表明不匹配不匹配3）表達式表達式檢驗結(jié)束時結(jié)束時， 若?？諚？?，則表明表達式中匹配正確匹配正確 否則表明“左括弧左括弧”有余有余int matching(char exp) int state = 1;i=0;InitStack(S); while (i=0&*exp=0&*exp=9);Suffixi+=$; /操作數(shù)之間的間隔符操作數(shù)之間的間隔符switch (*exp) case ( : Push(OPTR, *exp); break; case ) : Pop(OPTR, ch); while (ch!= ( ) Suffixi+=ch; Pop(OPT

13、R,ch) break; defult : while(precede(GetTop(OPTR),*exp)!=0&*Suffixnext=NULL)printf(L-data); else FindLastElem(L-next); 某些問題本身沒有明顯的遞歸結(jié)某些問題本身沒有明顯的遞歸結(jié)構(gòu)，但也用遞歸來求，甚至有些問題構(gòu)，但也用遞歸來求，甚至有些問題只能用遞歸求解。一個典型的例子就只能用遞歸求解。一個典型的例子就是是Hanoi塔問題。塔問題。3.3.2棧與遞歸的關(guān)系棧與遞歸的關(guān)系 將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存; 為被調(diào)用函數(shù)的局部變量分配存儲區(qū); 將控制轉(zhuǎn)移到被調(diào)用

14、函數(shù)的入口。 當在一個函數(shù)的運行期間調(diào)用另一個函數(shù)時，在運行該被調(diào)用函數(shù)之前，需先完成三項任務(wù)：保存被調(diào)函數(shù)的計算結(jié)果;釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū);依照被調(diào)函數(shù)保存的返回地址將控制轉(zhuǎn)移到調(diào)用函數(shù)。從被調(diào)用函數(shù)返回返回調(diào)用函數(shù)之前之前，應(yīng)該完成下列三項任務(wù)：多個函數(shù)嵌套調(diào)用的規(guī)則是:此時的內(nèi)存管理實行“棧式管理棧式管理”后調(diào)用先返回后調(diào)用先返回 ！遞歸工作棧：遞歸工作棧：遞歸過程執(zhí)行過程中占用的 數(shù)據(jù)區(qū)。遞歸工作記錄：遞歸工作記錄：每一層的遞歸參數(shù)合成 一個記錄。當前活動記錄：當前活動記錄：棧頂記錄指示當前層的 執(zhí)行情況。當前環(huán)境指針：當前環(huán)境指針：遞歸工作棧的棧頂指針。void hanoi (int

15、 n, char x, char y, char z) / 將塔座x上按直徑由小到大且至上而下編號為1至n/ 的n個圓盤按規(guī)則搬到塔座z上，y可用作輔助塔座。1 if (n=1)2 move(x, 1, z); / 將編號為的圓盤從x移到z3 else 4 hanoi(n-1, x, z, y); / 將x上編號為至n-1的 /圓盤移到y(tǒng), z作輔助塔5 move(x, n, z); / 將編號為n的圓盤從x移到z6 hanoi(n-1, y, x, z); / 將y上編號為至n-1的 /圓盤移到z, x作輔助塔7 8 3.3.3遞歸的實現(xiàn)遞歸的實現(xiàn)8 3 a b c返址 n x y z5 2

16、 a c b5 1 a b cvoid hanoi (int n, char x, char y, char z) 1 if (n=1)2 move(x, 1, z); 3 else 4 hanoi(n-1, x, z, y); 5 move(x, n, z); 6 hanoi(n-1, y, x, z); 7 8 7 1 c a b3.3.4用遞歸求所以出棧序列用遞歸求所以出棧序列 問題：問題：當序列當序列1，2，n， 依依次入棧，請問如何求出其所有可能的次入棧，請問如何求出其所有可能的出棧序列？出棧序列？ 下面給出求所有出棧序列的遞歸下面給出求所有出棧序列的遞歸算法的描述及算法：算法的描述

17、及算法： (1)若若n=1，則寫下唯一的出棧序，則寫下唯一的出棧序列；列； (2)否則，遞歸的調(diào)用該算法求出否則，遞歸的調(diào)用該算法求出第一個元素第一個元素1作為第作為第k個元素的所有出個元素的所有出棧序列棧序列(k =1，2， )。3.3.5遞歸的消除遞歸的消除 研究遞歸消除的主要原因有以下兩個研究遞歸消除的主要原因有以下兩個方面：第一，遞歸消除有利于提高算法的方面：第一，遞歸消除有利于提高算法的時空性能。在一般情況下，一個遞歸算法時空性能。在一般情況下，一個遞歸算法的時空性能相對較差，而非遞歸算法的時的時空性能相對較差，而非遞歸算法的時空性能要高得多。第二，研究遞歸消除有空性能要高得多。第二

18、，研究遞歸消除有助于透徹理解遞歸機制，而這種理解是熟助于透徹理解遞歸機制，而這種理解是熟練掌握遞歸程序設(shè)計技能的必要前提。練掌握遞歸程序設(shè)計技能的必要前提。 根據(jù)是否需要引入工作棧作為控制機根據(jù)是否需要引入工作棧作為控制機構(gòu)，可將遞歸消除技術(shù)分成兩類并分別加構(gòu)，可將遞歸消除技術(shù)分成兩類并分別加以討論。以討論。 1.簡單遞歸消除簡單遞歸消除(尾遞歸和單向遞歸消尾遞歸和單向遞歸消除除) 尾遞歸是指遞歸調(diào)用語句只有一個，尾遞歸是指遞歸調(diào)用語句只有一個，而且是處于算法的最后而且是處于算法的最后。 單向遞歸是指遞歸函數(shù)中雖然有一單向遞歸是指遞歸函數(shù)中雖然有一處以上的遞歸調(diào)用語句，但各次遞歸調(diào)用處以上的遞

19、歸調(diào)用語句，但各次遞歸調(diào)用語句的參數(shù)只和主調(diào)用函數(shù)有關(guān)，相互之語句的參數(shù)只和主調(diào)用函數(shù)有關(guān)，相互之間參數(shù)無關(guān)，并且這些遞歸調(diào)用語句也和間參數(shù)無關(guān)，并且這些遞歸調(diào)用語句也和尾遞歸一樣處于算法的最后尾遞歸一樣處于算法的最后。 這類遞歸算法可以不使用工作棧作這類遞歸算法可以不使用工作棧作為控制機構(gòu)而直接轉(zhuǎn)換成循環(huán)算法為控制機構(gòu)而直接轉(zhuǎn)換成循環(huán)算法。 2.基于棧的遞歸消除基于棧的遞歸消除 在復雜情況下，一個遞歸算法無法直在復雜情況下，一個遞歸算法無法直接轉(zhuǎn)換成循環(huán)算法。例如，前面介紹的接轉(zhuǎn)換成循環(huán)算法。例如，前面介紹的Hanoi問題。在這種情況下，通常通過引問題。在這種情況下，通常通過引入一個工作棧保

20、存入一個工作棧保存“返回位置返回位置”以實現(xiàn)過以實現(xiàn)過程調(diào)用一返回控制程調(diào)用一返回控制。3.4 隊列隊列3.4.1隊列的抽象數(shù)據(jù)類型定義隊列的抽象數(shù)據(jù)類型定義3.4.2隊列的鏈式表示與實現(xiàn)隊列的鏈式表示與實現(xiàn)3.4.3循環(huán)隊列循環(huán)隊列3.4.4隊列的應(yīng)用舉例隊列的應(yīng)用舉例 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： Dai | aiElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, ai D, i=2,.,n 約定其中a1 端為隊列頭隊列頭， an 端為隊列尾隊列尾基本操作：基本操作：3.4.1隊列的抽象數(shù)據(jù)類型定義隊列的抽象數(shù)據(jù)類型定義 ADT Queue

21、隊列的基本操作：隊列的基本操作： InitQueue(&Q)DestroyQueue(&Q)QueueEmpty(Q)GetHead(Q, &e)DeQueue(&Q, &e)EnQueue(&Q, e)InitQueue(&Q) 操作結(jié)果：操作結(jié)果：構(gòu)造一個空隊列Q。DestroyQueue(&Q)初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：隊列Q被銷毀， 不再存在。 QueueEmpty(Q)初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：若Q為空隊列，則返回TRUE，否則返回FALSE。 GetHead(Q, &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作

22、結(jié)果：用e返回Q的隊頭元素。a1a2an EnQueue(&Q, e) 初始條件：初始條件：隊列Q已存在。 操作結(jié)果：操作結(jié)果：插入元素e為Q的新的隊尾元素。a1a2ane DeQueue(&Q, &e) 初始條件：初始條件：Q為非空隊列。 操作結(jié)果：操作結(jié)果：刪除Q的隊頭元素，并用e返回其值。a1a2an 3.4.2 隊列的鏈式表示與實現(xiàn)隊列的鏈式表示與實現(xiàn) 隊列(Queue)是一種先進先出(first in first out，F(xiàn)IFO)的線性表，它只允許在表的一端進行插入操作，而在另一端進行刪除操作。允許插入的一端稱為隊尾(rear)，允許刪除的一端則稱為隊頭(front)。a1anan

23、-1Q.frontQ.erar圖3-4 鏈隊列示意圖隊頭隊尾Q.frontQ.rear(1)空隊列Q.frontQ.rearbaQ.frontQ.rear(2)元素a入隊列aQ.frontQ.rearab(3)元素b入隊列(4)元素a出隊列圖3-5 隊列運算指針變化情況 typedef struct QNode / 結(jié)點類型結(jié)點類型 ElemType data; struct QNode *next; QNode, *QueuePtr;typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針

24、 LinkQueue; int InitQueue (LinkQueue &Q) / 構(gòu)造一個空隊列Q Q.front = Q.rear = new QNode; if (!Q.front) exit (OVERFLOW); /存儲分配失敗 Q.front-next = NULL; return OK; int DestryQueue (LinkQueue &Q) / 銷毀隊列Q while(Q.front) Q.rear=Q.front-next; delete Q.front; Q.front=Q.rear; return OK; int EnQueue (LinkQueue &Q, El

25、emType e) / 插入元素e為Q的新的隊尾元素 p = new QNode; if (!p) exit (OVERFLOW); /存儲分配失敗 p-data = e; p-next = NULL; Q.rear-next = p; Q.rear = p; return OK;a1anQ.frontQ.rearep int DeQueue (LinkQueue &Q, ElemType &e) / 若隊列不空，則刪除Q的隊頭元素， /用 e 返回其值，并返回OK；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next;

26、e = p-data; Q.front-next = p-next; delete (p); return OK;if (Q.rear = p) Q.rear = Q.front;#define MAXSIZE 100 /最大隊列長度typedef struct ElemType *base; / 動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空， / 指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向 / 隊列尾元素 的下一個位置 SqQueue;3.4.3循環(huán)隊列循環(huán)隊列順序映象012345Q.frontQ.rearabcd圖3-6 循環(huán)隊列示意圖 int In

27、itQueue (SqQueue &Q) / 構(gòu)造一個最大存儲空間為 maxsize 的 / 空循環(huán)隊列 Q Q.base = new ElemTypeMAXSIZE; if (!Q.base) exit (OVERFLOW); Q.front = Q.rear = 0; return OK; int QueueLength (SqQueue Q) / 求循環(huán)隊列 的長度 return (Q.rear-Q.front+ maxsize)% maxsize; int EnQueue (SqQueue &Q, ElemType e) / 插入元素e為Q的新的隊尾元素 if (Q.rear+1) %

28、 Q.maxsize = Q.front) return ERROR; /隊列滿 Q.baseQ.rear = e; Q.rear = (Q.rear+1) % Q.maxsize; return OK; int DeQueue (SqQueue &Q, ElemType &e) / 若隊列不空，則刪除Q的隊頭元素， / 用e返回其值，并返回OK; 否則返回ERROR if (Q.front = Q.rear) return ERROR; e = Q.baseQ.front; Q.front = (Q.front+1) % maxsize; return OK;3.4.4 隊列應(yīng)用舉例隊列應(yīng)用

29、舉例 假設(shè)在周末舞會上，男士和女士進假設(shè)在周末舞會上，男士和女士進入舞廳時，各自排成一隊。跳舞開始時入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭各自出一個，依次從男隊和女隊的隊頭各自出一個人配成舞伴。若兩隊初始人數(shù)不相同，人配成舞伴。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一支則較長的那一隊中未配對者等待下一支舞曲?，F(xiàn)要求寫一算法模擬上述舞伴配舞曲。現(xiàn)要求寫一算法模擬上述舞伴配對問題。對問題。 由于先入隊的男士或女士亦先出隊配成舞由于先入隊的男士或女士亦先出隊配成舞伴，所以該問題具有典型的先進先出特性，可伴，所以該問題具有典型的先進先出特性，可用隊列作為算法的數(shù)據(jù)結(jié)構(gòu)

30、。在算法中，假設(shè)用隊列作為算法的數(shù)據(jù)結(jié)構(gòu)。在算法中，假設(shè)男士和女士的記錄存放在一個數(shù)組中作為輸入男士和女士的記錄存放在一個數(shù)組中作為輸入，然后依次掃描該數(shù)組的各元素，并根據(jù)性別，然后依次掃描該數(shù)組的各元素，并根據(jù)性別來決定是進入男隊還是女隊。當這兩個隊列構(gòu)來決定是進入男隊還是女隊。當這兩個隊列構(gòu)造完成之后，依次將兩隊當前的隊頭元素出隊造完成之后，依次將兩隊當前的隊頭元素出隊來配成舞伴，直至某個隊列變空為止。此時，來配成舞伴，直至某個隊列變空為止。此時，typedef struct char name20; char sex;/F表示女性，M表示男性 ElemType;某隊仍有等待的配對者，算法輸出此隊某隊仍有