第章棧和隊列

1、第 3 章 限定性線性表棧和隊列 第第3章章 限定性線性表限定性線性表棧和隊列棧和隊列 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)3.4 隊列隊列 第 3 章 限定性線性表棧和隊列 3.1 3.1 什么是棧什么是棧? ? 例 算術(shù)表達(dá)式5+6/2-3*4。正確理解： 5+6/2-3*4 = 5+3-3*4 = 8-3*4 = 8-12 = -4 p由兩類對象構(gòu)成的： 運算數(shù)，如2、3、4 運算符號，如+、-、*、/ p不同運算符號優(yōu)先級不一樣 第 3 章 限定性線性表棧和隊列 后綴表達(dá)式后綴表達(dá)式 中綴表達(dá)式：運算符號位于兩個運算數(shù)之間。如 a + b

2、* c - d / e 后綴表達(dá)式：運算符號位于兩個運算數(shù)之后。如 a b c *+ d e /-例 6 2 / 3 - 4 2 *+ = ? 后綴表達(dá)式求值策略：從左向右“掃描”，逐個處理運算數(shù)和運算符號 。1. 遇到運算數(shù)怎么辦？如何“記住”目前還不未參與運算的數(shù)？ 2. 遇到運算符號怎么辦？對應(yīng)的運算數(shù)是什么？ 需要有種存儲方法，能順序存儲運算數(shù)，需要有種存儲方法，能順序存儲運算數(shù)， 并在需要時并在需要時“倒序倒序”輸出！輸出！第 3 章 限定性線性表棧和隊列 對象: 6 (運算數(shù) )例 6 2 / 3 - 4 2 *+ = ? 對象: 2 ( 運算數(shù) )對象: / ( 運算符 ) 對象

3、: 3 (運算數(shù) ) 對象: - (運算符) 對象: 4 (運算數(shù) ) 對象: 2 (運算數(shù) ) 對象: * ( 運算符 )對象: + (運算符) Pop: 8top62toptop2 6 /= 33333-= 0042top24*= 8880+= 88T( N ) = O ( N )8第 3 章 限定性線性表棧和隊列 棧（Stack）：具有一定操作約束的線性表 只在一端（棧頂棧頂，Top）做 插入、刪除 插入數(shù)據(jù)：入棧入棧（Push） 刪除數(shù)據(jù)：出棧出棧（Pop） 后入先出后入先出：Last In First Out（LIFO）第 3 章 限定性線性表棧和隊列 圖圖3.1 棧棧 ana2a1

4、進棧出棧棧頂棧底進棧出棧(a) 棧的示意圖(b) 鐵路調(diào)序棧的表示第 3 章 限定性線性表棧和隊列 棧的抽象數(shù)據(jù)類型描述棧的抽象數(shù)據(jù)類型描述ADT Stack 數(shù)據(jù)對象集數(shù)據(jù)對象集：一個有0個或多個元素的有窮線性表。 基本操作：基本操作： （1） InitStack(&S) 初始條件： S為未初始化的棧。 操作結(jié)果： 將S初始化為空棧。 （2） ClearStack(&S) 初始條件： 棧S已經(jīng)存在。 操作結(jié)果： 將棧S置成空棧。 第 3 章 限定性線性表棧和隊列 （3） StackEmpty(S) 初始條件：棧S已經(jīng)存在。 操作結(jié)果：若S為空棧，則函數(shù)值為TRUE，否則FAL

5、SE （4） Push(&S,e) 初始條件：棧S已經(jīng)存在。 操作結(jié)果：在S的頂部插入(亦稱壓入)元素e；第 3 章 限定性線性表棧和隊列 （5） Pop(&S, &e) 初始條件：棧S已經(jīng)存在。 操作結(jié)果：刪除(亦稱彈出)棧S的頂部元素，并用e帶回該值。 （6） GetTop(S, &e) 初始條件： 棧S已經(jīng)存在。 操作結(jié)果：取棧S的頂部元素。與Pop(&S, e)不同之處在于GetTop(S,&e)不改變棧頂?shù)奈恢?。?3 章 限定性線性表棧和隊列 Push 和 Pop 可以穿插交替進行； 按照操作系列 (1)Push(S,A), Push

