第3章 棧和隊(duì)列

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

2、t In Last Out）?或后進(jìn)先出（Last In First Out）,3.1.1棧的ADT定義,a1,a2,a3,a4,棧模型：,輸入序列,輸出序列,特點(diǎn)：后進(jìn)先出LIFO(Last In First Out),思考：A, B, C, D依次進(jìn)棧，以下出棧序列中，哪些是可能的？哪些是不可能的？,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、,,棧的基本運(yùn)算:,初始化空棧：InitStack(&S)銷(xiāo)毀棧：DestroyStack(&S)清空棧：ClearStack(&S)判?？?StackEmpty(S)求棧長(zhǎng)：StackLength(S)讀棧頂：GetTop(S, &e)或 GetTop(S)進(jìn)棧：Push(&S, e)出棧：Pop(&S, &e),一、順序存儲(chǔ)結(jié)構(gòu)---

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

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

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

7、tatus Push(SqStack &S, SElemType e){ //插入元素e為新的棧頂元素 if(S.top-S.base==S.stacksize) {//棧滿(mǎn)，追加空間 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 棧的表示與實(shí)現(xiàn),基本運(yùn)算在順序棧上的實(shí)現(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 棧的表示與實(shí)現(xiàn),鏈棧結(jié)點(diǎn)存儲(chǔ)結(jié)構(gòu)：typedef struct SNode{ ElemType data； struct SNode *next；}SNode ，LinkStack；,二、鏈棧----帶頭結(jié)點(diǎn)的單鏈表,3.1.2 棧的表示與實(shí)現(xiàn),

10、,,,進(jìn)棧Push： p->next=S->next; S->next=p;,,,,,,,出棧Pop：p=S->next;S->next=p->next;free(p);判棧空條件： S->next==NULL;,,,基本運(yùn)算在鏈棧上的實(shí)現(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 棧的表示與實(shí)現(xiàn),基本運(yùn)算在鏈棧上的實(shí)現(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、表示與實(shí)現(xiàn),三、多個(gè)棧共享存儲(chǔ)空間問(wèn)題：多個(gè)同類(lèi)型的棧，但多數(shù)時(shí)候某些棧不滿(mǎn)，而某些棧過(guò)剩，如何更合理利用存儲(chǔ)空間？解決：多個(gè)棧共享同一個(gè)靜態(tài)存儲(chǔ)空間。,3.1.2 棧的表示與實(shí)現(xiàn),1）兩個(gè)棧共享空間,注意：棧的大小可能大于n/2,3.1.2 棧的表示與實(shí)現(xiàn),2）多個(gè)棧共享空間,若某個(gè)棧，如S1空間滿(mǎn)，但S2有空間，則，從S2整體往右邊移動(dòng)一個(gè)數(shù)據(jù)元素空間。,3.1.2 棧的表示與實(shí)現(xiàn),§3.1 棧(Sta

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

15、04 ) 8,借助一個(gè)棧來(lái)反轉(zhuǎn)計(jì)算結(jié)果的順序,3.2.1 數(shù)制轉(zhuǎn)換,void Convert（int N, int d）{//將十進(jìn)制N轉(zhuǎn)換成d進(jìn)制數(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 括號(hào)匹配的檢驗(yàn)3.2.3 迷宮問(wèn)題3.2.4 表達(dá)式求值,§3.2 棧的應(yīng)用舉例,思路：,( …{…}…) …[…{…(…)...[…]…}…[…]…],,(,{,[,{,(,[,[,3.2.2 括號(hào)匹配的檢驗(yàn),不能正確匹配的情況：,1.右括號(hào)多于右括號(hào)，如： …（ …） …） …#2.左括號(hào)多于左括號(hào)，如：…（ …（

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

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

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

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

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

22、 # ... a β b θ c ... #1. 從左至右逐個(gè)讀取表達(dá)式的每一項(xiàng)θ2. 如果θ是右＃且OPTR的棧頂是左＃，結(jié)束。3. θ是操作數(shù)：Push (OPND，θ ) ；goto # ?;4. θ是運(yùn)算符：β = GetTop (OPTR) ，比較β與θ 的優(yōu)先級(jí)：βθ: 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 表達(dá)式求值,上機(jī)實(shí)驗(yàn)：算術(shù)表達(dá)式求值要求：運(yùn)算對(duì)象為整數(shù)或?qū)崝?shù) 運(yùn)算符為+、-、*、/,§3.1 棧(Stack)&

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

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

29、 棧與遞歸的實(shí)現(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,,,,運(yùn)行棧,§3.3 棧與遞歸的實(shí)現(xiàn),遞歸調(diào)用是直接的或間接地自己調(diào)用自己。我們不妨把它看成是調(diào)用自身代碼的復(fù)制件，因而其內(nèi)部實(shí)現(xiàn)機(jī)理與普通多函數(shù)嵌套調(diào)用大致相同。,§3.3 棧與遞歸的實(shí)

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,,,,,,,,,,,,,,,舉例：一個(gè)遞歸函數(shù)的執(zhí)行過(guò)程,舉例：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 棧與遞歸的實(shí)現(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 棧與遞歸的實(shí)現(xiàn),§3.1 棧(Stack)§3.2 棧的應(yīng)用舉例§3.3 棧與遞歸的實(shí)現(xiàn)§3.4 隊(duì)列(Queue),第3章 棧和隊(duì)列,3.4.1 隊(duì)列的ADT定義,隊(duì)列：是一種限定僅在表尾插入，在表頭刪除的線性表。記為：Q=（a1,a2,…,an）隊(duì)頭（front）：線性表的第一個(gè)元素隊(duì)尾（rear）：線性

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

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

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

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

40、ar-Q.front+MAXQSIZE)%MAXQSIZE,3.4.2 隊(duì)列的表示與實(shí)現(xiàn),基本運(yùn)算在循環(huán)隊(duì)列上的實(shí)現(xiàn)初始化隊(duì)列：Status InitQueue_Sq（SqQueue &Q）{ //初始化隊(duì)列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 隊(duì)列的表示與實(shí)現(xiàn),基本運(yùn)算在循環(huán)隊(duì)列上的實(shí)現(xiàn)入隊(duì)：Status EnQueue_Sq(SqQueue &Q , ElemType e){ //將數(shù)據(jù)元素e入循環(huán)隊(duì)列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 隊(duì)列的表示與實(shí)現(xiàn),基本運(yùn)算在循環(huán)隊(duì)列上的實(shí)現(xiàn)出隊(duì)：Status DnQueue_Sq(SqQueue &Q , ElemType &e){ //循環(huán)隊(duì)列Q出隊(duì)，出隊(duì)元素賦值給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 隊(duì)列的表示與實(shí)現(xiàn),基本運(yùn)算在循環(huán)隊(duì)列上的實(shí)現(xiàn)求隊(duì)列長(zhǎng)度：int QueueLength_Sq(SqQueue Q){ //返回隊(duì)列Q的長(zhǎng)度 return (Q.rear-Q.front+MAX

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

45、Q.rear 指向最后一個(gè)結(jié)點(diǎn)隊(duì)空：Q.front 等于Q.rear,3.4.2 隊(duì)列的表示與實(shí)現(xiàn),3.4.2 隊(duì)列的表示與實(shí)現(xiàn),基本運(yùn)算在鏈隊(duì)列上的實(shí)現(xiàn)入隊(duì)：Status EnQueue_L(SqQueue& Q,ElemType e){ //將數(shù)據(jù)元素e入鏈隊(duì)列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 隊(duì)列的表示與實(shí)現(xiàn),出隊(duì)：Status DnQueue_L(SqQueue& Q ,ElemType &e){ //鏈隊(duì)列Q出隊(duì)，出隊(duì)元素賦值給e中 if（Q.front = = Q.re