數據結構課件 棧和隊列

1、第三章第三章 棧和隊列棧和隊列 本章學習兩種特殊的線性數據結構，它們特殊本章學習兩種特殊的線性數據結構，它們特殊在定義的操作不同，即插入和刪除操作只能在線在定義的操作不同，即插入和刪除操作只能在線性表的兩端進行。性表的兩端進行。 只能在一端進行的只能在一端進行的- 棧棧 分別在兩端進行的分別在兩端進行的- 隊列隊列 重點本章的學習重點在于掌握這兩種結構的特點，以便能在應用問題中正確使用。 知識點 順序棧、鏈棧、循環(huán)隊列、鏈隊列. 你見過餐館中一疊一疊的盤子嗎？如果它 們是按1,2,n 的次序往上疊的，那么使用時候 的次序應是什么樣的？. 在日常生活中，為了維持正常的社會秩序 而出現(xiàn)的常見現(xiàn)象是

2、什么？ 棧和隊列是在程序設計中被廣泛使用的兩種線性數據結構棧必須按“后進先出”的規(guī)則進行操作，而隊列必須按“先進先出”的規(guī)則進行操作。和線性表相比，它們的插入和刪除操作受更多的約束和限定，故又稱為限定性的線性表結構。 插 入 刪 除線性表： Insert(L,i,x) Delete(L,i) (1in+1) (1in)棧：Insert(L,n+1,x) Delete(L,n)隊列：Insert(L,n+1,x) Delete(L,1)第三章第三章 棧和隊列棧和隊列 3.1 棧棧1 、棧（、棧（stack) ：是一種特殊的線性表（數：是一種特殊的線性表（數據元素之間的關系是線性關系），據元素之間

3、的關系是線性關系），其插入、其插入、刪除只能在表的一端進行，另一端固定不動。刪除只能在表的一端進行，另一端固定不動。棧頂（棧頂（top ) ：插入、刪除的一端；：插入、刪除的一端；棧底（棧底（bottom ) ：固定不動的一端；：固定不動的一端；入棧（入棧（push ) ：又稱壓入，即插入一個元素；：又稱壓入，即插入一個元素；出棧（出棧（pop) ：又稱彈出，即刪除一個元素；：又稱彈出，即刪除一個元素； 一、抽象數據類型棧的定義一、抽象數據類型棧的定義2 、說明：設（說明：設（a1, a2, a3, , an ） 是一個棧是一個棧 （a1, a2, . , ai -1, ai , ai+1,

4、, an ）棧棧底底棧棧頂頂進棧進棧出棧出棧1）表尾稱為棧頂，表頭稱為棧底）表尾稱為棧頂，表頭稱為棧底 ，即，即a1為棧底元素，為棧底元素，an為棧頂元素為棧頂元素;2）在表尾插入元素的）在表尾插入元素的 操作稱進棧操作，在表頭刪除元素的操作稱為操作稱進棧操作，在表頭刪除元素的操作稱為出棧操作出棧操作;3）元素按）元素按a1, a2, a3, , an 的次序進棧的次序進棧, 第一個進棧的元素一定在第一個進棧的元素一定在棧底，最后一個進棧的元素一定在棧頂棧底，最后一個進棧的元素一定在棧頂, 第一個出棧的元素為棧頂元素；第一個出棧的元素為棧頂元素；棧的示意圖棧的示意圖棧特點：由于限制了插入刪除只

5、能在一端進行，那棧特點：由于限制了插入刪除只能在一端進行，那么元素的操作順序有么元素的操作順序有“先進后出先進后出”或或“后進先出后進先出”的特點的特點(Last In First out-LIFO First In Last out -FILO ) 第一個進棧的元素在第一個進棧的元素在棧底，最后一個進棧棧底，最后一個進棧的元素在棧頂，第一的元素在棧頂，第一個出棧的元素為棧頂個出棧的元素為棧頂元素，最后一個出棧元素，最后一個出棧的元素為棧底元素的元素為棧底元素課堂練習課堂練習假設有假設有A ， B , C , D 四個元素；它們入棧次四個元素；它們入棧次序為序為A一一 B 一一C 一一D 出棧

6、次序任意，出棧次序任意，請問不可能得到下面哪些出棧序列？請問不可能得到下面哪些出棧序列？( 1 ) A B C D ( 2 ) D B C A ( 3 ) C D B A ( 4 ) C B A D (5 ) A C B D ( 6 ) D B A C ( 7 ) A D C B ( 8 ) C A B D 3 、 棧的基本操作棧的基本操作 1） 初始化操作初始化操作InitStack(&S) 功能：構造一個空棧功能：構造一個空棧S； 2） 銷毀棧操作銷毀棧操作DestroyStack(&S) 功能：銷毀一個已存在的棧功能：銷毀一個已存在的棧; 3） 置空棧操作置空棧操作Cle