6、(S,B),Push(S,C),Pop(S),Pop(S),Pop(S) 棧輸出是？(2) 而Push(S,A), Pop(S),Push(S,B),Push(S,C),Pop(S),Pop(S) 棧輸出是? 例 如果三個字符按ABC順序壓入堆棧 ABC的所有排列都可能是出棧的序列嗎？ 可以產(chǎn)生CAB這樣的序列嗎？ CBAACB第 3 章 限定性線性表棧和隊列 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 1. 順序棧順序棧 順序棧是用順序存儲結(jié)構(gòu)實現(xiàn)的棧，由一個一維數(shù)組和一個記錄棧頂元素位置的變量組成。define TRUE 1define FALSE 0typedef struct SElem

7、Type * base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; /棧可使用的最大容量 SqStack; 第 3 章 限定性線性表棧和隊列 圖3.2 順序棧中的進棧和出棧 43210432104321043210第 3 章 限定性線性表棧和隊列 順序?；静僮鞯膶崿F(xiàn)如下:(1) 初始化。 Status InitStack (SqStack &S) S.base = (SElemType *)malloc (STACK_INIT_SIZE *sizeof(SElemType); if (! S.base) exit (OVERFLOW); S

8、.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK;第 3 章 限定性線性表棧和隊列 (2) 取棧頂元素 Status GetTop(SqStack S, SElemType &e) if (S.top = = S.base) return ERROR; e= * (S.top-1); return OK;第 3 章 限定性線性表棧和隊列 (3) 入棧。 Status Push(SqStack &S, SElemType e) if (S.top - S.base= S.stacksize) S.base=(SElem

9、Type*)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; return OK; 第 3 章 限定性線性表棧和隊列 (4) 出棧 Status Pop(SqStack &S, SelemType &e) if( S.top= =S.base) return ERROR; e=*-S.top; return OK;第

10、 3 章 限定性線性表棧和隊列 在棧的共享技術(shù)中最常用的是兩個棧的共享技術(shù)：它主要利用了?！皸５孜恢貌蛔儯鴹ｍ斘恢脛討B(tài)變化”的特性。首先為兩個棧申請一個共享的一維數(shù)組空間SM，將兩個棧的棧底分別放在一維數(shù)組的兩端，分別是0、M-1。由于兩個棧頂動態(tài)變化，這樣可以形成互補，使得每個?？捎玫淖畲罂臻g與實際使用的需求有關(guān)。由此可見，兩棧共享比兩個棧分別申請M/2的空間利用率高。第 3 章 限定性線性表棧和隊列 圖3.3 共享棧 Stack:0M 1top0top1第 3 章 限定性線性表棧和隊列 2. 鏈棧鏈棧 圖3.4 鏈棧示意圖 棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)實際上就是一個單鏈表，叫做鏈棧。插入和刪除操作只

11、能在鏈棧的棧頂進行。 棧頂指針Top應(yīng)該在鏈表的哪一頭？ 第 3 章 限定性線性表棧和隊列 3.2 棧的應(yīng)用：表達(dá)式求值棧的應(yīng)用：表達(dá)式求值 回憶：應(yīng)用棧實現(xiàn)后綴表達(dá)式求值的基本過程回憶：應(yīng)用棧實現(xiàn)后綴表達(dá)式求值的基本過程： 從左到右讀入后綴表達(dá)式的各項（運算符或運算數(shù)）； 1.運算數(shù)運算數(shù)：入棧； 2.運算符運算符：從棧中彈出適當(dāng)數(shù)量的運算數(shù)，計算并結(jié)果入棧； 3.最后，棧頂上的元素就是表達(dá)式的結(jié)果值。 第 3 章 限定性線性表棧和隊列 中綴表達(dá)式求值中綴表達(dá)式求值 基本策略：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后求值基本策略：將中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式，然后求值 如何將中綴表達(dá)式轉(zhuǎn)換為后綴？

