1、棧 ( Stack )隊(duì)列 ( Queue )棧和隊(duì)列的應(yīng)用第三章 棧和隊(duì)列棧 ( Stack )第三章 棧和隊(duì)列操作原則 后進(jìn)先出 (LIFO)3.1 棧 ( Stack )topbottoma1anan-1進(jìn)棧a 1 a n出棧a n a 1只允許在一端插入和刪除的線性表 S= （a 1 a 2 a 3 a n-1 a n ）允許插入和刪除的一端稱為棧頂 (top)，另一端稱為棧底(bottom)topbottoma1anan-1x操作原則3.1 棧 ( Stack )topbottADT List 數(shù)據(jù)對(duì)象: D=ai|1i n, n 0, ai屬Elemtype類型 數(shù)據(jù)關(guān)系: R1=

2、| ai ,ai+1 D, i=1,2, ,n-1 基本運(yùn)算: InitStack(&S ); ClearStack(S); StackEmpty(S); StackLength(S): Push(&S,e); Pop(&S,&e) GetTop(S,&e); DispStack(S);抽象數(shù)據(jù)類型棧的定義ADT List抽象數(shù)據(jù)類型棧的定義typedef struct /順序棧定義 ElemType datamaxsize; /棧數(shù)組 int top; /棧頂指針 SqStack;順 序 棧top (?？? 0 1 2 3 4 5 6 7 8 9 maxsize-1datacab順 序 棧t

3、op (棧空) 0 1 2 top空棧topa 進(jìn)棧a topabcdef 進(jìn)棧溢出topb 進(jìn)棧abtopabcdee 進(jìn)棧topabdee 退棧ctop空棧topa 進(jìn)棧a topabcdtop空棧topabdd 退棧cc 退棧topabcb 退棧abtopaa 退棧toptop空棧topabdd 退棧cc 退棧topabcb 退棧 void InitStack (SqStack *&S) /置空棧 S=(SqStack *)malloc(sizeof(SqStack); S-top = -1; return; bool StackEmpty (SqStack *S) /判斷棧是否空？空則

4、返回1，否則返回0 if(S-top=-1) return false; else return true; void InitStack (SqStack *&S) bool push (SqStack *&S, ElemType e)/若棧滿返回0, 否則新元素 x 進(jìn)棧并返回1 if ( S-top=maxsize-1) return false; S-top+; S-dataS-top = e; /加入新元素 return true;bool pop (SqStack *&S, ElemType &e)/若棧空返回0, 否則棧頂元素讀到x并返回1 if ( S-top=-1 ) ret

5、urn false; e = S-dataS-top; S-top-; return true;bool push (SqStack *&S, ElemTy棧 1 top1 top2 棧2 0 MaxSize-1data雙棧共享一個(gè)?？臻g進(jìn)棧 退棧棧1top1+; datatop1=x;x=datatop1; top1-;棧2top2-; datatop2=x;x=datatop2; top2+;棧滿？棧空？數(shù)據(jù)類型typedef struct ElemType dataMaxSize; int top1,top2; DseqStack;基本運(yùn)算push(&S, i, x)pop(&S,i,&

6、x)stackempty(S, i)棧 1 top1 top2 鏈 式 棧注：每個(gè)結(jié)點(diǎn)的指針指向直接前驅(qū)結(jié)點(diǎn)結(jié)構(gòu)：data next 數(shù)據(jù)類型：typedef struct linknode ElemType data; struct linknode *next;LiStack;LiStack *s; /top確定鏈棧 sabc鏈 式 棧注：每個(gè)結(jié)點(diǎn)的指針指向直接前驅(qū)結(jié)點(diǎn)結(jié)構(gòu)：dat sabpxp-next=s-next生成新結(jié)點(diǎn)ps-next=p鏈?zhǔn)綏２僮鞯膶?shí)現(xiàn)void push (LiStack *&S, ElemType e ) LiStack *p; p = (LiStack * )

7、 malloc( sizeof (LiStack ) ); p-data = e; p-next = S-next; S-next=p; 進(jìn)棧 sabpxp-next=s-next生成新結(jié)p=s-nexts-next=p-next退棧sabcpbool StackEmpty (LiStack *S) if (S-next = NULL) return true ; return false;bool pop (LiStack *&S, ElemType *e ) if (S-next=NULL) ) return false; p = S-next; S-next=p-next; e = p-

8、data; free (p); return true; p=s-nexts-next=p-next退棧sabc3.2 棧的應(yīng)用例如：函數(shù)的嵌套調(diào)用main( ) f1( ) f2( ) f3( ) f1( ); f2( ); f3( ) ; r1: r2: r3:依次保存r1、r2、r3，而返回時(shí)依次取出r3、r2、r1返回調(diào)用函數(shù)，后進(jìn)先出，利用棧保存返回地址。注：為確保正確返回調(diào)用函數(shù)，則需要保存返回地址。r1r2r3r1r2r33.2 棧的應(yīng)用例如：函數(shù)的嵌套調(diào)用main( ) 1 1 1 1 1 1 1 1 11 11 11 1 1 11 1 11 11 1 1 1 1 1 1 1

