棧棧的應(yīng)用舉例隊列ppt課件

1、1 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 隊列隊列 2 第第3 3章章 棧和隊列棧和隊列 重點重點: (1)棧、隊列的定義、特點、性質(zhì)和應(yīng)用；棧、隊列的定義、特點、性質(zhì)和應(yīng)用；(2)ADT棧、棧、ADT隊列的設(shè)計和實現(xiàn)以及基本操作及隊列的設(shè)計和實現(xiàn)以及基本操作及相關(guān)算法。相關(guān)算法。 難點難點: (1)循環(huán)隊列中對邊界條件的處理；循環(huán)隊列中對邊界條件的處理；(2)分析棧分析棧和隊列在表達(dá)式求值、括號匹配、數(shù)制轉(zhuǎn)換、迷宮和隊列在表達(dá)式求值、括號匹配、數(shù)制轉(zhuǎn)換、迷宮求解中的應(yīng)用實例，提高利用棧和隊列解決實際問求解中的應(yīng)用實例，提高利用棧和隊列解決實際問題的應(yīng)用水平。題的應(yīng)用水平。

2、本章重點難點 3 第第3 3章章 棧和隊列棧和隊列 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 隊列隊列 4 第第3 3章章 棧和隊列棧和隊列 3.1 棧棧 3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 5 第第3 3章章 棧和隊列棧和隊列3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義p棧的定義棧的定義棧棧(Stack)是一種特殊的線性表，其插入和刪除操是一種特殊的線性表，其插入和刪除操作均在表的一端進(jìn)行，是一種運算受限的線性表。作均在表的一端進(jìn)行，是一種運算受限的線性表。棧頂棧頂(top)是棧中允許插入和刪除的一端。是棧中允

3、許插入和刪除的一端。棧底棧底(bottom)是棧頂?shù)牧硪欢?。是棧頂?shù)牧硪欢?。p棧的術(shù)語棧的術(shù)語 6 第第3 3章章 棧和隊列棧和隊列p棧的特點棧的特點p棧的示意圖棧的示意圖后進(jìn)先出后進(jìn)先出(Last In First Out，簡稱，簡稱LIFO)。又稱棧為后進(jìn)先出表又稱棧為后進(jìn)先出表(簡稱簡稱LIFO結(jié)構(gòu)結(jié)構(gòu))。 ana2a1棧底棧底棧頂棧頂入棧入棧出棧出棧3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 7 第第3 3章章 棧和隊列棧和隊列 ADT Stack 數(shù)據(jù)對象：數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： p抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型棧基本操作：基本操作： ADT StackR1 | ai

4、-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 D ai | ai ElemSet, i=1,2,.,n, n0 見下頁見下頁3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 8 第第3 3章章 棧和隊列棧和隊列InitStack(&S) /初始化棧初始化棧DestroyStack(&S) /銷毀棧銷毀棧ClearStack(&S) /清空棧清空棧StackEmpty(S) /判棧空判?？誗tackLength(S) /求棧長度求棧長度GetTop(S, &e) /取棧頂元素取棧頂元素Push(&S,

5、e) /入棧入棧Pop(&S, &e) /出棧出棧StackTravers(S, visit() /遍歷棧遍歷棧p棧的基本操作棧的基本操作3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 9 第第3 3章章 棧和隊列棧和隊列 3.1 棧棧 3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 10 第第3 3章章 棧和隊列棧和隊列3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) /- 棧的順序存儲表示棧的順序存儲表示 - #define STACK_INIT_SIZE 100; /存儲空間初始分配存儲空間初始分配量量 #define STA

6、CKINCREMENT 10; /存儲空間分配增存儲空間分配增量量 typedef struct SElemType *base; /棧底指針棧底指針 SElemType *top; /棧頂指針棧頂指針 int stacksize; /當(dāng)前可使用最大容量當(dāng)前可使用最大容量 SqStack;SqStack S;p順序棧的順序棧的C語言實現(xiàn)語言實現(xiàn) 11 第第3 3章章 棧和隊列棧和隊列3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)p棧初始化過程演示棧初始化過程演示(1) 給棧給棧S申請?？臻g申請?？臻g(2) 設(shè)置基地址設(shè)置基地址S.base和棧頂?shù)刂泛蜅ｍ數(shù)刂稴SS.base(3) 設(shè)置棧容量設(shè)置棧容