12、 觀察一個簡單例子： 3 + 4 * 5 -6 3 4 5 * + 6 1.運算數(shù)相對順序不變 2.運算符號順序發(fā)生改變 需要存儲“等待中”的運算符號 要將當(dāng)前運算符號與“等待中”的最后一個運算符號比較 有括號怎么辦？有括號怎么辦？棧第 3 章 限定性線性表棧和隊列 例 3 * (4 +5 ) / 6 = ? 3 4 5 + * 6 /top輸出: 3輸入對象: 3 (操作數(shù)) 輸入對象: * (乘法)輸入對象: ( (左括號)輸入對象: 4 (操作數(shù))輸入對象: + (加法)輸入對象: 5 (操作數(shù))輸入對象: ) (右括號)輸入對象: / (除法)輸入對象: 6 (操作數(shù))(4+5T( N

13、 ) = O ( N )*+*/6 /第 3 章 限定性線性表棧和隊列 中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式中綴表達(dá)式如何轉(zhuǎn)換為后綴表達(dá)式 從頭到尾讀取中綴表達(dá)式的每個對象，對不同對象按不同的情況處理。 運算數(shù)：直接輸出； 左括號：壓入棧； 右括號：將棧頂?shù)倪\算符彈出并輸出，直到遇到左括號（出棧，不輸出）； 運算符： 若優(yōu)先級大于棧頂運算符時，則把它壓棧； 若優(yōu)先級小于等于棧頂運算符時，將棧頂運算符彈出并輸出；再比較新的棧頂運算符，直到該運算符大于棧頂運算符優(yōu)先級為止，然后將該運算符壓棧； 若各對象處理完畢，則把棧中存留的運算符一并輸出。 第 3 章 限定性線性表棧和隊列 棧的其他應(yīng)用：棧的其他應(yīng)用

14、： 函數(shù)調(diào)用及遞歸實現(xiàn) 深度優(yōu)先搜索 回溯算法 第 3 章 限定性線性表棧和隊列 3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) 棧非常重要的一個應(yīng)用是在程序設(shè)計語言中用來實現(xiàn)遞歸。遞歸遞歸是指在定義自身的同時又出現(xiàn)了對自身的調(diào)用。直接遞歸函數(shù)直接遞歸函數(shù)間接遞歸函數(shù)間接遞歸函數(shù)第 3 章 限定性線性表棧和隊列 遞歸過程的實現(xiàn)遞歸過程的實現(xiàn) 一個函數(shù)調(diào)用另一個函數(shù)時，在運行被調(diào)用函數(shù)之前，系統(tǒng)做的工作有： (1) 保留本層參數(shù)與返回地址（將所有的實在參數(shù)、返回地址等信息傳遞給被調(diào)用函數(shù)保存）； (2) 給下層參數(shù)賦值（為被調(diào)用函數(shù)的局部變量分配存儲區(qū)）； (3) 將程序轉(zhuǎn)移到被調(diào)函數(shù)的入口。 第 3 章

15、 限定性線性表棧和隊列 而從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，系統(tǒng)也應(yīng)完成三件工作： (1) 保存被調(diào)函數(shù)的計算結(jié)果； (2) 恢復(fù)上層參數(shù)（釋放被調(diào)函數(shù)的數(shù)據(jù)區(qū)）； (3) 依照被調(diào)函數(shù)保存的返回地址，將控制轉(zhuǎn)移回調(diào)用函數(shù)。 當(dāng)多個函數(shù)調(diào)用時按后調(diào)用先返回后調(diào)用先返回的原則。 第 3 章 限定性線性表棧和隊列 系統(tǒng)將整個程序運行時所需的數(shù)據(jù)空間安排在一個棧中，每次調(diào)用一個函數(shù)時就為它在棧頂分配一個存儲區(qū)，當(dāng)一個函數(shù)返回時就釋放它的存儲區(qū)，當(dāng)前正在運行的函數(shù)所有數(shù)據(jù)必在棧頂。void first(int,int); void first(int s,int t)void second(int); v

16、oid main() int i; int m,n; sencond(i); 2: first(m,n); 1: void second(int d) int x,y; 第 3 章 限定性線性表棧和隊列 例例：n階Hanoi塔問題：假設(shè)有三個分別命名為X、Y和Z的塔座，在塔座X上插有n個直徑大小各不相同、依小到大編號為1，2, ，n的圓盤?，F(xiàn)要求將X軸上的n個圓盤移至塔座Z上并仍按同樣順序疊排，圓盤移動時必須遵循下列原則： (1) 每次只能移動一個圓盤； (2) 圓盤可以插在X、Y和Z中的任何一個塔座上； (3) 任何時刻都不能將一個較大的圓盤壓在較小的圓盤之上。 第 3 章 限定性線性表棧和