9、10 1 1 1 0 1 01 0 0 0 0 1 10 1 0 1 0 1 10 1 0 1 1 1 01 0 1 0 1 0 10 0 1 0 0 0 11 1 0 0 1 1 0例如：迷宮問(wèn)題(x,y)(x +1,y) (x -1,y) (x-1,y-1)(x,y-1) (x+1,y-1) (x+1,y+1) (x,y+1) (x-1,y+1)( 1, 1 , 2)( 2, 2 , 1)( 2, 3, 1 )( 2, 4, 1 )( 2, 5, 3 )( 3, 5, ? )( 2, 5, 7 ) ( 1, 5, ?) ( 2, 4, 4 )( 3, 3, 3 )( 4, 3, 2 ) 1

10、 1 1 1 1 1 1 1 例如：表達(dá)式的計(jì)算中綴表達(dá)式: # A + ( B C / D ) * E #后綴表達(dá)式: # A B C D /- E* + #問(wèn)題：由于各運(yùn)算優(yōu)先級(jí)別不同，計(jì)算機(jī)很難實(shí)現(xiàn)。注：只有當(dāng)掃描到運(yùn)算符時(shí)，才可進(jìn)行運(yùn)算，因此，需要先保存已掃描的操作數(shù)。由于后保存的數(shù)先進(jìn)行運(yùn)算，滿足后進(jìn)先出的原則，所以利用棧來(lái)保存操作數(shù)及每次運(yùn)算的結(jié)果。 ABCD/: R1=C/D R1-: R2=B-R1 R2*: R3=R2*E+: R4=A+R3 R4E R3 例如：表達(dá)式的計(jì)算中綴表達(dá)式: # A + ( B C 允許刪除的一端叫做隊(duì)頭(front)，允許插入的一端叫做隊(duì)尾(r

11、ear)。frontreara1 a2 an-1 an 3.3 隊(duì)列 ( Queue )隊(duì)列是只允許在一端刪除，在另一端插入的線性表操作原則先進(jìn)先出(FIFO, First In First Out)x隊(duì)尾插入a1隊(duì)頭刪除允許刪除的一端叫做隊(duì)頭(front)，frontreara1ADT List 數(shù)據(jù)對(duì)象: D=ai|1i n, n 0, ai屬Elemtype類型 數(shù)據(jù)關(guān)系: R1=| ai ,ai+1 D, i=1,2, ,n-1 基本運(yùn)算: InitQueue(&Q); ClearQueue (&Q); QueueEmpty(Q); QueueLength(Q): EnQueue (&

12、Q,e); DeQueue (&Q,&e) GetFront(Q,&e);抽象數(shù)據(jù)類型隊(duì)列的定義ADT List抽象數(shù)據(jù)類型隊(duì)列的定義typedef int ElemType;typedef struct ElemType dataMaxSize; int front, rear,; SqQueue;隊(duì)列的順序存儲(chǔ)表示 順序隊(duì)列 0 2 3 4 5 6 7 8 9 MaxSize-1dataa b c drear（指向隊(duì)尾元素）front （指向隊(duì)頭之前）typedef int ElemType;隊(duì)列的順序存儲(chǔ)表示隊(duì)列的進(jìn)隊(duì)和出隊(duì) frontrear空隊(duì)列frontrearA進(jìn)隊(duì)Afrontr

13、earB進(jìn)隊(duì)A BfrontrearB退隊(duì)C DfrontrearC, D進(jìn)隊(duì)A B C DfrontrearA退隊(duì)B C D隊(duì)列的進(jìn)隊(duì)和出隊(duì) frontrear空隊(duì)列frontrea隊(duì)列的進(jìn)隊(duì)和出隊(duì)的操作解決辦法之一：將隊(duì)列元素存放數(shù)組首尾 相接，形成循環(huán)(環(huán)形)隊(duì)列。 進(jìn)隊(duì)： rear = rear + 1 datarear=x出隊(duì): front = front + 1 x= datafrontH進(jìn)隊(duì),溢出C D E F frontrear1 2 3 4 5 6 7GG進(jìn)隊(duì)C出隊(duì)？“假溢出”？滿？空Hrearrear隊(duì)列的進(jìn)隊(duì)和出隊(duì)的操作解決辦法之一：將隊(duì)列元素存放數(shù)組首尾進(jìn)循環(huán)隊(duì)列 (C

14、ircular Queue)frontrear6MaxSize-1012345DA B C .循環(huán)隊(duì)列 (Circular Queue)frontrear01234567frontrearfront01234567Arearfront01234567ABCrear隊(duì)列初值A(chǔ)進(jìn)隊(duì)B, C進(jìn)隊(duì)A退隊(duì)B退隊(duì)frontrear01234567BCrearfront01234567BCA001234567frontrearfront01234567Y進(jìn)隊(duì)rearfront67012345XWYZZ進(jìn)隊(duì)rear = rear+1( ) % MaxSize67012345BACBArearA出隊(duì)B出隊(duì)fro