7、arStack(&S) 功能：將棧功能：將棧S置為空棧置為空棧; 4）判空棧操作）判空棧操作StackEmpty(S) 功能：若棧為空棧，返回功能：若棧為空棧，返回TRUE，否則，否則FALSE 5）取長度操作）取長度操作StackLength(S) 功能：返回棧功能：返回棧S的元素個數的元素個數 6）取棧頂元素操作）取棧頂元素操作GetTop(S, &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e 返回返回;7）進棧操作）進棧操作Push(&S, e)功能：元素功能：元素e進棧進棧;8）退棧操作）退棧操作Pop(&S, &e) 功能：棧頂元素退棧

8、，并用功能：棧頂元素退棧，并用e返回返回;7）棧遍歷）棧遍歷StackTraverse(S) 功能：從棧底到棧頂依次調用函數功能：從棧底到棧頂依次調用函數visit().4、棧的ADT描述棧的抽象數據類型定義為： ADT Stack 數據對象：Dai|aiElemSet, i=1,2,.,n, n0 數據關系：R1 | ai-1 , ai D, i=2,.,n 約定an端為棧頂,a1端為棧底?；静僮鳎夯静僮鳎? ADT Stack 二 棧的存儲表示和操作的實現(xiàn)和線性表類似，棧也有兩種存儲表示，其順序存儲結構簡稱為順序棧順序棧。和順序表類似，對順序棧也需要事先為它分配一個可以容納最多元素的存

9、儲空間。 順序存儲方式：順序存儲方式：同一般線性表的順序存儲結構同一般線性表的順序存儲結構完全相同。完全相同。是利用一組連續(xù)的內存單元依次存放是利用一組連續(xù)的內存單元依次存放自棧底到棧頂的數據元素自棧底到棧頂的數據元素，棧頂元素的位置由一，棧頂元素的位置由一個稱為棧頂指針的變量指示個稱為棧頂指針的變量指示 。 實際是棧中元素的個數 順序棧類型的定義 / 結構定義： typedef struct ElemType *base; / 存儲空間基址 int top; / 棧頂指針 int stacksize; / 允許的最大存儲空間 Stack; 棧頂指針總是指在棧頂元素的后面一個位置上 top=0

10、123450?？誸op123450進棧Atop出棧棧滿BCDEF設數組維數為stacksizetop=0,?？?，此時出棧，則下溢（underflow)top= stacksize,棧滿，此時入棧，則上溢（overflow)toptoptoptoptop123450ABCDEFtoptop特點：簡單、方便，但易產生溢出。特點：簡單、方便，但易產生溢出。上溢（上溢（Overflow ) 棧已經滿，又要壓入元素；棧已經滿，又要壓入元素； 下溢（下溢（Underflow ) 棧已經空，還要彈出元素；棧已經空，還要彈出元素；注：上溢是一種錯誤，使問題的處理無法進行下去；注：上溢是一種錯誤，使問題的處理無

11、法進行下去；而下溢一般認為是一種結束條件，即問題處理結束。而下溢一般認為是一種結束條件，即問題處理結束。# #define STACK_INIT_SIZE 100define STACK_INIT_SIZE 100/棧存儲空間的初始分配量棧存儲空間的初始分配量# #define STACKINCREMENT 10define STACKINCREMENT 10/ / 棧存儲空間的分配增量棧存儲空間的分配增量typedef structtypedef structSElemType SElemType * *base;base;/棧空間基址?？臻g基址稱為棧底指針，指向棧底位置稱為棧底指針，指向棧

12、底位置SElemType SElemType * *top top /棧頂指針棧頂指針, ,約定棧頂指針指向棧頂元素的約定棧頂指針指向棧頂元素的 /下（后面）一個位置；下（后面）一個位置； int stacksize; int stacksize; /當前分配的?？臻g大小當前分配的棧空間大小 / /（以（以sizeof(SElemType)sizeof(SElemType)為單位為單位） SqStackSqStack;/ ;/ SqStack:：結構類型名結構類型名順序棧的存儲表示順序棧的存儲表示 n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksi

