第3章 棧和隊列

1、第三章 棧和隊列 Stack and Queue,?§3.1 棧(Stack)§3.2 棧的應(yīng)用舉例§3.3 棧與遞歸的實現(xiàn)§3.4 隊列(Queue),第3章 棧和隊列,棧：是一種插入和刪除操作被限定在表尾的線性表。 記作:S=(a1,a2,…,an)棧底：線性表的第一個元素棧頂：線性表的最后一個元素?？眨壕€性表長度為0操作特點：先進后出（Firs

2、t In Last Out）?或后進先出（Last In First Out）,3.1.1棧的ADT定義,a1,a2,a3,a4,棧模型：,輸入序列,輸出序列,特點：后進先出LIFO(Last In First Out),思考：A, B, C, D依次進棧，以下出棧序列中，哪些是可能的？哪些是不可能的？,D,C,B,A,D,C,A,B,D,B,C,A,A,B,C,D,B,C,D,A,C,D,B,A,C,D,A,B,C,A,B,D,,,

3、,,棧的基本運算:,初始化空棧：InitStack(&S)銷毀棧：DestroyStack(&S)清空棧：ClearStack(&S)判?？?StackEmpty(S)求棧長：StackLength(S)讀棧頂：GetTop(S, &e)或 GetTop(S)進棧：Push(&S, e)出棧：Pop(&S, &e),一、順序存儲結(jié)構(gòu)---

4、-順序棧 二、鏈式存儲結(jié)構(gòu)----鏈棧,3.1.2 棧的表示與實現(xiàn),一、順序棧typedef struct {SElemType *base; //數(shù)組首地址SElemType *top; //棧頂指針int stacksize; //棧容量}SqStack；,3.1.2 棧的表示與實現(xiàn),a1,a2,a3,a4,Top指在棧頂元素的下一個位置,空棧：S.base == S.

5、top 棧長：S.top－S.base,棧滿：S.top – S.base >= S.stacksize,基本運算在順序棧上的實現(xiàn)讀棧頂：Status GetTop(SqStack S, SElemType &e){//若棧不空，則用e返回S的棧頂元素，并返OK，//否則返回ERRORif(S.top==S.base) return ERROR; //棧空e=*(S.top-1);

6、return OK;}//GetTop,3.1.2 棧的表示與實現(xiàn),基本運算在順序棧上的實現(xiàn)判棧空：Status StackEmpty(SqStack S){//若?？?，返回TRUE；否則返回FALSE。if(S.top==S.base) return TRUE； //?？誩lse return FALSE;}//StackEmpty,3.1.2 棧的表示與實現(xiàn),基本運算在順序棧上的實現(xiàn)進棧：S

7、tatus Push(SqStack &S, SElemType e){ //插入元素e為新的棧頂元素 if(S.top-S.base==S.stacksize) {//棧滿，追加空間 S.base=(SElemType*)realloc(S.base, (S.stacksize+STACKINCREMENT)*sizeof(SElemType));if(!S.base) exit(OV

8、ERFLOW); S.stacksize+=STACKINCREMENT; } *(S.top++)=e; return OK;}//Push,3.1.2 棧的表示與實現(xiàn),基本運算在順序棧上的實現(xiàn)出棧：status Pop(SqStack &S, SElemType &e){ //若棧不空，則刪除棧頂元素，用e返回其值，并返回OK；//否則返回ERROR if(S.

9、top==S.base) return ERROR; //棧空 e=*（--S.top）; return OK;}//Pop,3.1.2 棧的表示與實現(xiàn),鏈棧結(jié)點存儲結(jié)構(gòu)：typedef struct SNode{ ElemType data； struct SNode *next；}SNode ，LinkStack；,二、鏈棧----帶頭結(jié)點的單鏈表,3.1.2 棧的表示與實現(xiàn),