15、nt = front+1( ) % MaxSizefront？空C出隊(duì)frontfrontCfront= =rearrearA B C D ？滿rearA B C進(jìn)隊(duì)D進(jìn)隊(duì)front= =rear？如何區(qū)別滿和空Y進(jìn)隊(duì)rearfront67012345XWYZZ進(jìn)隊(duì)rea67012345XWYZA B C 方法一：增加一個(gè)存儲(chǔ)單元n 用于存儲(chǔ)隊(duì)列的長(zhǎng)度 n=0 空 n=MaxSize 滿方法二：利用隊(duì)列中最后一個(gè) 存儲(chǔ)單元標(biāo)志滿空：front=rear滿:rearfrontfront = = rear +1( )%MaxSize67012345XWYZA B C 方法一：增加一個(gè)存儲(chǔ)單元voi

16、d Initqueue (SqQueue *&Q) Q=(SqQueue *)malloc(sizeof(SqQueue); Q-rear = Q-front = 0;bool QueueEmpty (SqQueue *Q ) if (Q-rear = Q-front) return true; else return false;循環(huán)隊(duì)列操作的實(shí)現(xiàn)void Initqueue (SqQueue *&Q) 循bool enQueue (SqQueue *&Q, elemtype e ) if (Q-front= =(Q-rear+1)% MaxSize ) return false; Q-re

17、ar = (Q-rear+1) % MaxSize; Q-dataQ-rear = e; return true;入 隊(duì) 列bool enQueue (SqQueue *&Q, elebool deQueue (SqQueue *Q; elemtype &e ) if (Q-front=Q-rear) return false; Q-front = (Q-front+1) % MaxSize; e = Q-dataQ-front; return true;出 隊(duì) 列bool deQueue (SqQueue *Q; elem隊(duì)列的鏈接表示 鏈?zhǔn)疥?duì)列frontrear入隊(duì)列：XPa1a2an生成

18、新結(jié)點(diǎn)p插入隊(duì)尾出隊(duì)列：P刪除結(jié)點(diǎn)p釋放結(jié)點(diǎn)p？front 用于出隊(duì)列 rear 用于入隊(duì)列隊(duì)列的鏈接表示 鏈?zhǔn)疥?duì)列frontrear入隊(duì)列：XP 鏈?zhǔn)疥?duì)列的定義typedef struct node ElemType data; /隊(duì)列結(jié)點(diǎn)數(shù)據(jù) struct node *next; /結(jié)點(diǎn)鏈指針 QNode;typedef struct QNode *rear, *front; LiQueue;a1a2anfront rearqlinkqueue *q; 鏈?zhǔn)疥?duì)列的定義a1void InitQueue ( LiQueue *&Q ) Q=(LiQueue *)malloc(sizeof(Li

19、Queue); Q-rear = Q-front = NULL;bool QueueEmpty ( LiQueue *Q ) if(Q-front = NULL) return true; else return falsebool GetFront ( LiQueue *Q, ElemType &e ) if (Q-front=NULL ) return false; e = Q-front-data; return true;鏈?zhǔn)疥?duì)列主要操作的實(shí)現(xiàn)void InitQueue ( LiQueue *&Q )int EnQueue ( LiQueue *&Q, ElemType e ) QN

20、ode *s = ( QNode * ) malloc( sizeof ( QNode ) ); s-data = s; s-next = NULL; if (Q-front = NULL ) /空,創(chuàng)建第一個(gè)結(jié)點(diǎn) Q-front = Q-rear = s; else Q-rear -next = s; Q-rear=s; int EnQueue ( LiQueue *&Q, Elebool DeQueue ( LiQueue *Q, elemtype &e) /刪去隊(duì)頭結(jié)點(diǎn)，并返回隊(duì)頭元素的值 if (Q-rear=NULL ) return false;/判隊(duì)空 QNode *t = Q-

21、front; e = t-data; /保存隊(duì)頭的值 Q-front = Q-front-link; /新隊(duì)頭 if (Q-front = NULL) Q-rear = NULL; free (t); return 1;bool DeQueue ( LiQueue *Q, ele1 1 1 1 1 1 1 1 1 11 11 11 1 1 11 11 11 1 1 1 1 1 1 1 1 10 1 1 1 0 1 1 11 0 1 0 1 0 1 00 1 0 0 1 1 1 10 1 1 1 0 0 1 11 0 0 1 1 0 0 00 1 1 0 0 1 1 0(x,y)(x +1,y) (x-1,y) (x-1,y-1)(x,y-1) (x+1,y-1) (x+1,y+1) (x,y+1) (x-1,y+1)例如：迷宮問(wèn)題 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20