7、量S.stacksize=STACK_INIT_SIZE 12 第第3 3章章 棧和隊列棧和隊列 Status InitStack (SqStack &S) / 構(gòu)造一個空棧構(gòu)造一個空棧S S.base=(ElemType*)malloc(STACK_INIT_SIZE* sizeof(ElemType); if (!S.base) exit (OVERFLOW); /存儲分配失敗存儲分配失敗 S = S.base; S.stacksize = STACK_INIT_SIZE; return OK;3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)p棧初始化算法棧初始化算法 13 第第3 3章章

8、 棧和隊列棧和隊列3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)p入棧操作演示入棧操作演示(1) 如果棧滿，給棧增加容量如果棧滿，給棧增加容量abcdef(2) 將數(shù)據(jù)存入棧頂位置，棧頂后移一位將數(shù)據(jù)存入棧頂位置，棧頂后移一位SS.baseeS 14 第第3 3章章 棧和隊列棧和隊列 Status Push (SqStack &S, SElemType e) if (S - S.base = S.stacksize) S.base = (ElemType *) realloc ( S.base, (S.stacksize + STACKINCREMENT) * sizeof (ElemTyp

9、e); if (!S.base) exit (OVERFLOW); /存儲分配失敗存儲分配失敗 S = S.base + S.stacksize; S.stacksize += STACKINCREMENT; *S+ = e; return OK;3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)p入棧操作演示入棧操作演示 15 第第3 3章章 棧和隊列棧和隊列3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)DestroyStack(&S) /銷毀棧銷毀棧ClearStack(&S) /清空棧清空棧StackEmpty(S) /判?？张袟？誗tackLength(S) /求棧長度求棧長度GetT

10、op(S, &e) /取棧頂元素取棧頂元素Pop(&S, &e) /出棧出棧StackTravers(S, visit() /遍歷棧遍歷棧p其它棧操作討論其它棧操作討論 16 第第3 3章章 棧和隊列棧和隊列 Typedef struct SNode ElemType data; /數(shù)據(jù)域數(shù)據(jù)域 struct Snode *next; /鏈域鏈域 SNode, *LinkStack; 3.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn)p鏈棧的鏈棧的C語言類型定義語言類型定義 鏈棧的實現(xiàn)與鏈表的實現(xiàn)基本相同，頭結(jié)鏈棧的實現(xiàn)與鏈表的實現(xiàn)基本相同，頭結(jié)點作為棧頂位置。點作為棧頂位置。L