17、隊列 如何實現(xiàn)移動圓盤的操作呢？如何實現(xiàn)移動圓盤的操作呢？ n=1時 1：X - Z n1時 1(n-1)：X - Y n：X - Z 1 (n-1)：Y - Z 如何將n-1個圓盤從一個塔座移至另一個塔座問題是一個和原問題具有相同特征屬性的問題，只是問題的規(guī)模小個1，因此可以用同樣方法求解。第 3 章 限定性線性表棧和隊列 void hanoi(int n,char x,char y,char z) /*將塔座X上編號為1至n的n個圓盤按規(guī)則搬到塔座Z上， Y可用作輔助塔座 */ 12 if(n=1) 3 move(x,1,z); /* 將編號為1的圓盤從X移動Z */4 else 5 ha

18、noi(n-1,x,z,y); /* 將X上編號為1至n-1的圓盤移到Y(jié),Z作輔助塔 */ 6 move(x,n,z); /* 將編號為n的圓盤從X移到Z */ 7 hanoi(n-1,y,x,z); /* 將Y上編號為1至n-1的圓盤移動到Z， X作輔助塔 */8 9 第 3 章 限定性線性表棧和隊列 下面給出三個盤子搬動時hanoi(3, A, B, C) 遞歸調(diào)用過程， 如圖3.5所示。 hanoi(2,A,C,B): hanoi(1,A,B,C) move(A-C) 1號搬到C move(A-B) 2號搬到B hanoi(1,C,A,B) move(C-B) 1號搬到B move(A-

19、C) 3號搬到C hanoi(2,B,A,C): hanoi(1,B,C,A) move(B-A) 1號搬到A move(B-C) 2號搬到C hanoi(1,A,B,C) move(A-C) 1號搬到C 第 3 章 限定性線性表棧和隊列 圖3.5 Hanoi塔的遞歸函數(shù)運行示意圖 321a321abc321abc321abc321abcbc321abc321abc321abc第 3 章 限定性線性表棧和隊列 遞歸的優(yōu)點遞歸的優(yōu)點 通過上面的例子可看出，遞歸既是強有力的數(shù)學(xué)方法， 也是程序設(shè)計中一個很有用的工具。其特點是對遞歸問題描述簡捷，結(jié)構(gòu)清晰，程序的正確性容易證明。 遞歸算法求解問題的要

20、素遞歸算法求解問題的要素 遞歸算法就是算法中有直接或間接調(diào)用算法本身的算法。 遞歸算法的要點如下： (1) 問題具有類同自身的子問題的性質(zhì)，被定義項在定義中的應(yīng)用具有更小的尺度。 (2) 被定義項在最小尺度上有直接解。 第 3 章 限定性線性表棧和隊列 設(shè)計遞歸算法的方法是： (1) 尋找方法，將問題化為原問題的子問題求解（例n!=n*(n-1)!）。 (2) 設(shè)計遞歸出口，確定遞歸終止條件(例求解n!時，當(dāng)n=1時，n! =1)。 第 3 章 限定性線性表棧和隊列 遞歸算法到非遞歸算法轉(zhuǎn)換遞歸算法到非遞歸算法轉(zhuǎn)換 遞歸算法具有兩個特性： (1) 遞歸算法是一種分而治之、把復(fù)雜問題分解為簡單問

21、題的求解問題方法，對求解某些復(fù)雜問題，遞歸算法的分析方法是有效的。 （2） 遞歸算法的時間效率低。 第 3 章 限定性線性表棧和隊列 1) 消除遞歸的原因 其一：有利于提高算法時空性能，因為遞歸執(zhí)行時需要系統(tǒng)提供隱式棧實現(xiàn)遞歸，效率低且費時。 其二： 無應(yīng)用遞歸語句的語言設(shè)施環(huán)境條件，有些計算機語言不支持遞歸功能，如FORTRAN語言中無遞歸機制 。 其三：遞歸算法是一次執(zhí)行完，這在處理有些問題時不合適，也存在一個把遞歸算法轉(zhuǎn)化為非遞歸算法的需求。 第 3 章 限定性線性表棧和隊列 2) 簡單遞歸消除 在簡單情況下，將遞歸算法可簡化為線性序列執(zhí)行，可直接轉(zhuǎn)換為循環(huán)實現(xiàn)。 遞歸進層三件事： 保存

