第3章 棧和隊列

1、內(nèi)容回顧n線性表 n定義n表示/實現(xiàn)方式（2種）n操作（3個）n順序表和鏈表各自特點（優(yōu)缺點，2方面）n鏈表類型（3種）第三章第三章 棧和隊列棧和隊列n本章內(nèi)容本章內(nèi)容3.1 棧棧3.1.1 棧的定義及基本運算棧的定義及基本運算3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.3 棧的應(yīng)用棧的應(yīng)用3.2 隊列隊列3.2.1 隊列的定義及基本運算隊列的定義及基本運算3.2.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)3.2.3 隊列的應(yīng)用隊列的應(yīng)用3.1.1 棧的定義及基本運算棧的定義及基本運算n棧棧(Stack)的定義的定義 棧棧(Stack)是限制在表的一端是限制在表的一端進行插入和刪

2、除運算的線性表，進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為通常稱插入、刪除的這一端為棧頂棧頂(top),另一端為棧底另一端為棧底(bottom)。當(dāng)表中沒有元素。當(dāng)表中沒有元素時稱為空棧。時稱為空棧。anan-1 .a2a1棧底棧底棧頂棧頂入棧入棧出棧出棧棧的特點棧的特點棧的修改是按后進先出的原棧的修改是按后進先出的原則進行的。因此，棧稱為后進先則進行的。因此，棧稱為后進先出表（出表（LIFO）。）。3.1.1 棧的定義及基本運算棧的定義及基本運算n棧的運算演示棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出四個元素依次進入一個棧，再依次出棧，得到一個輸出序列棧，得

3、到一個輸出序列DCBA。DCBAABCDDCBA 3.1.1 棧的定義及基本運算棧的定義及基本運算n棧的運算演示棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出四個元素依次進入一個棧，再依次出棧，得到一個輸出序列棧，得到一個輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得到出棧序列CBDAE？ABCDE操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧入棧A A 元素元素B入棧入棧B B 元素元素C入棧入棧C C3.1.1 棧的定義及基本運算棧的定義及基本運算n棧的運算演示棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出

4、四個元素依次進入一個棧，再依次出棧，得到一個輸出序列棧，得到一個輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得到出棧序列CBDAE？ DE操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧入棧A 元素元素B入棧入棧B 元素元素C入棧入棧 元素元素C出棧出棧CC 元素元素B出棧出棧B3.1.1 棧的定義及基本運算棧的定義及基本運算n棧的運算演示棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出四個元素依次進入一個棧，再依次出棧，得到一個輸出序列棧，得到一個輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得

5、到出棧序列CBDAE？ DE操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧入棧A 元素元素B入棧入棧 元素元素C入棧入棧 元素元素C出棧出棧C 元素元素B出棧出棧B 元素元素D入棧入棧D D 元素元素D出棧出棧D 元素元素A出棧出棧A3.1.1 棧的定義及基本運算棧的定義及基本運算n棧的運算演示棧的運算演示(1)A、B、C、D四個元素依次進入一個棧，再依次出四個元素依次進入一個棧，再依次出棧，得到一個輸出序列棧，得到一個輸出序列DCBA。(2)能否由入棧序列能否由入棧序列A、B、C、D、E得到出棧序列得到出棧序列CBDAE？ E操作序列：操作序列：出棧序列：出棧序列： 元素元素A入棧

6、入棧 元素元素B入棧入棧 元素元素C入棧入棧 元素元素C出棧出棧C 元素元素B出棧出棧B 元素元素D入棧入棧 元素元素D出棧出棧D 元素元素A出棧出棧A 元素元素E入棧入棧EE 元素元素E出棧出棧En棧的基本運算棧的基本運算InitStack(&S): InitStack(&S): 初始化棧初始化棧S SStackEmpty(): StackEmpty(): 判斷棧是否為空判斷棧是否為空Push(e): Push(e): 將元素將元素e e放入棧頂放入棧頂Pop(e): Pop(e): 移走棧頂?shù)脑兀瑫r由移走棧頂?shù)脑?，同時由e e帶回該元帶回該元素的值素的值Gettop(

7、): Gettop(): 獲取棧頂?shù)脑?，但不從棧中移走獲取棧頂?shù)脑兀粡臈Ｖ幸谱?.1.1 棧的定義及基本運算棧的定義及基本運算3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)anan-1 .a2a1棧棧basetop3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)n順序棧的類型定義順序棧的類型定義/ -棧的順序存儲表示棧的順序存儲表示-# define STACK_INIT_SIZE 100;# define STACKINCREMENT 10;typedef struct ElemType *base; /棧底指針，棧構(gòu)造前和銷毀后為空