11、inkStack *top; /棧頂指針棧頂指針 17 第第3 3章章 棧和隊列棧和隊列InitStack(&S) /初始化棧初始化棧DestroyStack(&S) /銷毀棧銷毀棧ClearStack(&S) /清空棧清空棧StackEmpty(S) /判?？张袟？誗tackLength(S) /求棧長度求棧長度GetTop(S, &e) /取棧頂元素取棧頂元素Push(&S, e) /入棧入棧Pop(&S, &e) /出棧出棧StackTravers(S, visit() /遍歷棧遍歷棧p討論鏈?；静僮鞯膶崿F(xiàn)討論鏈?；静僮鞯膶崿F(xiàn)3

12、.1.2 棧的表示和實現(xiàn)棧的表示和實現(xiàn) 18 第第3 3章章 棧和隊列棧和隊列3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗括號匹配的檢驗3.2.3 行編輯程序問題行編輯程序問題3.2.4 迷宮求解迷宮求解3.2.5 表達(dá)式求值表達(dá)式求值 19 第第3 3章章 棧和隊列棧和隊列3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換00122.YaYaYaYaNnnX 任何任何X進(jìn)制數(shù)進(jìn)制數(shù)N轉(zhuǎn)換成轉(zhuǎn)換成Y進(jìn)制數(shù)其結(jié)果都是要化進(jìn)制數(shù)其結(jié)果都是要化成如下形式。成如下形式。p進(jìn)制轉(zhuǎn)換原理：進(jìn)制轉(zhuǎn)換原理： 轉(zhuǎn)換的過程就是通過取余運算求出轉(zhuǎn)換的過程就是通過取余運算求出a0,a1,an，而先

13、求出的是個位，十位而先求出的是個位，十位，與我們寫數(shù)的習(xí)慣先，與我們寫數(shù)的習(xí)慣先從高位寫正好相反，通過棧先進(jìn)后出的特點，很容從高位寫正好相反，通過棧先進(jìn)后出的特點，很容易實現(xiàn)倒過來的過程。易實現(xiàn)倒過來的過程。 20 第第3 3章章 棧和隊列棧和隊列過程如下：過程如下：N N div 8 N mod 81348 168 4168 21 021 2 52 0 2輸出順序輸出順序計算順序計算順序3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換例例將將10進(jìn)制進(jìn)制1346轉(zhuǎn)換成轉(zhuǎn)換成8進(jìn)制進(jìn)制 21 第第3 3章章 棧和隊列棧和隊列void conversion () InitStack(S); scanf (%d,N)

14、; while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion3.2.1 數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換p10進(jìn)制數(shù)進(jìn)制數(shù)N轉(zhuǎn)換成轉(zhuǎn)換成8進(jìn)制的算法進(jìn)制的算法 22 第第3 3章章 棧和隊列棧和隊列 一個表達(dá)式中，包含三種括號一個表達(dá)式中，包含三種括號“(”和和“)”，“”和和“”和和“”和和“”，這三種括號可以按任意的合，這三種括號可以按任意的合法次序使用。法次序使用。 設(shè)計算法檢驗表達(dá)式中所使用括號的合法性。設(shè)計算法檢驗表達(dá)式中所使用括號的合法性。3.2.2 括號匹配的

15、檢驗括號匹配的檢驗p問題描述問題描述 討論：如果第一次遇到的右括號是討論：如果第一次遇到的右括號是“”，那么前，那么前面出現(xiàn)的左括號有什么特點。面出現(xiàn)的左括號有什么特點。 p問題討論問題討論 結(jié)論：如果第一次遇到的右括號是結(jié)論：如果第一次遇到的右括號是“”，那么前，那么前面出現(xiàn)的左括號最后一個必然是面出現(xiàn)的左括號最后一個必然是“”，否則不合法。，否則不合法。 23 第第3 3章章 棧和隊列棧和隊列p算法過程算法過程3.2.2 括號匹配的檢驗括號匹配的檢驗當(dāng)遇到左括號時，進(jìn)棧，遇到右括號時出棧；當(dāng)遇到左括號時，進(jìn)棧，遇到右括號時出棧；(2) 當(dāng)遇到某一個右括號時，棧已空，說明到當(dāng)遇到某一個右括號

16、時，棧已空，說明到目前為止，右括號多于左括號；目前為止，右括號多于左括號；(3) 從棧中彈出的左括號與當(dāng)前檢驗的右括號從棧中彈出的左括號與當(dāng)前檢驗的右括號類型不同，說明出現(xiàn)了括號交叉情況；類型不同，說明出現(xiàn)了括號交叉情況；(4) 算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹算術(shù)表達(dá)式輸入完畢，但棧中還有沒有匹配的左括號，說明左括號多于右括號。配的左括號，說明左括號多于右括號。 24 第第3 3章章 棧和隊列棧和隊列Status check( ) char ch; InitStack(S); while (ch=getchar()!=#) switch (ch) case (ch=(|ch=|ch=):

17、Push(S,ch);break; case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= () return FALSE; break;p括號匹配檢驗算法括號匹配檢驗算法3.2.2 括號匹配的檢驗括號匹配的檢驗 25 第第3 3章章 棧和隊列棧和隊列 case (ch= ): if (StackEmpty(S) retrun FALSE; else Pop(S,e); if(e!= ) return FALSE; break; default:break; if (StackEmpty(S) return TRUE

18、;else return FALSE;p括號匹配檢驗算法括號匹配檢驗算法3.2.2 括號匹配的檢驗括號匹配的檢驗 26 第第3 3章章 棧和隊列棧和隊列3.2.3 行編輯程序問題行編輯程序問題 設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的設(shè)立一個輸入緩沖區(qū)，用以接受用戶輸入的一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)一行字符，然后逐行存入用戶數(shù)據(jù)區(qū)，并假設(shè)“#”為退格符，為退格符，“”“”為退行符。為退行符。 在用戶輸入一行的過程中，允許用戶輸入出差在用戶輸入一行的過程中，允許用戶輸入出差錯，并在發(fā)現(xiàn)有誤時可以及時更正。錯，并在發(fā)現(xiàn)有誤時可以及時更正。p解決辦法解決辦法p問題描述問題描述 27 第第3

19、 3章章 棧和隊列棧和隊列假設(shè)從終端接受了這樣兩行字符：假設(shè)從終端接受了這樣兩行字符： whli#ilr#es#*s) outchaputchar(*s=#+);則實際有效的是下列兩行：則實際有效的是下列兩行： while (*s) putchar(*s+);例例3.2.3 行編輯程序問題行編輯程序問題 28 第第3 3章章 棧和隊列棧和隊列 DestroyStack(S);void LineEdit() /利用字符棧利用字符棧S，從終端接收一行并傳送至調(diào)，從終端接收一行并傳送至調(diào) /用過程的數(shù)據(jù)區(qū)用過程的數(shù)據(jù)區(qū) InitStack(S); ch=getchar(); . 3.2.3 行編輯程

20、序問題行編輯程序問題p行編輯問題算法行編輯問題算法while (ch != EOF) /EOF為全文結(jié)束符為全文結(jié)束符 while (ch != EOF & ch != n) 29 第第3 3章章 棧和隊列棧和隊列 switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置重置S為空棧為空棧 default : Push(S, ch); break; ch = getchar(); / 從終端接收下一個字符從終端接收下一個字符 ClearStack(S); / 重置重置S為空棧為空棧if (ch !=

21、EOF) ch = getchar(); 棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；棧中字符傳送至調(diào)用過程的數(shù)據(jù)區(qū)；3.2.3 行編輯程序問題行編輯程序問題p行編輯問題算法行編輯問題算法 30 第第3 3章章 棧和隊列棧和隊列入口入口出口出口3.2.4 迷宮求解迷宮求解如圖表示一個迷宮，有一個入口，一個出口，從一個如圖表示一個迷宮，有一個入口，一個出口，從一個位置可以向位置可以向4個方向個方向(東、南、西、北東、南、西、北)走，白方塊表示走，白方塊表示通道，藍(lán)方塊表示墻，求從入口到出口的路徑。通道，藍(lán)方塊表示墻，求從入口到出口的路徑。p問題描述問題描述1234567812345678 31 第第3 3章

22、章 棧和隊列棧和隊列3.2.4 迷宮求解迷宮求解p求解方法求解方法“窮舉求解方法：從入口出發(fā)，順某一方向向前探窮舉求解方法：從入口出發(fā)，順某一方向向前探索，若能走通，則繼續(xù)往前走；否則沿原路退回，換索，若能走通，則繼續(xù)往前走；否則沿原路退回，換一個方向再繼續(xù)探索，直至所有可能的通路都探索到一個方向再繼續(xù)探索，直至所有可能的通路都探索到為止。為止。為了保證在任何位置上都能沿原路退回，需要一個后為了保證在任何位置上都能沿原路退回，需要一個后進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，進(jìn)先出的結(jié)構(gòu)來保存從入口到當(dāng)前位置的路徑。因此，求解迷宮通路算法需要應(yīng)用求解迷宮通路算法需要應(yīng)用“棧來保存當(dāng)前路

23、徑。棧來保存當(dāng)前路徑。 32 第第3 3章章 棧和隊列棧和隊列3.2.4 迷宮求解迷宮求解p 四周墻壁解決辦法如圖四周墻壁解決辦法如圖012345678901234567891234567812345678 33 第第3 3章章 棧和隊列棧和隊列p當(dāng)前位置：在搜索過程中某一時刻所在圖中某個方當(dāng)前位置：在搜索過程中某一時刻所在圖中某個方塊位置。塊位置。p當(dāng)前位置可通：未承走到過的通道塊，該方塊既不當(dāng)前位置可通：未承走到過的通道塊，該方塊既不在當(dāng)前路徑上，也不是曾經(jīng)納入過路徑的通道塊。在當(dāng)前路徑上，也不是曾經(jīng)納入過路徑的通道塊。3.2.4 迷宮求解迷宮求解01234567890123456789p

24、下一位置：當(dāng)前位下一位置：當(dāng)前位置四周置四周4個方向個方向(東、東、南、西、北南、西、北)上相鄰上相鄰的方塊。的方塊。當(dāng)前當(dāng)前位置位置(3,3)(3,2)(2,2)(1,2)當(dāng)前路徑當(dāng)前路徑 34 第第3 3章章 棧和隊列棧和隊列3.2.4 迷宮求解迷宮求解p 算法思想算法思想(1)若當(dāng)前位置若當(dāng)前位置“可通可通”，則納入，則納入“當(dāng)前路徑當(dāng)前路徑”，并繼續(xù)朝，并繼續(xù)朝“下一位置探求，即切換下一位置探求，即切換“下一位置為下一位置為“當(dāng)前位置當(dāng)前位置”，如此重復(fù)直至到達(dá)出口；如此重復(fù)直至到達(dá)出口；(2)若當(dāng)前位置若當(dāng)前位置“不可通不可通”，則應(yīng)順著，則應(yīng)順著“來向退回到來向退回到“前前一通道塊

25、一通道塊”，然后朝著除了，然后朝著除了“來向之外的其他方向繼來向之外的其他方向繼續(xù)探索；續(xù)探索；(3)若該通道塊的四周若該通道塊的四周4個方塊均個方塊均“不可通不可通”，則應(yīng)從，則應(yīng)從“當(dāng)當(dāng)前路徑上刪除該通道塊。前路徑上刪除該通道塊。 35 第第3 3章章 棧和隊列棧和隊列設(shè)定當(dāng)前位置的初值為入口位置；設(shè)定當(dāng)前位置的初值為入口位置； do 若當(dāng)前位置可通，若當(dāng)前位置可通， 那么將當(dāng)前位置插入棧頂；那么將當(dāng)前位置插入棧頂； 若該位置是出口位置，則算法結(jié)束；若該位置是出口位置，則算法結(jié)束； 否則切換當(dāng)前位置的東鄰方塊為否則切換當(dāng)前位置的東鄰方塊為 新的當(dāng)前位置；新的當(dāng)前位置； 否則否則 .whil

26、e (棧不空）；棧不空）；p迷宮路徑求解算法迷宮路徑求解算法3.2.4 迷宮求解迷宮求解 36 第第3 3章章 棧和隊列棧和隊列 若棧不空且棧頂位置尚有其他方向未被探索，若棧不空且棧頂位置尚有其他方向未被探索， 則設(shè)定新的當(dāng)前位置為則設(shè)定新的當(dāng)前位置為: 沿順時針方向旋轉(zhuǎn)找沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊；到的棧頂位置的下一相鄰塊； 若棧不空但棧頂位置的四周均不可通，那么若棧不空但棧頂位置的四周均不可通，那么 刪去棧頂位置；刪去棧頂位置； 若棧不空，則重新測試新的棧頂位置，若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？?；直至找到一個可通的相鄰塊或出棧至?？?；

27、若棧空，則表明迷宮沒有通路。若?？?，則表明迷宮沒有通路。p迷宮路徑求解算法迷宮路徑求解算法3.2.4 迷宮求解迷宮求解 37 第第3 3章章 棧和隊列棧和隊列012345678901234567893.2.4 迷宮求解迷宮求解p求解過程示例求解過程示例 38 第第3 3章章 棧和隊列棧和隊列3.2.5 表達(dá)式求值表達(dá)式求值 一個表達(dá)式由操作數(shù)一個表達(dá)式由操作數(shù)(operand)、運算符、運算符(operator)、界限符、界限符(delimiter)組成。寫出組成。寫出“算符算符優(yōu)先法求值的算法。優(yōu)先法求值的算法。p問題描述問題描述例例求求3*(2+3*5)+6的值的值 39 第第3 3章章

28、棧和隊列棧和隊列 設(shè)置兩個棧，一個存操作數(shù)，棧名為設(shè)置兩個棧，一個存操作數(shù)，棧名為OPND，一個存操作符，棧名為一個存操作符，棧名為OPTR棧。棧。 (1) 首先置操作數(shù)棧為空，表達(dá)式起始符首先置操作數(shù)棧為空，表達(dá)式起始符#為運為運算符棧的棧底元素；算符棧的棧底元素； (2)依次讀入表達(dá)式中每個字符，若是操作數(shù)則依次讀入表達(dá)式中每個字符，若是操作數(shù)則進(jìn)進(jìn)OPND棧，若是運算符則和棧，若是運算符則和OPTR棧的棧頂運算棧的棧頂運算符比較優(yōu)先權(quán)后作相應(yīng)操作，直到整個表達(dá)式操作符比較優(yōu)先權(quán)后作相應(yīng)操作，直到整個表達(dá)式操作完畢。完畢。3.2.5 表達(dá)式求值表達(dá)式求值p算法求解過程算法求解過程 40 第

29、第3 3章章 棧和隊列棧和隊列 (1)若棧頂運算符小于輸入運算符，輸入運算符若棧頂運算符小于輸入運算符，輸入運算符進(jìn)棧進(jìn)棧OPTR； (2)若棧頂運算符等于輸入運算符只有棧頂是若棧頂運算符等于輸入運算符只有棧頂是“（”，輸入是，輸入是“）”，或者棧頂是，或者棧頂是“#”，輸入是，輸入是“#）”兩種情況，分別去除一對括號，或結(jié)束。兩種情況，分別去除一對括號，或結(jié)束。 (3)若棧頂運算符大于輸入運算符，彈出棧頂運若棧頂運算符大于輸入運算符，彈出棧頂運算符，從算符，從OPND中彈出兩個操作數(shù)與彈出運算符計算中彈出兩個操作數(shù)與彈出運算符計算后再存入后再存入OPND棧，繼續(xù)。棧，繼續(xù)。3.2.5 表達(dá)式

30、求值表達(dá)式求值p算法求解過程算法求解過程 41 第第3 3章章 棧和隊列棧和隊列OperandType EvaluateExpression() initStack(OPTR);Push(OPTR,#); initStack(OPND);c=getchar(); while(c!=#)|GetTop(OPTR)!=#) if(!In(c,OP) Push(OPND,c);c=getchar(); else switch(Precede(GetTop(OPTR),c)3.2.5 表達(dá)式求值表達(dá)式求值p表達(dá)式求值算法表達(dá)式求值算法 42 第第3 3章章 棧和隊列棧和隊列case : Pop(OPT

31、R,theta); Pop(OPND,a); Pop(OPND,b); Push(OPND,Operate(a,theta,b);break; /switch語句結(jié)束語句結(jié)束 /while 語句結(jié)束語句結(jié)束 return(GetTop(OPND); /算法結(jié)束算法結(jié)束p表達(dá)式求值算法表達(dá)式求值算法 43 第第3 3章章 棧和隊列棧和隊列 3.1 棧棧 3.2 棧的應(yīng)用舉例棧的應(yīng)用舉例 3.3 隊列隊列 44 第第3 3章章 棧和隊列棧和隊列p隊列的定義隊列的定義3.4.1 抽象數(shù)據(jù)類型隊列的定義抽象數(shù)據(jù)類型隊列的定義 隊列隊列(Queue)是一種運算受限的特殊的線性是一種運算受限的特殊的線性表

32、，它只允許在表的一端進(jìn)行插入，而在表的另一表，它只允許在表的一端進(jìn)行插入，而在表的另一端進(jìn)行刪除。端進(jìn)行刪除。 隊尾隊尾(rear)是隊列中允許插入的一端。是隊列中允許插入的一端。 隊頭隊頭(front)是隊列中允許刪除的一端。是隊列中允許刪除的一端。p隊列的術(shù)語隊列的術(shù)語 45 第第3 3章章 棧和隊列棧和隊列p隊列的特點隊列的特點p隊列示意圖隊列示意圖3.4.1 抽象數(shù)據(jù)類型隊列的定義抽象數(shù)據(jù)類型隊列的定義a1a2a3 an隊頭隊頭隊尾隊尾出隊出隊出隊出隊 先進(jìn)先出先進(jìn)先出(First In First Out ，簡稱，簡稱FIFO)。 又稱隊列為先進(jìn)先出表。又稱隊列為先進(jìn)先出表。 46

33、第第3 3章章 棧和隊列棧和隊列 ADT Queue 數(shù)據(jù)對象：數(shù)據(jù)對象： 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： p抽象數(shù)據(jù)類型棧抽象數(shù)據(jù)類型棧基本操作：基本操作： ADT Queue見下頁見下頁3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義Dai | aiElemSet, i=1,2,.,n, n0R1 | ai-1, ai D, i=2,.,n約定其中約定其中a1 端為隊列頭，端為隊列頭， an 端為隊列尾端為隊列尾 47 第第3 3章章 棧和隊列棧和隊列InitQueue(&Q) /初始化隊列初始化隊列DestroyQueue(&Q) /銷毀隊列銷毀隊列QueueEmpty(Q)

34、/判隊列是否空判隊列是否空QueueLength(Q) /求隊列長度求隊列長度GetHead(Q, &e) /取隊頭元素取隊頭元素ClearQueue(&Q) /清空隊列清空隊列EnQueue(&Q, e) /入隊列入隊列DeQueue(&Q, &e) /出隊列出隊列QueueTravers(Q, visit() /遍歷隊列遍歷隊列p隊列的基本操作隊列的基本操作3.1.1 抽象數(shù)據(jù)類型棧的定義抽象數(shù)據(jù)類型棧的定義 48 第第3 3章章 棧和隊列棧和隊列3.4.2 鏈隊列鏈隊列 typedef struct QNode / 結(jié)點類型結(jié)點類型 QElemTy

35、pe data; struct QNode *next; QNode, *QueuePtr;p鏈隊列結(jié)點實現(xiàn)鏈隊列結(jié)點實現(xiàn)typedef struct / 鏈隊列類型鏈隊列類型 QueuePtr front; / 隊頭指針隊頭指針 QueuePtr rear; / 隊尾指針隊尾指針 LinkQueue;p鏈隊列數(shù)據(jù)類型實現(xiàn)鏈隊列數(shù)據(jù)類型實現(xiàn) 49 第第3 3章章 棧和隊列棧和隊列Q.frontQ.rearp帶頭結(jié)點的鏈隊列示意圖帶頭結(jié)點的鏈隊列示意圖3.4.2 鏈隊列鏈隊列頭結(jié)點頭結(jié)點空隊列空隊列a1a2anQ.frontQ.rear 50 第第3 3章章 棧和隊列棧和隊列 Status In

36、itQueue (LinkQueue &Q) / 構(gòu)造一個空隊列構(gòu)造一個空隊列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode); if (!Q.front) exit (OVERFLOW); /存儲分配失敗存儲分配失敗 Q.front-next = NULL; return OK;3.4.2 鏈隊列鏈隊列p帶頭結(jié)點的鏈隊列初始化帶頭結(jié)點的鏈隊列初始化 51 第第3 3章章 棧和隊列棧和隊列 Status EnQueue (LinkQueue &Q, QElemType e) / 插入元素插入元素e為為Q的新的隊尾元素的新的隊

37、尾元素 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.2 鏈隊列鏈隊列p帶頭結(jié)點的鏈隊列入隊算法帶頭結(jié)點的鏈隊列入隊算法 52 第第3 3章章 棧和隊列棧和隊列 Status DeQueue (LinkQueue &Q, QElemType &e) / 若隊列不空，則刪除若隊列不空，則刪除Q的隊頭元素，的隊頭元素， /用用 e 返回

38、其值，并返回返回其值，并返回OK；否則返回；否則返回ERROR if (Q.front = Q.rear) return ERROR; p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = p) Q.rear = Q.front; free (p); return OK;3.4.2 鏈隊列鏈隊列p帶頭結(jié)點的鏈隊列出隊算法帶頭結(jié)點的鏈隊列出隊算法 53 第第3 3章章 棧和隊列棧和隊列DestroyQueue(&Q) /銷毀隊列銷毀隊列QueueEmpty(Q) /判隊列是否空判隊列是否空QueueLength

39、(Q) /求隊列長度求隊列長度GetHead(Q, &e) /取隊頭元素取隊頭元素ClearQueue(&Q) /清空隊列清空隊列QueueTravers(Q, visit() /遍歷隊列遍歷隊列3.4.2 鏈隊列鏈隊列p帶頭結(jié)點的鏈隊列其它操作討論帶頭結(jié)點的鏈隊列其它操作討論 54 第第3 3章章 棧和隊列棧和隊列3.4.3 循環(huán)隊列循環(huán)隊列 循環(huán)隊列屬于順序隊列的一種，討論在采用一般循環(huán)隊列屬于順序隊列的一種，討論在采用一般順序隊列時出現(xiàn)的問題。順序隊列時出現(xiàn)的問題。 p順序隊列討論順序隊列討論43210空隊列空隊列AA入隊入隊BAB入隊入隊EDCBAC,D,E相繼相繼入隊

40、入隊Sq.rearSq.frontSq.rearSq.frontSq.rearSq.frontSq.rearSq.front 55 第第3 3章章 棧和隊列棧和隊列EDCBA隊列滿隊列滿EDCBA被刪除被刪除(出隊出隊)EDCB被刪除被刪除討論結(jié)論：在采用一般順序隊列時出現(xiàn)假上溢現(xiàn)象？討論結(jié)論：在采用一般順序隊列時出現(xiàn)假上溢現(xiàn)象？C,D,E相繼相繼被刪除被刪除p順序隊列討論順序隊列討論3.4.3 循環(huán)隊列循環(huán)隊列43210Sq.rearSq.frontSq.frontSq.rearSq.rearSq.frontSq.frontSq.rear 56 第第3 3章章 棧和隊列棧和隊列p循環(huán)隊列示意

41、圖循環(huán)隊列示意圖3.4.3 循環(huán)隊列循環(huán)隊列01234CDESq.frontSq.rear01234CDESq.frontSq.rearFF入隊入隊01234CDESq.frontSq.rearFGG入隊入隊 57 第第3 3章章 棧和隊列棧和隊列3.4.3 循環(huán)隊列循環(huán)隊列#define MAXQSIZE 100 /最大隊列長度最大隊列長度 typedef struct QElemType *base; / 動態(tài)分配存儲空間動態(tài)分配存儲空間 int front; / 頭指針，若隊列不空，頭指針，若隊列不空， / 指向隊列頭元素指向隊列頭元素 int rear; / 尾指針，若隊列不空，指向尾

42、指針，若隊列不空，指向 隊列尾元素隊列尾元素 的下一個位置的下一個位置 SqQueue;SqQueue Sq;p鏈隊列數(shù)據(jù)類型實現(xiàn)鏈隊列數(shù)據(jù)類型實現(xiàn) 58 第第3 3章章 棧和隊列棧和隊列 循環(huán)隊列是順序隊列的一種特例，它是把順序隊循環(huán)隊列是順序隊列的一種特例，它是把順序隊列構(gòu)造成一個首尾相連的循環(huán)表。指針和隊列元素之列構(gòu)造成一個首尾相連的循環(huán)表。指針和隊列元素之間關(guān)系不變。間關(guān)系不變。3.4.3 循環(huán)隊列循環(huán)隊列p循環(huán)隊列的定義循環(huán)隊列的定義01maxsize-1Sq.frontSq.rear 59 第第3 3章章 棧和隊列棧和隊列3.4.3 循環(huán)隊列循環(huán)隊列p循環(huán)隊列空狀態(tài)和滿狀態(tài)的討論循

43、環(huán)隊列空狀態(tài)和滿狀態(tài)的討論討論結(jié)論：討論結(jié)論：循環(huán)隊列空狀循環(huán)隊列空狀態(tài)和滿狀態(tài)都態(tài)和滿狀態(tài)都滿足滿足Q.front=Q.rear01234CDESq.frontSq.rearFG滿隊列滿隊列01234Sq.frontSq.rear空隊列空隊列 60 第第3 3章章 棧和隊列棧和隊列 (1) 另設(shè)一個標(biāo)志區(qū)別隊列是空還是滿；另設(shè)一個標(biāo)志區(qū)別隊列是空還是滿；3.4.3 循環(huán)隊列循環(huán)隊列p循環(huán)隊列空狀態(tài)和滿狀態(tài)的判別循環(huán)隊列空狀態(tài)和滿狀態(tài)的判別 例如：設(shè)一個變量例如：設(shè)一個變量count用來記錄隊列中元素個用來記錄隊列中元素個數(shù)，當(dāng)數(shù)，當(dāng)count=0時隊列為空，當(dāng)時隊列為空，當(dāng)count= MAXQSIZE時隊列為滿。時隊列為滿。 61 第第3 3章章 棧和隊列棧和隊列 (2)隊滿條件：以隊頭指針在隊列尾指針的下隊滿條件：以隊頭指針在隊列尾指針的下一位置作為隊列呈滿狀態(tài)的標(biāo)志，犧牲一個存儲一位置作為隊列