22、本層參數(shù)、 返回地址; 傳遞參數(shù)，分配局部數(shù)據(jù)空間;控制轉(zhuǎn)移。遞歸退層三件事： 恢復(fù)上層；傳遞結(jié)果；轉(zhuǎn)斷點執(zhí)行。 第 3 章 限定性線性表棧和隊列 尾遞歸尾遞歸 是指遞歸調(diào)用語句只有一個，而且是處于算法的最后。我們以階乘問題的遞歸算法Fact(n)為例討論尾遞歸算法的運行過程。為討論方便，我們列出階乘問題的遞歸算法Fact(n)，并簡化掉參數(shù)n的出錯檢查語句，改寫遞歸調(diào)用語句的位置在最后，算法如下： long Fact(int n) if(n=0) return 1; return n * Fact(n-1); 第 3 章 限定性線性表棧和隊列 圖圖3.6 遞歸調(diào)用變化情況示意遞歸調(diào)用變化情況

23、示意 棧：調(diào) f(2) 前調(diào) f(1) 后2r3r返 f(1) 后2r3r返 f(3) 前調(diào) f(2) 后3r調(diào) f(0) 后2r3r1r返 f(2) 后3rf(3)f(2)f(1)f(0)6213*22*11第 3 章 限定性線性表棧和隊列 圖3.7 f(3)遞歸調(diào)用流程變化示意 f(3)f(2)f(1)f(0)3*22*111自下而上返回階段自上而下遞歸進層階段第 3 章 限定性線性表棧和隊列 由圖3.7可看出，整個計算包括自上而下遞歸調(diào)用進層和自下而上遞歸返回退層兩個階段，所有遞歸調(diào)用直接或間接依賴f(0)，所以整個階段分兩步，計算順序在第二階段，先計算f(0)f(1)f(n)，工作變量

24、y記錄中間結(jié)果。 第 3 章 限定性線性表棧和隊列 循環(huán)結(jié)構(gòu)的階乘問題算法Fact(n)如下： long Fact(int n) int fac=1; for(int i=1;inext = NULL; return OK; 第 3 章 限定性線性表棧和隊列 （2）銷毀隊列Status DestroyQueue(LinkQueue &Q) while(Q.front) Q.rear = Q.front-next;free (Q.front);Q.front = Q.rear; return OK;第 3 章 限定性線性表棧和隊列 （3） 入隊操作 Status EnQueue (Lin

25、kQueue &Q, QelemType e) p= (QueuePtr) malloc(sizeof(QNode); if (!p) exit ( OVERFLOW); p-data = e; p-next = NULL; Q.rear - next =p; Q.rear = p; return OK;第 3 章 限定性線性表棧和隊列 （4） 出隊操作 Status DeQueue (LinkQueue &Q, QelemType &e) if ( Q.front = Q.rear) return ERROR; p=Q.front-next; e=p-data; Q.

26、front-next =p-next; if (Q.rear = p) Q.rear = Q.front; free(p); return OK;第 3 章 限定性線性表棧和隊列 2. 隊列的順序存儲實現(xiàn)隊列的順序存儲實現(xiàn) 隊列的順序存儲結(jié)構(gòu)通常由一個一維數(shù)組和一個記錄隊列頭元素位置的變量front以及一個記錄隊列尾元素位置的變量rear組成。 0 1 2 3 4 5frontrear例 一個工作隊列 操作過程：（1）a, b, c, d依次入隊（2）a, b, c依次出隊（3）e, f入隊 （4）g入隊 (能入否？)abcdefrearrearrearrearrearrearfront第 3

27、 章 限定性線性表棧和隊列 1 0 2 3 4 5 frontrear循環(huán)隊列循環(huán)隊列操作過程：（1）a, b, c, d依次入隊abcdefgrearfront（2）a, b, c依次出隊（3）e, f入隊 （4）g入隊rear（5）m, n 入隊mnrear思考思考: （1）這種方案：堆棧空和滿的判別條件是什么？）這種方案：堆?？蘸蜐M的判別條件是什么？ （2）為什么會出現(xiàn)空、滿無法區(qū)分？根本原因？）為什么會出現(xiàn)空、滿無法區(qū)分？根本原因？ （6）x 入隊第 3 章 限定性線性表棧和隊列 圖3.9 循環(huán)隊列 012354rearfront(a) 空隊列012354e6e7e8e3e4e5012354(b) 隊列滿(b) 一般情況frontreare3e4e5frontrear第 3 章 限定性線性表棧和隊列 如何區(qū)分隊列如何區(qū)分隊列“空空”和和“滿滿”另設(shè)一個標(biāo)志位以區(qū)分隊列是空還是滿；少用一個元素空間，當(dāng)隊列頭指針在隊列尾指針的下一個