10、,,,進棧Push： p->next=S->next; S->next=p;,,,,,,,出棧Pop：p=S->next;S->next=p->next;free(p);判?？諚l件： S->next==NULL;,,,基本運算在鏈棧上的實現(xiàn)入棧：status Push(LinkStack &S, SElemType e){ //插入元素e為

11、新的棧頂元素 p=（LinkStack）malloc（sizeof（SNode））； if(!p) exit(OVERFLOW); p->data=e; p->next=S->next; S->next=p; //頭插棧頂元素 return OK;}//Pusp,3.1.2 棧的表示與實現(xiàn),基本運算在鏈棧上的實現(xiàn)出棧：status Pop(LinkStack &S

12、, SElemType &e){ //若棧不空，則刪除棧頂元素，用e返回其值，并返回OK；//否則返回ERROR if(S->next==NULL) return ERROR; //?？?p=s->next; e=p->data; S->next=p->next; free(p); //刪除棧頂元素 return OK;}//Pop,3.1.2 棧的

13、表示與實現(xiàn),三、多個棧共享存儲空間問題：多個同類型的棧，但多數(shù)時候某些棧不滿，而某些棧過剩，如何更合理利用存儲空間？解決：多個棧共享同一個靜態(tài)存儲空間。,3.1.2 棧的表示與實現(xiàn),1）兩個棧共享空間,注意：棧的大小可能大于n/2,3.1.2 棧的表示與實現(xiàn),2）多個棧共享空間,若某個棧，如S1空間滿，但S2有空間，則，從S2整體往右邊移動一個數(shù)據(jù)元素空間。,3.1.2 棧的表示與實現(xiàn),§3.1 棧(Sta

14、ck)§3.2 棧的應(yīng)用舉例§3.3 棧與遞歸的實現(xiàn)§3.4 隊列(Queue),第3章 棧和隊列,3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗3.2.3 迷宮問題3.2.3 表達式求值,§3.2 棧的應(yīng)用舉例,原理： N = ( N div d) × d ＋ N mod d 例： ( 1348 ) 10 ＝ ( 25

15、04 ) 8,借助一個棧來反轉(zhuǎn)計算結(jié)果的順序,3.2.1 數(shù)制轉(zhuǎn)換,void Convert（int N, int d）{//將十進制N轉(zhuǎn)換成d進制數(shù)輸出 InitStack（S）； do{ Push（S，N %d）； N = N /d; }while (N!=0); while(!StackEmpty(S)) {Pop(S, e); printf(e);}}//C

16、onvert,3.2.1 數(shù)制轉(zhuǎn)換,3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗3.2.3 迷宮問題3.2.4 表達式求值,§3.2 棧的應(yīng)用舉例,思路：,( …{…}…) …[…{…(…)...[…]…}…[…]…],,(,{,[,{,(,[,[,3.2.2 括號匹配的檢驗,不能正確匹配的情況：,1.右括號多于右括號，如： …（ …） …） …#2.左括號多于左括號，如：…（ …（

17、 …） …#3.‘）（’不匹配，如： …） …（ …#4.多種括號時，括號不配對，如…[…(…] …) …#,3.2.2 括號匹配的檢驗,算法（文字描述）：設(shè)只處理小括號的情況設(shè)輔助棧S，從左到右掃描輸入串：1）遇到‘（’，進棧。2）遇到‘）’，若棧非空，配對成功，出棧； 否則，出錯（‘）’比‘（’多）；3）遇到‘#’，若?？?，配對成功； 否則，出錯（‘（’比‘）’多）。4）遇到其他字符，則

18、越過不處理。,3.2.2 括號匹配的檢驗,3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗3.2.3 迷宮問題3.2.4 表達式求值,§3.2 棧的應(yīng)用舉例,1. 問題：尋找一條從迷宮入口到出口的路徑且該路徑為簡單路徑。2. 迷宮的描述——矩陣（1）下一個位置的探測,3.2.3 迷宮問題,* * @ @ * * * *,∧

19、 ∧ ∧ ∧ ∧ ∧ ∧ ∧,（2）矩陣,,擴展：墻壁用’’1”表示,,∧：可到達但尚未到達#：障礙*：路徑上的位置@：曾經(jīng)到達但此路不通的位置,3.2.3 迷宮問題,棧元素：,棧變化：,,,2,3,4,,,2,2,3.2.1 數(shù)制轉(zhuǎn)換3.2.2 括號匹配的檢驗3.2.3 迷宮問題3.2.4 表達式求解,§3.2 棧的應(yīng)用舉例,算術(shù)表達式：

20、(a+b)*(c–d)–d/e,a + b,左操作數(shù),右操作數(shù),,運算規(guī)則：先算乘除，后算加減； 先算括號里，后算括號外； 從左算到右。,3.2.5 表達式求值,中綴表達式求值：,(a + b) * (c – d) – e / f 由于要處理括號和算符優(yōu)先級，所以算法比較復(fù)雜，需要借助兩個棧： 操作數(shù)棧：OPND 運算符棧：OPTR,3.2.5

21、 表達式求值,... （ 5 + 2 * 3 - 8 / 2 ）...,,從左向右掃描表達式。當(dāng)掃描到 “*” 號時，我們并不能計算5＋2， 因為“＋”的優(yōu)先級比 “*” 低 ；繼續(xù)掃描到 “-” 時，才能計算2 * 3，因為 “*” 的優(yōu)先級比“-”高。,可以算2*3了,繼續(xù)算5+6,3.2.5 表達式求值,# ... a θ1 b θ2 c ... #,θ1,θ2,3.2.5 表達式求值,算法原理：

22、 # ... a β b θ c ... #1. 從左至右逐個讀取表達式的每一項θ2. 如果θ是右＃且OPTR的棧頂是左＃，結(jié)束。3. θ是操作數(shù)：Push (OPND，θ ) ；goto # ?;4. θ是運算符：β = GetTop (OPTR) ，比較β與θ 的優(yōu)先級：βθ: Pop (OPND, b); Pop (OPND, a) ; Pop

23、 (OPTR, β);Push (OPND，a β b) ; goto 4;,例如：3*（7-2）#步驟OPTR OPND 輸入字符 主要操作 # 3*(7-2)# PUSH(OPND,3)2 # 3 *(7-2)# PUSH

24、(OPTR,*)3 #* 3 (7-2)# PUSH(OPTR,()4 #*( 3 7-2)# PUSH(OPND,7)5 #*( 37 -2)# PUSH(OPTR,-)6

25、 #*(- 37 2)# PUSH(OPND,2)7 #*(- 372 )# PUSH(OPND,operat(7-2)) 8 #*( 35 )# POP(OPTR)9 #*

26、 35 # PUSH(OPND,operat(3*5)) 10 # 15 # RETURN(GetTop(OPND)),3.2.5 表達式求值,上機實驗：算術(shù)表達式求值要求：運算對象為整數(shù)或?qū)崝?shù) 運算符為+、-、*、/,§3.1 棧(Stack)&

27、#167;3.2 棧的應(yīng)用舉例§3.3 棧與遞歸的實現(xiàn)§3.4 隊列(Queue),第3章 棧和隊列,,3.3.1 多函數(shù)嵌套調(diào)用 多函數(shù)的嵌套調(diào)用具有棧的特征： 后調(diào) (最里層)的函數(shù)先返回。,§3.3 棧與遞歸的實現(xiàn),程序在運行時，通過一個運行棧來實現(xiàn)被嵌套調(diào)用的函數(shù)之間的鏈接和信息傳遞。 運行棧中每個棧元素保留的信息：

28、 程序運行的全過程都是在運行棧中進行的,當(dāng)前正在執(zhí)行的函數(shù)的現(xiàn)場在棧頂。,§3.3 棧與遞歸的實現(xiàn),執(zhí)行調(diào)用時，做以下操作：返回主調(diào)函數(shù)的地址進棧，同時在棧頂為被調(diào)函數(shù)的形參和局部變量分配空間；為被調(diào)函數(shù)準備數(shù)據(jù)：計算實在參數(shù)的值，并將其賦給棧頂對應(yīng)的形參；控制轉(zhuǎn)入被調(diào)函數(shù)入口的代碼。執(zhí)行返回時，做以下動作：從棧頂取出返回地址，出棧（同時回收了被調(diào)過程的形參和局部變量的空間）按返回地址返回,§3.3

29、 棧與遞歸的實現(xiàn),void main ( ){ int m1,m2,m3; ... First( m1,m2); F: ... return; },void First(int i, int j){ int f1, f2; ... Second( i, f1); S: ... return; },void Second(int r, int t){ int s1;

30、 ... return; },0, m1,m2,m3,,S, r,t, s1,F, i, j, f1, f2,,,,運行棧,§3.3 棧與遞歸的實現(xiàn),遞歸調(diào)用是直接的或間接地自己調(diào)用自己。我們不妨把它看成是調(diào)用自身代碼的復(fù)制件，因而其內(nèi)部實現(xiàn)機理與普通多函數(shù)嵌套調(diào)用大致相同。,§3.3 棧與遞歸的實

31、現(xiàn),,,,,,,,,,,,,P(3)①② 調(diào)P(2)③ printf(3)④ 調(diào)P(2),P(2)①② 調(diào)P(1)③ printf(2)④ 調(diào)P(1),P(1)①② 調(diào)P(0)③ printf(1)④ 調(diào)P(0),P(0)① return,P(0)① return,P(1)①② 調(diào)P(0)③ printf(1)④ 調(diào)P(0),P(0)① return,P(0)① return,P(2)①②

32、 調(diào)P(1)③ printf(2)④ 調(diào)P(1),,void P( int w ) { ① if (w==0) return; ② P(w-1); ③ printf( “%d”, w); ④ P(w-1); },輸出序列：,,1,2,1,3,1,2,1,,,,,,,,,,,,,,,舉例：一個遞歸函數(shù)的執(zhí)行過程,舉例：Fib函數(shù) 0

33、 n=0 Fib(n)= 1 n=1 Fib(n-1) + Fib(n-2) n≥2,,void main( ) { int result ; result = Fib (4) ; printf (“%d\n”, result) ; return ; },int Fib ( i

34、nt n ) { int f1, f2 ; ① if ( n<=1) return n ; ② f1=Fib (n-1) ; ③ f2=Fib (n-2) ; ④ return f1 + f2 ; },§3.3 棧與遞歸的實現(xiàn),Fib (3),Fib (4),Fib (2),Fib (2),Fib (1),Fib (1),Fib (0),Fib (1),Fib (0),＋

35、,＋,＋,＋,,,,,,1,,3,遞歸調(diào)用示意,§3.3 棧與遞歸的實現(xiàn),§3.1 棧(Stack)§3.2 棧的應(yīng)用舉例§3.3 棧與遞歸的實現(xiàn)§3.4 隊列(Queue),第3章 棧和隊列,3.4.1 隊列的ADT定義,隊列：是一種限定僅在表尾插入，在表頭刪除的線性表。記為：Q=（a1,a2,…,an）隊頭（front）：線性表的第一個元素隊尾（rear）：線性

36、表的最后一個元素隊空：線性表長度為0操作特點：先進先出（First In First Out）或后進后出（Last In Last Out）?,§3.4 隊列(Queue),,,a1,a2,a3,a4,隊列模型：,輸入序列,輸出序列,特點：?后進先出FIFO(First In First Out),隊列的基本運算:,初始化空隊列：InitQueue(&Q)銷毀隊列：DestroyQueue(&

37、Q)清空隊列：ClearQueue(&Q)判棧隊列:StackQueue(Q)求隊列長：QueueLength(Q)入隊：EnQueue(&Q, e)出隊：DeQueue(&Q, &e),§3.4 隊列(Queue),一、順序存儲結(jié)構(gòu)----循環(huán)隊列 二、鏈式存儲結(jié)構(gòu)----鏈隊列,3.4.2 隊列的表示與實現(xiàn),一、循環(huán)隊列問題：當(dāng)不斷入隊和出隊后，可

38、能出現(xiàn)假溢出的情況，即仍有空間，但無法再入隊且不宜再動態(tài)分配空間。如圖：,,,隊頭front,隊尾rear,解決方法：將順序隊列臆想成一個循環(huán)隊列,3.4.2 隊列的表示與實現(xiàn),空隊列,入隊,隊滿,出隊,一、循環(huán)隊列#define MAXQSIZE 100 typedef struct {QElemType *base; //數(shù)組首地址int front; //隊頭下標(biāo)i

39、nt rear; //隊尾下標(biāo)}SqQueue；front為隊頭元素的下標(biāo)Rear為隊尾元素的后一個單元的下標(biāo),3.4.2 隊列的表示與實現(xiàn),空隊列：Q.front等于Q.rear隊滿：法1：Q.rear 等于Q.front，并設(shè)一個全局變量區(qū)分隊滿還是空隊列 法2：設(shè)置數(shù)字計數(shù)器（經(jīng)常求長度時可用）法2：浪費一個元素空間，（Q.rear+1 ）%MAXQSIZE 等于Q.front 隊長：(Q.re

40、ar-Q.front+MAXQSIZE)%MAXQSIZE,3.4.2 隊列的表示與實現(xiàn),基本運算在循環(huán)隊列上的實現(xiàn)初始化隊列：Status InitQueue_Sq（SqQueue &Q）{ //初始化隊列Q Q.base = （ElemType*）malloc（MAXQSIZE*sizeof(ElemType)）； if（！Q.base） exit（OVERFLOW）; Q.f

41、ront = Q.rear =0; return OK;} // InitQueue_Sq,3.4.2 隊列的表示與實現(xiàn),基本運算在循環(huán)隊列上的實現(xiàn)入隊：Status EnQueue_Sq(SqQueue &Q , ElemType e){ //將數(shù)據(jù)元素e入循環(huán)隊列Q中 if((Q.rear+1)%MAXQSIZE = = Q.front) return ERROR;

42、 Q.base[Q.rear] = e; Q.rear = (Q.rear+1)%MAXQSIZE; return OK;}// EnQueue_Sq,3.4.2 隊列的表示與實現(xiàn),基本運算在循環(huán)隊列上的實現(xiàn)出隊：Status DnQueue_Sq(SqQueue &Q , ElemType &e){ //循環(huán)隊列Q出隊，出隊元素賦值給e中 if(Q.rear = = Q.

43、front) return ERROR;e = Q.base[Q.front];Q.front = (Q.front+1)%MAXQSIZE; return OK;}// DeQueue_Sq,3.4.2 隊列的表示與實現(xiàn),基本運算在循環(huán)隊列上的實現(xiàn)求隊列長度：int QueueLength_Sq(SqQueue Q){ //返回隊列Q的長度 return (Q.rear-Q.front+MAX

44、QSIZE)%MAXQSIZE;} //QueueLength_Sq,3.4.2 隊列的表示與實現(xiàn),二、鏈隊列typedef struct QNode{ElemType data； struct Qnode *next；}QNode，*QueuePtr；typdef struct{ QueuePtr front，rear；}LinkQueue；Q.front指向頭結(jié)點

45、Q.rear 指向最后一個結(jié)點隊空：Q.front 等于Q.rear,3.4.2 隊列的表示與實現(xiàn),3.4.2 隊列的表示與實現(xiàn),基本運算在鏈隊列上的實現(xiàn)入隊：Status EnQueue_L(SqQueue& Q,ElemType e){ //將數(shù)據(jù)元素e入鏈隊列Q中 p = (QueuePtr)malloc(sizeof(QNode)); if(!p) exit(OVERFLOW);

46、 p->data = e; p->next = NULL; Q.rear ->next = p; Q.rear = p; return OK;}// EnQueue_L,3.4.2 隊列的表示與實現(xiàn),出隊：Status DnQueue_L(SqQueue& Q ,ElemType &e){ //鏈隊列Q出隊，出隊元素賦值給e中 if（Q.front = = Q.re