8、棧底指針，棧構(gòu)造前和銷毀后為空 ElemType *top; /棧頂指針，指向棧頂元素的下一位置棧頂指針，指向棧頂元素的下一位置 int stacksize; /當(dāng)前分配的棧的存儲空間數(shù)當(dāng)前分配的棧的存儲空間數(shù)SqStack; 2.2 線性表的順序表示和實現(xiàn)線性表的順序表示和實現(xiàn)(對應(yīng)對應(yīng))n順序表存儲的語言實現(xiàn)順序表存儲的語言實現(xiàn)由于由于C C語言中的一維數(shù)組也是采用順序存儲表語言中的一維數(shù)組也是采用順序存儲表示，故可以用數(shù)組類型來描述順序表。下面我們用示，故可以用數(shù)組類型來描述順序表。下面我們用結(jié)構(gòu)類型來定義順序表類型。結(jié)構(gòu)類型來定義順序表類型。/-/-動態(tài)分配動態(tài)分配-#defineLI

9、ST_INIT_SIZE100 /空間初始分配量空間初始分配量#defineLISTINCREMENT10 /空間分配增量空間分配增量typedefstruct ElemType*elem;/存儲空間基址存儲空間基址intlength;/當(dāng)前長度當(dāng)前長度intlistsize;/當(dāng)前分配的存儲容量當(dāng)前分配的存儲容量 SqList；3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)(2)判斷?？张袛鄺？読nt StackEmpty(SqStack *S) return(S.base=S.top);(3)判斷棧滿判斷棧滿int StackFull(Sq

10、Stack *S) return(S.top-S.base=S.stacksize);3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)Status Push(SqStack &S, ElemType e)/插入元素插入元素e為新的棧頂元素為新的棧頂元素if (S.top S.base = S.stacksize) return ERROR; /棧滿棧滿*S.top = e;S.top+;return OK;/Push3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)n鏈棧鏈棧anan-1 .a

11、2a1棧棧棧底棧底棧頂棧頂S棧的鏈式存儲棧的鏈式存儲an an-1 a1a2 思考思考 鏈棧是否需要另外設(shè)置頭指針？鏈棧是否需要另外設(shè)置頭指針？ 建立鏈棧適合用哪種插入法？建立鏈棧適合用哪種插入法？ 鏈棧的基本操作的實現(xiàn)。鏈棧的基本操作的實現(xiàn)。 鏈棧的基本操作鏈棧的基本操作 置空棧置空棧void InitStack(SqStack *p) ptop=NULL; 判斷?？张袛鄺？読nt StackEmpty(linkstack *p) return ptop=NULL;3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧

12、的存儲結(jié)構(gòu)和實現(xiàn)3.1.2 棧的存儲結(jié)構(gòu)和實現(xiàn)棧的存儲結(jié)構(gòu)和實現(xiàn)被除數(shù)被除數(shù)除數(shù)除數(shù)商商余數(shù)余數(shù)432211212101102505221221012010 輸出輸出void conversion( ) InitStack(S); /構(gòu)造空棧構(gòu)造空棧scanf (“%d”,&n);while(n)Push(S,n%2);n=n/2; while(! StackEmpty(S)Pop(S,e);printf(“%d”,e); n括號匹配括號匹配設(shè)一個表達式中可以包含三種括號：設(shè)一個表達式中可以包含三種括號：“(”和和“)”、“”和和“”、“”和和“”，并且這三種括號可以按照任意，并且這三

13、種括號可以按照任意的次序的次序嵌套嵌套使用，考查表達式中的括號是否匹配。例如：使用，考查表達式中的括號是否匹配。例如： .(.).).n例：例：a=b+(c-d)*(e-f);while (m(a8+t) m=m+1; t=t-1;n實現(xiàn)方法利用棧進行表達式中的括號匹配實現(xiàn)方法利用棧進行表達式中的括號匹配自左至右掃描表達式，若遇左括號，則將左括號入自左至右掃描表達式，若遇左括號，則將左括號入棧，若遇右括號，則將其與棧頂?shù)淖罄ㄌ栠M行匹配，若棧，若遇右括號，則將其與棧頂?shù)淖罄ㄌ栠M行匹配，若配對，則棧頂?shù)淖罄ㄌ柍鰲?，否則出現(xiàn)括號不匹配錯誤。配對，則棧頂?shù)淖罄ㄌ柍鰲?，否則出現(xiàn)括號不匹配錯誤。思考：匹配

14、的充要條件？思考：匹配的充要條件？n迷宮問題迷宮問題尋找一條從入口到出口的通路。尋找一條從入口到出口的通路。81 2 3 4 5 6 781234567入口入口出口出口前進方向：前進方向： 上上(北北)、下、下(南南)、左、左(西西)、右、右(東東)東東南南北北西西n 走步規(guī)則：走步規(guī)則：首先從向下開始，按首先從向下開始，按照逆時針方向搜索下一步照逆時針方向搜索下一步可能前進的位置可能前進的位置棧棧n迷宮問題迷宮問題81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,