13、zeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE初始化操作圖示初始化操作圖示順序?；静僮鞯乃惴樞驐；静僮鞯乃惴?）初始化操作）初始化操作InitStack_Sq(SqStack &S) 參數：參數：S是存放棧的結構變量；是存放棧的結構變量； 功能：建一個空棧功能：建一個空棧S；Status InitStack_Sq(SqStack &S) /構造一個空棧構造一個空棧S S.base=(SElemType * )malloc(STACK_INIT_SIZE * sizeof(SElemType); /為順序棧動態(tài)

14、分配存儲空間為順序棧動態(tài)分配存儲空間 if (! S. base) exit(OVERFLOW); /存儲分配失敗存儲分配失敗 S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /InitStack_SqStatus DetroyStack_Sq ( SqStack &S) If (!S.base) return ERROR; /若棧未建立（尚未分配?？臻g）若棧未建立（尚未分配棧空間） free (S.base); / 回收?？臻g回收?？臻g S.base = S.top = null; S.stacksize = 0; retu

15、rn OK; / DetroyStack_Sq2） 銷毀棧操作銷毀棧操作 DestroyStack_Sq(SqStack &SSqStack &S ) 功能：銷毀一個已存在的棧功能：銷毀一個已存在的棧;S.top = nullS.top = nullS.stacksizeS.stacksizeS.base = nullS.base = null 0 0 n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_IN

16、IT_SIZESTACK_INIT_SIZE 銷毀前銷毀前 銷毀后銷毀后銷毀棧操作圖示銷毀棧操作圖示3）置空棧操作置空棧操作ClearStack_Sq(SqStack &S) 功能：將棧功能：將棧S置為空棧置為空棧 算法算法 Status ClearStack_Sq ( SqStack &S) If (!S.base) return ERROR; / 若棧未建立（尚未分若棧未建立（尚未分 /配?？臻g）配?？臻g） S.top = S.base ; return OK; / ClearStack_Sq n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na ai

17、ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZE n nn-1n-1i-1i-1i-2i-2 1 1 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a2 2a a1 1置空棧操作圖示置空棧操作圖示S.base=S.topS.base=S.top表明棧為空表明棧為空置空前置空前置空后置空后Status

18、GetTop_Sq(SqStack S, SelemType &e) / 若棧不空，則用若棧不空，則用e返回返回S的棧頂元素，并返回的棧頂元素，并返回/OK；否則返回否則返回ERROR if (S.top= =S.base) return ERROR; /若棧為空若棧為空 e = * (S.top-1); return OK;/GetTop_Sq4） 取棧頂元素操作取棧頂元素操作GetTop_Sq(SqStack S, SElemType &e) 功能：取棧頂元素，并用功能：取棧頂元素，并用e返回返回; n nn-1n-1i-1i-1i-2i-2 1 1 0 0a an na

19、ai ia ai-1i-1a a2 2a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an n 取棧頂元素操作圖示取棧頂元素操作圖示5）進棧操作進棧操作Push(SqStack &S, SElemType eSqStack &S, SElemType e) 功能：元素功能：元素e 進棧進棧; 進棧操作主要步驟：進棧操作主要步驟： 1）S是否已滿，是否已滿， 若若棧棧滿，重新分配存儲空間；滿，重新分配存儲空間； 2）將元素將元素e 寫入棧頂；寫入棧頂； 3）修

20、改棧頂指針，使棧頂指針指向棧頂元素的）修改棧頂指針，使棧頂指針指向棧頂元素的下（后面）一個位置；下（后面）一個位置； n nn-1n-1i-1i-1i-2i-2 0 0n+1n+1n nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEe ea an na ai ia ai-1i-1a a1 1anana ai ia ai-1i-1a a1 1S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_S

21、IZESTACK_INIT_SIZE e 進棧前進棧前 e 進棧后進棧后 進棧操作圖示進棧操作圖示Status Push(SqStack &S, SElemType e) /將元素將元素e插入棧成為新的棧頂元素插入棧成為新的棧頂元素,要考慮上溢情況要考慮上溢情況 if (S.top-S.base=S.stacksize) /棧滿，追加存儲空間棧滿，追加存儲空間 S.base= (SElemType * )realloc(S.base, (S.stacksize +STACKINCREMENT) sizeof(ElemType); if (! S. base) exit(OVERFLOW

22、); /存儲分配失敗存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /元素元素e 插入棧頂，修改棧頂指針插入棧頂，修改棧頂指針 return OK; /Push進棧操作算法：進棧操作算法：Status Pop(SqStack &S, SElemType &e) /若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用e 返回其值并返回返回其值并返回OK /否則返回否則返回ERROR if (S.top= = S.base) return ERROR; /?？眨祷貤？?，返回

23、ERROR e = * -S.top; /刪除棧頂元素，用刪除棧頂元素，用e 返回其值，并修返回其值，并修 /改棧頂指針改棧頂指針 return OK; /Pop6）出）出棧操作棧操作Pop(SqStack &S, SElemType &e )功能：棧頂元素退棧，并用功能：棧頂元素退棧，并用e 返回返回;S.topS.topS.stacksizeS.stacksizeS.baseS.base n nn-1n-1i-1i-1i-2i-2 0 0a an na ai ia ai-1i-1a a1 1STACK_INIT_SIZESTACK_INIT_SIZE 出棧操作前出棧操作前n

24、 nn-1n-1i-1i-1i-2i-2 0 0S.topS.topS.stacksizeS.stacksizeS.baseS.baseSTACK_INIT_SIZESTACK_INIT_SIZEa an na ai ia ai-1i-1a a1 1 出棧操作后出棧操作后a an ne e出棧操作圖示出棧操作圖示鏈棧鏈棧即為棧的鏈式存儲結構。 鏈棧的結點結構和單鏈表中的結點結構相同。由于棧只在棧頂作插入和刪除操作，因此鏈棧中不需要頭結點，但是鏈棧中指針的方向是從棧頂指向棧底的，這正好和單鏈表是相反的。 鏈棧中結點的定義： 鏈棧結構定義：typedef struct LNode ElemType

25、 data; struct LNode *next;* SLink;typedef struct SLink top; /棧頂指針 int length; /棧中元素個數LStack;鏈棧的基本操作和順序棧操作基本相同，只需修改兩處：初始化時不需要maxsize的參數在進行入棧操作時不需要顧忌棧的空間是否已經被填滿。void InitStack ( LStack &S ) / 構造一個空棧構造一個空棧 SS.top = NULL; / 設棧頂指針的初值為空S.length = 0; / 空棧中元素個數為0 / InitStack void Push ( LStack &S, E

26、lemType e )/ 在棧頂之上插入元素在棧頂之上插入元素 e 為新的棧頂元素為新的棧頂元素p = (LNode *)malloc(sizeof(LNode); / 建新的結點if(!p) exit(1);/ 存儲分配失敗p - data = e;p - next = S.top;/ 鏈接到原來的棧頂S.top = p; / 移動棧頂指針+S.length; / 棧的長度增1 / Push .棧底toptopxpbool Pop ( LStack &S, ElemType &e ) / 若棧不空，則刪除若棧不空，則刪除S的棧頂元素，用的棧頂元素，用 e 返回其值，返回其值，

27、/ 并返回并返回 TRUE；否則返回；否則返回 FALSEif ( !S.top )return FALSE; else e = S.top - data; / 返回棧頂元素 q = S.top; S.top = S.top - next;/ 修改棧頂指針 -S.length; / 棧的長度減1 delete q; / 釋放被刪除的結點空間 return TRUE; / Pop top .棧底topq 小小 結結 1.棧是限定僅能在表尾一端進行插入、 刪除操作的線性表；2. 棧的元素具有后進先出的特點；3. 棧頂元素的位置由一個稱為棧頂指針的變量表示，進棧、出棧操作要修改棧頂指針；3.2 棧的

28、應用舉例棧的應用舉例 N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2輸出順序輸出順序計算順序計算順序數制轉換 十進制數N和其他d進制數的轉換是計算機實現(xiàn)計算的基本問題，其解決方法很多，其中一個簡單算法基于下列原理：N = (N div d)d + N mod d (其中：div 為整除運算，mod 為求余運算)例如：(1348)10 = (2504)8 由上述求解過程可以看出，在計算過程中是從低由上述求解過程可以看出，在計算過程中是從低位到高位順序產生八進制數的各個數位，而顯示位到高位順序產生八進制數的各個數位，而顯示時按照我們的習慣是高位

29、在前，低位在后，即按時按照我們的習慣是高位在前，低位在后，即按從高位到低位的順序輸出從高位到低位的順序輸出, 即后計算出的（高）位即后計算出的（高）位數先輸出，具有數先輸出，具有后進先出后進先出的特點，因此可將計算的特點，因此可將計算過程中得到的八進制數順序進棧，出棧序列打印過程中得到的八進制數順序進棧，出棧序列打印輸出的就是對應的八進制數。輸出的就是對應的八進制數。3） 算法算法void conversion( ) /對于輸入的任意一個非負十對于輸入的任意一個非負十/進制整數，打印輸出與其等值的八進制數進制整數，打印輸出與其等值的八進制數 InitStack(S); /建空棧建空棧 scan

30、f(“%d”, N); /輸入一個輸入一個非負十進制整數非負十進制整數 while(N) / N不等于零不等于零，循環(huán)，循環(huán) Push(S, N % 8); / N/8第一個余數進棧第一個余數進棧 N=N/8 ; /整除運算整除運算 while(! StackEmpty) /輸出存放在棧中的八進制數。輸出存放在棧中的八進制數。 Pop(S, e); Printf(“%d”, e); /conversion 2 表達式求值表達式求值1） 表達式的構成表達式的構成 操作數操作數+運算符運算符+界符（如括號）界符（如括號）2） 表達式的求值：表達式的求值： 例例 5+6 (1+2)- 4 按照四則運

31、算法則，上述表達式的計算過程為：按照四則運算法則，上述表達式的計算過程為： 5+6 (1+2)- 4=5+6 3- 4 = 5+18-4= 23-4=19 表達式中運算符的運算順序為：表達式中運算符的運算順序為： + ， ， +， -如何確定運算符的運算順序？如何確定運算符的運算順序？3） 算符優(yōu)先關系表算符優(yōu)先關系表 表達式中任何相鄰運算符表達式中任何相鄰運算符 1、 2的優(yōu)先關系有：的優(yōu)先關系有： 1 2： 1的優(yōu)先級高于的優(yōu)先級高于 2 由四則運算法則，可得到如下的算符優(yōu)先關系表：由四則運算法則，可得到如下的算符優(yōu)先關系表：+ 21- -* */ /( () )# #+ - + - *

32、* / ( ) # / ( ) # = = = 算符間的優(yōu)先關系表算符間的優(yōu)先關系表注：注： 1 2是相鄰算符，是相鄰算符，1在左在左 2在右在右4) 算符優(yōu)先算法算符優(yōu)先算法 我們再來分析一下表達式我們再來分析一下表達式5+4 (1+2)- 6 計算過程：計算過程： 從左向右掃描表達式：從左向右掃描表達式： 遇操作數遇操作數保存；保存；遇運算符號遇運算符號 j與前面的剛掃描過的運算符與前面的剛掃描過的運算符 i比較比較 若若 i j 則保存則保存 j，（，（ 因此已保存的運算符的優(yōu)先關系為因此已保存的運算符的優(yōu)先關系為 1 2 3 j 則說明則說明 i是已掃描的運算符中優(yōu)先級最高者，可進行運

33、算；是已掃描的運算符中優(yōu)先級最高者，可進行運算； 若若 i = j 則則 i為（，為（， j 為為 ），說明括號內的式子已計算完，需要消去括），說明括號內的式子已計算完，需要消去括號；號； 5+4 (1+2)- 6后面也許有優(yōu)先后面也許有優(yōu)先級更大的算符級更大的算符算法思想：(1) 設置兩個棧：運算符棧（OPTR)和操作數棧（OPND)(2)設置數據棧為空棧，表達式起始符“#”為算符棧的棧底元素。(3)自左向右，依次掃描表達式中的基本符號，若掃描的基本符號為操作數，則將操作數入OPND棧。(4)若基本符號為運算符，則和OPTR棧頂元素的優(yōu)先級比較（棧頂元素為C1,讀到的算符為C2）： （a）c

34、1c2，c1出棧，從OPND棧取出兩個元素（a和b），按c1進行運算，并把運算結果放入OPND棧。(5)重復上述過程，直到表達式求值完畢（OPTR棧為空棧）表達式求值示意圖：表達式求值示意圖：5+65+6 (1+2)-4 (1+2)-4 toptopbasebaseOPTROPTR棧棧# #OPNDOPND棧棧toptopbasebase5 5toptoptoptop+ +toptop6 6toptoptoptop( (toptop1 1toptop+ +toptop2 2toptoptoptoptoptoptoptop3 3toptoptoptoptoptoptoptoptoptop1818

35、toptoptoptoptoptoptoptop2323toptop- -toptop4 4toptoptoptoptoptoptoptop1919toptoptoptoptoptop5 5讀入表達式過程：讀入表達式過程： + +6 6( (1 1+ +2 2) )- -4 4# #=19=191+2=36 63=183=185+18=235+18=2323-4=1923-4=193.4 棧的應用舉例棧的應用舉例 在算符優(yōu)先算法中，建立了兩個工作棧。一個是在算符優(yōu)先算法中，建立了兩個工作棧。一個是OPTR棧，用以保存棧，用以保存運算符運算符,一個是一個是OPND棧，用以保存操作數或運算結果。棧

36、，用以保存操作數或運算結果。 operandType EvaluateExpression( ) /算術表達式求值的算符優(yōu)先算法。設算術表達式求值的算符優(yōu)先算法。設OPTR和和OPND分別為運算符棧分別為運算符棧和運算數棧，和運算數棧，OP為運算符集合。為運算符集合。 InitStack(OPTR); Push (OPTR, #); InitStack(OPND); c=qetchar( ); While(c!= # | GetTop(OPTR)!=#) if (! In (c, OP) Push(OPND, c); c=getchar( ) /不是運算符則進棧不是運算符則進棧,In(c, O

37、P)判斷判斷c是否是運算符的函數是否是運算符的函數 else 續(xù)續(xù) switch (Precede(GetTop(OPTR), c) case : /新輸入的算符新輸入的算符c優(yōu)先級低，即棧頂算符優(yōu)先權優(yōu)先級低，即棧頂算符優(yōu)先權 /高高,出棧并將運算結果入棧出棧并將運算結果入棧OPND Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch /while return GetTop(OPND); /EvaluateExpression3括弧匹配檢驗 假設表達式中

38、允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（ ）或（ （ ）或 ( ( ) ) ）均為錯誤的匹配。問題：如何檢驗一個給定表達式中的括弧是否正確匹配？解決辦法：用期待的急迫程度這個概念來描述。 對于后出現(xiàn)的左括號,它等待與其匹配的右括號出 現(xiàn)的急迫心情要比先出現(xiàn)的左括號高,也就是說,對 左括號來說,后出現(xiàn)的比先出現(xiàn)的優(yōu)先等待檢測. 對右括號來說,每個出現(xiàn)的右括號要去找在它之前最后出現(xiàn)的那個左括號去匹配.例如考慮下列括號序列： ( ) 1 2 3 4 5 6 7 8顯然,必須將先后出現(xiàn)的左括號依次保存,為了反映這個優(yōu)先程度,保存左括號的結構應該使用棧 對

39、于出現(xiàn)的右括號來說,只要棧頂元素相匹配即可.如果棧頂的左括號正好和它匹配,就可將它從棧頂刪除.什么樣的情況是“不匹配”的情況呢？1和棧頂的左括弧不相匹配；2棧中并沒有左括弧等在那里；3棧中還有左括弧沒有等到和它相匹配的右括弧。Bool match()InitStack(S); /初始化棧初始化棧 ch=getchar(); /接收第一個括號接收第一個括號 while(ch!=#) /不是結束符不是結束符 if(ch=(|ch=) /左括號時進棧左括號時進棧 push(S,ch); /if else if(ch=) /) 時檢測匹配時檢測匹配 if(!StackEmpty(S) gettop(S

40、,e); /取棧頂元素取棧頂元素 if(e=() /匹配成功匹配成功 pop(S); /if else return false; /匹配失敗匹配失敗 /if /elseElse /時檢測匹配時檢測匹配 if(!StackEmpty(S) gettop(S,e); /取棧頂元素取棧頂元素 if(e=) /匹配成功匹配成功 pop(S); /if else return false; /匹配失敗匹配失敗 /if /else ch=getchar();/whileIf(!StackEmpty(S) return false; /棧中還有沒有匹配棧中還有沒有匹配 /成功的左括號成功的左括號 else

41、 return true;/match算法實現(xiàn)算法實現(xiàn)4.迷宮求解問題計算機解迷宮時，通常用的是“窮舉求解窮舉求解”的方法. 1進入迷宮之后，不管在迷宮的哪一個位置上，都先往東走，如果走得通就繼續(xù)往東走，如果在某個位置上往東走不通的話，就依次試探往南、往西和往北方向，從一個走得通的方向繼續(xù)往前直到出口為止；2如果某個位置上四個方向都走不通的話，就退回到前一個位置，換一個方向再試，如果這個位置已經沒有方向可試了就再退一步，如果所有已經走過的位置的四個方向都試探過了，一直退到起始點都沒有走通，那就說明這個迷宮根本不通； 為了保證在任何位置上都能沿原路退回，需要用 一個“后進先出”的結構即棧來保存從

42、入口到當前 位置的路徑。并且在走出出口之后，棧中保存的 正是一條從入口到出口的路徑。算法的基本思想是：若當前位置“可通”，則納入“當前路徑”，并繼續(xù)朝“下一位置”探索；若當前位置“不可通”，則應順著“來的方向”退回到“前一通道塊”，然后朝著除“來向”之外的其他方向繼續(xù)探索；若該通道塊的四周四個方塊均“不可通”，則應從“當前路徑”上刪除該通道塊。 偽碼算法 ：設定當前位置的初值為入口位置； do 若當前位置可通， 則將當前位置插入棧頂； / 納入路徑 若該位置是出口位置，則算法結束； 否則切換當前位置的東鄰方塊為新的當前位置； 否則 若棧不空且棧頂位置尚有其他方向未被探索， 則設定新的當前位置為

43、: 沿順時針方向旋轉找到的棧頂位置的下一相鄰塊；若棧不空但棧頂位置的四周均不可通， 則 刪去棧頂位置； / 從路徑中刪去該通道塊若棧不空，則重新測試新的棧頂位置， 直至找到一個可通的相鄰塊或出棧至?？?； while (棧不空)； 沒有路徑存在3.3 棧與遞歸 由上看到：應用中如果處理數據處理過程具有后由上看到：應用中如果處理數據處理過程具有后進先出的特性，可利用棧來實現(xiàn)數據處理過程。下進先出的特性，可利用棧來實現(xiàn)數據處理過程。下面我們將看到可以用棧來實現(xiàn)遞歸。面我們將看到可以用棧來實現(xiàn)遞歸。1什么是遞歸什么是遞歸 遞歸是一個很有用的工具，在數學和程序設計等許多遞歸是一個很有用的工具，在數學和程

44、序設計等許多領域中都用到了遞歸。遞歸定義：簡單地說，一個領域中都用到了遞歸。遞歸定義：簡單地說，一個用自己定義自己的概念用自己定義自己的概念,稱為遞歸定義。稱為遞歸定義。例例 n!= 1 2 3 4 (n-1) n n!遞歸定義遞歸定義 n!= 1 當當 n=0時時 n!= n (n-1)! 當當n 0時時用(n-1)!定義n!棧與遞歸2.遞歸函數遞歸函數：一個直接調用自己或通過一系列調用：一個直接調用自己或通過一系列調用間接調用自己的函數稱為遞歸函數。間接調用自己的函數稱為遞歸函數。 A（ ） A( ) ; B( ) C( ) C( ); B( ); A 直接調用自己直接調用自己B間接調用自

45、己間接調用自己棧與遞歸遞歸是程序設計中的有用工具，下面舉例說明遞歸算法的編寫遞歸是程序設計中的有用工具，下面舉例說明遞歸算法的編寫和執(zhí)行過程。和執(zhí)行過程。2遞歸算法的編寫遞歸算法的編寫1）將問題用遞歸的方式描述（定義）將問題用遞歸的方式描述（定義）2）根據問題的遞歸描述（定義）編寫遞歸算法）根據問題的遞歸描述（定義）編寫遞歸算法 問題的遞歸描述（定義）問題的遞歸描述（定義） 遞歸定義包括兩項遞歸定義包括兩項 基本項（終止項）基本項（終止項）：描述遞歸終止時問題的求解；：描述遞歸終止時問題的求解； 遞歸項：遞歸項：將問題分解為與原問題性質相同，但規(guī)模較小將問題分解為與原問題性質相同，但規(guī)模較小

46、的問題；的問題； 棧與遞歸棧與遞歸例例1 編寫求解編寫求解 階乘階乘n! 的遞歸算法的遞歸算法首先給出階乘首先給出階乘n! 的遞歸定義的遞歸定義 n!的遞歸定義的遞歸定義 基本項：基本項： n!=1 當當 n=1 遞歸項：遞歸項： n!=n (n-1)! 當當 n 1 有了問題的遞歸定義，很容易寫出對應的遞歸算法：有了問題的遞歸定義，很容易寫出對應的遞歸算法：int fact (int n) /算法功能是求解并返回算法功能是求解并返回n的階乘的階乘 If（n=1） return（1）；）； Else return（n*fact (n-1)）；）；/fact 棧與遞歸棧與遞歸例例2. 編寫求解編

47、寫求解Hanoi塔問題的遞歸算法塔問題的遞歸算法 有三個各為有三個各為X，Y，Z的塔座，在的塔座，在X項有項有n個大小不個大小不同，依小到大編號為同，依小到大編號為1，2n的圓盤。的圓盤。 現(xiàn)要求將現(xiàn)要求將X上上的的n個圓盤移至個圓盤移至Z上，并仍以同樣順序疊放，上，并仍以同樣順序疊放， 圓盤移動圓盤移動時必須遵守下列原則：時必須遵守下列原則：1）每次移動一個盤子；）每次移動一個盤子；2）圓盤可以放在）圓盤可以放在X，Y，Z中的任一塔座上；中的任一塔座上；3）任何時刻都不能將較大的圓盤壓放在較小圓盤之上；）任何時刻都不能將較大的圓盤壓放在較小圓盤之上；例例 n=3時圓盤移動的過程如下圖所示時圓

48、盤移動的過程如下圖所示：abc321 11213121棧與遞歸棧與遞歸Y YX XZ Z棧與遞歸棧與遞歸首先給出求解首先給出求解Hanoi塔問題塔問題 的遞歸描述（定義）的遞歸描述（定義） 基本項：基本項： n=1時，將時，將n號圓盤從號圓盤從X移至移至Z； 遞歸項：遞歸項： n1時，時， 將將X上上1n-1號圓盤移至號圓盤移至Y； 將將X上的上的n號圓盤從號圓盤從X移至移至Z; 將將Y上上1n-1號圓盤從號圓盤從Y移至移至Z; 將規(guī)模為將規(guī)模為n n的的問題的求解歸問題的求解歸結為規(guī)模為結為規(guī)模為n-n-1 1的問題的求的問題的求解解有了問題的遞歸定義，很容易寫出對應的遞歸有了問題的遞歸定義

49、，很容易寫出對應的遞歸算法：算法：void hanoi (int n, char x, char y, char z) /將塔座將塔座x上按直徑由小到大且自上而下編號為上按直徑由小到大且自上而下編號為1至至n的的n個圓盤按規(guī)則搬到塔座個圓盤按規(guī)則搬到塔座z上，上，y可用作輔助塔座。可用作輔助塔座。 if (n= =1) move(x,1,z); /將編號為將編號為1的圓盤從的圓盤從x移動移動z else hanoi(n-1, x, z, y); /將將x上編號為上編號為1至至n-1的圓盤移到的圓盤移到y(tǒng), z作輔助塔作輔助塔 move(x, n, z); /將編號為將編號為 n的圓盤從的圓盤從

50、x移到移到z hanoi(n-1, y, x, z)； /將將y上編號為上編號為1至至n-1的圓盤移到的圓盤移到z，x作輔助塔作輔助塔 棧與遞歸棧與遞歸3 遞歸函數的實現(xiàn)遞歸函數的實現(xiàn)先看一般函數的調用機制如何實現(xiàn)的。先看一般函數的調用機制如何實現(xiàn)的。 A( )B( );C( )B( )C( );調用調用返回返回函數調用順序 A B C函數返回順序 C B A后調用的函數先返回后調用的函數先返回 函數調用機制可通過棧來實現(xiàn)函數調用機制可通過棧來實現(xiàn)計算機正是利用棧來實現(xiàn)函計算機正是利用棧來實現(xiàn)函數的調用和返回的數的調用和返回的棧與遞歸棧與遞歸我們看一下我們看一下n=3 n=3 階乘函數階乘函數

51、fact(n)fact(n)的執(zhí)行過程的執(zhí)行過程Main( ) int n=3,y;L y= fact(n);調調用用調用調用int fact (n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=3int fact (int n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=2int fact (int n) If（n=1） return（1）； Else L1 return（n*fact (n-1)）；/factn=1L 3L 3L1 1L1 1L1 2L1 2

52、返回1 1返回2 2返返回回6 61 1n*fact (n-1)n*fact (n-1)fact(n)返回地址 實參 注意遞歸調用中 棧的變化2 、隊列的特點：由于限制了插入、刪除分別在兩端進行，、隊列的特點：由于限制了插入、刪除分別在兩端進行，那么元素的操作順序有那么元素的操作順序有“先進先出先進先出”或或“后進后出后進后出”的特點的特點（First In First Out-FIFO Last In Last Out - LILO） 1 、隊列（、隊列（Queue ) ：是一種特殊的線性表是一種特殊的線性表(數據元數據元 之間的關系是線性關系之間的關系是線性關系.其插入、刪除分別在表的其插

53、入、刪除分別在表的兩端進行，一端只能插入、另一端只能刪除。兩端進行，一端只能插入、另一端只能刪除。)隊首（隊首（front ) ：進行刪除的一端；：進行刪除的一端；隊尾（隊尾（rear ) ：進行插入的一端；：進行插入的一端；入隊：在隊尾插入一個元素；入隊：在隊尾插入一個元素；出隊：在隊首刪除一個元素；出隊：在隊首刪除一個元素；3.4隊列3.4.13.4.1抽象數據類型隊列的定義抽象數據類型隊列的定義 a1 a2 a3 an入隊列隊頭隊尾出隊列隊列的示意圖隊列的示意圖隊列的特點隊列的特點先進先出先進先出第一個入隊的元素在隊頭，第一個入隊的元素在隊頭，最后一個入隊的元素在隊尾，最后一個入隊的元素

54、在隊尾，第一個出隊的元素為隊頭元素，第一個出隊的元素為隊頭元素，最后一個出隊的元素為隊尾元素最后一個出隊的元素為隊尾元素 隊列類似于日常的排隊，新來的人站在隊尾，隊頭的人進隊列類似于日常的排隊，新來的人站在隊尾，隊頭的人進行事務處理后離隊。行事務處理后離隊。 隊列通常設置兩個變量分別指示隊頭元素位置和隊尾元素隊列通常設置兩個變量分別指示隊頭元素位置和隊尾元素的位置，這兩個變量分別稱為隊頭指針、隊尾指針；的位置，這兩個變量分別稱為隊頭指針、隊尾指針；2. 隊列的基本操作隊列的基本操作1）初始化操作）初始化操作InitQueue( &Q) 功能：構造一個空隊列功能：構造一個空隊列Q；2）銷

55、毀操作銷毀操作DestroyQueue( &Q) 功能：銷毀已存在隊列功能：銷毀已存在隊列Q；3）置空操作置空操作ClearQueue(&Q) 功能：功能： 將隊列將隊列Q置為空隊列置為空隊列 ；4）判空操作）判空操作QueueEmpty(Q) 功能：若隊列功能：若隊列Q為空，則返回為空，則返回True，否則返回否則返回False； 5）取隊頭元素操作取隊頭元素操作GetHead(Q,&e) 功能：取隊頭元素，并用功能：取隊頭元素，并用e返回；返回；6）入隊操作入隊操作EnQueue( &Q, e ) 功能：將元素功能：將元素e插入插入Q的隊尾；的隊尾；7）出隊

56、操作）出隊操作DeQueue( &Q, &e) 功能：若隊列不空，則刪除功能：若隊列不空，則刪除Q的隊頭元素，用的隊頭元素，用e返返回其值，并返回回其值，并返回OK，否則返回否則返回ERROR；隊列的抽象數據類型定義： ADT Queue 數據對象：數據對象：Dai|aiElemSet, i=1,2,.,n, n0 數據關系：數據關系：R1 | ai-1,ai D, i=2,.,n約定其中a1端為隊列頭，an端為隊列尾基本操作： InitQueue(&Q) DestroyQueue(&Q) ClearQueue(&Q)QueueEmpty(Q)Queue

57、Length(Q)GetHead(Q,&e)EnQueue(&Q,e) DeQueue(&Q,&e)QueueTraverse(Q,visit( ) ADT Queue 3.隊列隊列ADT應用舉例應用舉例 打印機隊列管理：打印機隊列管理：在一臺打印機共享使用時，任何在一臺打印機共享使用時，任何時刻它只能處理一個用戶的打印請求。打印任務的組時刻它只能處理一個用戶的打印請求。打印任務的組織就用一個隊列來組織（先請求的，先處理）?？椌陀靡粋€隊列來組織（先請求的，先處理）。當用戶發(fā)出打印請求時，把打印任務當用戶發(fā)出打印請求時，把打印任務入隊入隊；當打印機空閑時，從打印隊

58、列中當打印機空閑時，從打印隊列中出隊出隊一個任務；一個任務；當打印機阻塞時當打印機阻塞時,系統(tǒng)管理員可以系統(tǒng)管理員可以清空隊列清空隊列.1 、存儲方式：同一般線性表的順序存儲結構完全、存儲方式：同一般線性表的順序存儲結構完全相同。但是由于在兩端操作，設兩個指示器，相同。但是由于在兩端操作，設兩個指示器，(rear 和和front ）分別指示隊列的尾和首。）分別指示隊列的尾和首。特別約定特別約定:頭指針始終指向隊列頭元素，而尾指針頭指針始終指向隊列頭元素，而尾指針 始終指向始終指向 隊列尾元素的下一位置！隊列尾元素的下一位置！ 空隊列：空隊列：rear = front = 0 入隊：入隊：rea

59、r =rear + 1 出隊：出隊：front = front + 1 隊列空：隊列空：front = rear 3.4.2 隊列的順序存儲結構特點特點:簡單簡單,方便方便,但是易產生但是易產生假假 溢出溢出.只是稱為指針，實現(xiàn)時不一定用指針變量2.隊列的簡單操作的實現(xiàn)隊列的簡單操作的實現(xiàn)(1）初始化）初始化 Q .front = Q.rear =0 ;(2）入隊）入隊Q .baseQ .reare ; Q .rear + + ;(3）出隊）出隊Q .front + + ;(4）判空）判空Q .front = = Q .rear ;(5）求隊長）求隊長Q .rear-Q .front思考：順序

60、隊列存在的問題及解決方案思考：順序隊列存在的問題及解決方案可以看出：當入隊一個元素時，可能會出現(xiàn)假可以看出：當入隊一個元素時，可能會出現(xiàn)假溢出現(xiàn)象溢出現(xiàn)象.即：空間并沒有使用完，但不能入隊！即：空間并沒有使用完，但不能入隊！解決的辦法：解決的辦法：( 1 ）平移，一旦發(fā)生假溢出，把隊列）平移，一旦發(fā)生假溢出，把隊列中所有元素移到隊列開頭效率低中所有元素移到隊列開頭效率低( 2 ）使用動態(tài)數組，當產生假溢出或）使用動態(tài)數組，當產生假溢出或真溢出時，都重新分配一個更大的空真溢出時，都重新分配一個更大的空間（不可取）間（不可?。? 3 ）使用環(huán)數組，即將順序存儲的空）使用環(huán)數組，即將順序存儲的空間視為一個環(huán)空間。間視為一個環(huán)空間。3.4.3 循環(huán)隊列存儲結構及操作實現(xiàn)循環(huán)隊列存儲結構及操作實現(xiàn) 方式：將順序隊列臆造為一個環(huán)狀的空間，如方式：將順序隊列臆造為一個環(huán)狀的空間，如圖所示，稱之為循環(huán)隊列圖所示，稱之為循環(huán)隊列.指針和隊列元素之間指針和隊列元素之間的關系不變的關系不變這種循環(huán)的圈只是一這種循環(huán)的圈只是一種邏輯上的圈種邏輯上的圈,在物理在物