15、1)(7,1)i棧棧n迷宮問題迷宮問題81 2 3 4 5 6 781234567(1,1)(1,1)i(2,1)(2,1)i(3,1)(3,1)i(4,1)(4,1)i(5,1)(5,1)i(6,1)(6,1)(7,1)(7,1)i (5,2)(5,2)i(5,3)(5,3)i(6,3)(6,3)i(6,4)(6,4)i(8,8)(8,8)iiiiiin迷宮問題迷宮問題n迷宮的表示迷宮的表示const int N=8;struct PosType int x, y;char mazeNN; /位置上的標(biāo)識，是否可通過位置上的標(biāo)識，是否可通過n迷宮初始化迷宮初始化用二層嵌套循環(huán)對迷宮賦值用二層

16、嵌套循環(huán)對迷宮賦值n迷宮求解迷宮求解(見教材算法見教材算法)n輸出棧中的路徑輸出棧中的路徑Status MazePath(maze, start, end) /若迷宮中存在一條從入口若迷宮中存在一條從入口start到出口到出口end的通道，則求出這樣的一條通路的通道，則求出這樣的一條通路 InitStack(S); curpos = start; curstep = 1; do if (pass(curpos) /當(dāng)前位置可以通過當(dāng)前位置可以通過 Mark(maze,curpos); /留下記號留下記號 e = (curstep,curpos,1); push(S,e); /加入路徑加入路徑

17、if (curpos=end) return true; /到達出口到達出口 curpos = NextPos(curpos,1) ;/下一個位置下一個位置 curstep+; else /當(dāng)前位置不能通過當(dāng)前位置不能通過 if (!StackEmpty(S) pop(S,e); /退回一步退回一步 while(e.di=4 & ! !StackEmpty(S) /當(dāng)前位置是死胡同當(dāng)前位置是死胡同 Markdead(maze,e.seat)；pop(S,e); /留下記號，沿來路返回留下記號，沿來路返回 if (e.di4) /當(dāng)前位置還有其他方向沒有探索，繼續(xù)試探當(dāng)前位置還有其他方向

18、沒有探索，繼續(xù)試探 e.di+; push(S,e); curpos =NextPos(e.seat, e.di); while (!StackEmpty(S); return false; 表達式求值表達式求值算符優(yōu)先法算符優(yōu)先法 4+23-10/5 先乘除先乘除,后加減后加減; 從左算到右從左算到右 先括號內(nèi)先括號內(nèi),后括號外后括號外 4+23-10/5=4+6-10/5=10-10/5=10-2=8 表達式由表達式由操作數(shù)操作數(shù)(operand)、運算符運算符(operator)和和界限符界限符(delimiter)組成的。組成的。 將運算符和界限符統(tǒng)稱為將運算符和界限符統(tǒng)稱為算符算符。

19、它們構(gòu)成的集合命名為。它們構(gòu)成的集合命名為OP 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) case : /退棧并將運算結(jié)果入棧退棧并將運算結(jié)果入棧 Pop(OPTR,theta); Pop(

20、OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch/while return GetTop(OPND);/EvaluateExpression3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)n棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)用棧結(jié)構(gòu)實現(xiàn)程序設(shè)計語言中函數(shù)的嵌套調(diào)用和遞歸用棧結(jié)構(gòu)實現(xiàn)程序設(shè)計語言中函數(shù)的嵌套調(diào)用和遞歸調(diào)用調(diào)用例：例： long f(int n) if (n1) return n*f(n-1); else return 1; void main( ) int n=4; printf(“%ld”,f(n); 棧與遞歸3

21、.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn)棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Base case: n = 1 X Z棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Base case: n = 1 X Z棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Recursion: n 1 前前n-1 個盤個盤: X Y棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Recursion: n 1 前前n-1 個盤個盤: X Y棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔

22、問題Recursion: n 1 最大盤最大盤: X Z棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Recursion: n 1 最大盤最大盤: X Z棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Recursion: n 1 前前n-1個盤個盤: Y Z棧與遞歸3.3 棧與遞歸的實現(xiàn)棧與遞歸的實現(xiàn) n階階Hanoi塔問題塔問題Recursion: n 1 前前n-1個盤個盤: Y Z棧與遞歸3.4.1 隊列的定義及基本運算隊列的定義及基本運算n隊列隊列(Queue)的定義的定義隊列是僅限定在隊列是僅限定在表尾進行插入表尾進行插入和和表

23、頭進行刪除操作表頭進行刪除操作的線性表。的線性表。n術(shù)語術(shù)語隊頭隊頭(front)隊列的表頭，即只允許刪除的一端。隊列的表頭，即只允許刪除的一端。隊尾隊尾(rear) 隊列的表尾隊列的表尾，即只允許插入的一端。即只允許插入的一端。入隊入隊(EnQueue) 向隊尾插入元素。向隊尾插入元素。出隊出隊(DeQueue) 從隊頭刪除元素。從隊頭刪除元素。隊列的特點隊列的特點隊列的修改是按隊列的修改是按先進先出先進先出的原則進行的。因此，隊的原則進行的。因此，隊列稱為先進先出表（列稱為先進先出表（FIFO）。）。a1 a2 ai an隊頭隊頭front隊尾隊尾rear出隊出隊入隊入隊3.4.1 隊列的

24、定義及基本運算隊列的定義及基本運算n隊列的基本運算隊列的基本運算InitQueue(&Q): 初始化隊列初始化隊列QQueueEmpty(): 判斷隊列是否為空判斷隊列是否為空EnQueue(e): 將元素將元素e放入隊尾放入隊尾DeQueue(e): 移走隊頭元素，由移走隊頭元素，由e帶回該元帶回該元素的值素的值GetFront(): 獲取隊頭元素的值，但不從隊列獲取隊頭元素的值，但不從隊列中移走該元素中移走該元素Length(): 計算并返回隊列中元素的個數(shù)計算并返回隊列中元素的個數(shù)3.4.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)n鏈隊列鏈隊列隊列的鏈式存儲結(jié)構(gòu)隊列的鏈式存儲結(jié)

25、構(gòu) 隊列的鏈式存儲隊列的鏈式存儲a1 a2 anai Q.frontQ.reara1 a2 ai an隊頭隊頭front隊尾隊尾rear出隊出隊入隊入隊3.4.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)n鏈隊列的鏈隊列的C語言實現(xiàn)語言實現(xiàn) /-單鏈隊列的存儲結(jié)構(gòu)單鏈隊列的存儲結(jié)構(gòu)-typedef struct QNode /鏈表結(jié)點類型鏈表結(jié)點類型 QElemType data; struct QNode *next;QNode,*QueuePtr; typedef struct /隊列類型隊列類型 QueuePtr front; /隊頭指針隊頭指針 QueuePtr rear; /隊尾指針

26、隊尾指針LinkQueue;data Q.frontQ.rearStatus InitQueue(LinkQueue &Q) /構(gòu)造一個空隊列構(gòu)造一個空隊列QQ.front= Q.rear = (QueuePtr)malloc(sizeof(QNode);if(!Q.front) exit(OVERFLOW);Q.front-next = NULL;return OK;(2) 入隊入隊Status EnQueue(LinkQueue &Q, QElemType e)/將元素將元素e插入到隊列插入到隊列Q中中p = (QueuePtr)malloc(sizeof(QNode);i

27、f (!p) exit(OVERFLOW);p-data = e;p-next=NULL;Q.rear-next = p; Q.rear = p;return OK;3.4.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)n鏈隊列基本操作的實現(xiàn)鏈隊列基本操作的實現(xiàn)(1) 初始化初始化 Q.frontQ.rearStatus DeQueue(LinkQueue &Q, QElemType &e)/若隊列不空，則隊頭元素出隊列，用若隊列不空，則隊頭元素出隊列，用e返回其值，返回返回其值，返回OK /否則返回否則返回ERROR if (Q.rear = Q.front) return E

28、RROR; 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 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)n鏈隊列基本操作的實現(xiàn)鏈隊列基本操作的實現(xiàn)(1) 初始化初始化 (2) 入隊列入隊列 (3) 出隊列出隊列 Q.frontQ.rear思考：思考：如果不設(shè)置頭結(jié)點，如果不設(shè)置頭結(jié)點，需要考慮那些特殊情需要考慮那些特殊情況？況？3.4.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)n循環(huán)隊列隊列的順序存儲結(jié)構(gòu)循環(huán)隊

29、列隊列的順序存儲結(jié)構(gòu)a1 a2 ai an隊頭隊頭front隊尾隊尾rear出隊出隊入隊入隊6F36an6F26ai . .6F02a26F00a1Q.frontQ.reara1a2a3Q.frontanQ.rear012nn+1m-1循環(huán)隊列循環(huán)隊列n循環(huán)隊列的循環(huán)隊列的C語言實現(xiàn)語言實現(xiàn)/-循環(huán)隊列的存儲結(jié)構(gòu)循環(huán)隊列的存儲結(jié)構(gòu)-#define MAXSIZE 100typedef struct QElemType *base; int front; int rear; SqQueue;3.4.2 隊列的存儲結(jié)構(gòu)和實現(xiàn)隊列的存儲結(jié)構(gòu)和實現(xiàn)n循環(huán)隊列基本操作的實現(xiàn)循環(huán)隊列基本操作的實現(xiàn)(1) 初始化初始化Status InitQueue(SqQueue &Q)Q.base=(QEl