第3章堆棧與隊列

1、第三章堆棧與隊列n隊列的應(yīng)用隊列的應(yīng)用3.1 堆棧堆棧一、堆棧的基本概念一、堆棧的基本概念n定義定義棧：用于局部變量、函數(shù)的形參等的空間棧：用于局部變量、函數(shù)的形參等的空間分配。分配。堆：由程序員申請，并對之進行釋放。堆：由程序員申請，并對之進行釋放。例如：例如：mallocmalloc（）；（）；freefree（）；（）；3.1 堆棧堆棧一、堆棧的基本概念一、堆棧的基本概念n定義定義 棧是限定只能在表的一端進行插入和刪棧是限定只能在表的一端進行插入和刪除的線性表。在表中允許插入和刪除的除的線性表。在表中允許插入和刪除的一端叫做一端叫做棧頂棧頂(top)(top)；表的另一端則叫做；表的另一

2、端則叫做棧底棧底(bottom)(bottom)。 棧又稱后進先出棧又稱后進先出(Last In First Out,(Last In First Out,簡寫簡寫為為LIFO)LIFO)表表出?；虺鰲；蛲藯Ｍ藯Ｈ霔；蛉霔；蜻M棧進棧a0a1an-2an-1bottomtop相關(guān)術(shù)語相關(guān)術(shù)語棧滿：棧滿：棧內(nèi)元素個數(shù)為棧內(nèi)元素個數(shù)為MaxSize時。時。 top=MaxSize-1棧空：?？眨簵?nèi)無元素。棧內(nèi)無元素。 top=-1上溢：上溢：當(dāng)棧滿時，還要進棧。當(dāng)棧滿時，還要進棧。下溢：下溢：當(dāng)棧空時，還要出棧。當(dāng)?？諘r，還要出棧。例：例： 對于一個棧，給出輸入項對于一個棧，給出輸入項A、B、C，

3、如果輸入項序列，如果輸入項序列由由ABC組成，試給出所有可能的輸出序列。組成，試給出所有可能的輸出序列。1. A進進 A出出 B進進 B出出 C進進 C出出 ABC2. A進進 A出出 B進進 C進進 C出出 B出出 ACB3. A進進 B進進 B出出 A出出 C進進 C出出 BAC4. A進進 B進進 B出出 C進進 C出出 A出出 BCA5. A進進 B進進 C進進 C出出 B出出 A出出 CBA不可能產(chǎn)生輸出序列不可能產(chǎn)生輸出序列 CAB1、初始化、初始化2、進棧、進棧3、退棧、退棧4、取棧頂元素、取棧頂元素5、判棧是否非空、判棧是否非空二、堆棧的操作二、堆棧的操作三、棧的順序表示和實現(xiàn)

4、三、棧的順序表示和實現(xiàn)順序堆棧順序堆棧1. 順序棧的存儲結(jié)構(gòu)順序棧的存儲結(jié)構(gòu)出?；虺鰲；蛲藯Ｍ藯Ｈ霔；蛉霔；蜻M棧進棧bottomtopa0a1a3a4a5maxlen-1543210順序棧的定義順序棧的定義typedef int DataType;#define maxlen 64typedef struct DataType stackmaxlen; int top;seqstack;topstackmaxlenss-tops-stack0s-stack1s-stack2s-stackmaxlen-12. 順序堆棧的操作實現(xiàn)順序堆棧的操作實現(xiàn)toptopa1a2a3a4toptoptopma

5、xlen個a1進棧a2進棧a3進棧a4進棧a4出棧topn初始化voidinistack(seqstack*s)s-top=-1;n判棧空操作int empty(seqstack s) if(s.top=-1) return 1; else return 0;n入棧入棧int push(seqstack int push(seqstack * *s,DataType x)s,DataType x) if (s-top=maxlen-1)if (s-top=maxlen-1) printf(“nStack is full”);printf(“nStack is full”);return 0;r

6、eturn 0; s-top+;s-top+;s-stacks-top=x;s-stacks-top=x;return 1;return 1; 判棧滿？判棧滿？棧頂下棧頂下標(biāo)加標(biāo)加1 1入棧入棧n出棧出棧int pop(seqstack int pop(seqstack * *s,DataType s,DataType * *d)d) if(s-top=-1) if(s-top=-1) printf(n Stack is empty!); printf(n Stack is empty!); return 0; return 0; else else * *d= s-stacks-top; d

7、= s-stacks-top; (s-top)- -; (s-top)- -; return 0; return 0; 判?？?？判?？?？元素出元素出棧棧棧頂下標(biāo)減棧頂下標(biāo)減1n取棧頂元素取棧頂元素int gettop(seqstack *s,DataType *d) if(s-top=-1) printf(“nStack is empty!”); return 0; else *d=s-stacks-top; return 1; 堆棧算法練習(xí)堆棧算法練習(xí)順序棧的順序棧的C C語言描述：語言描述：typedef int elemtype;#define maxsize 10elemtype st

8、ackmaxsize; int top;寫出堆棧的入棧和出棧算法寫出堆棧的入棧和出棧算法兩個堆棧共享空間目的：兩個堆棧共享空間目的：節(jié)省空間節(jié)省空間堆棧共用問題堆棧共用問題兩個堆棧共享空間的運算：初始化兩個堆棧共享空間的運算：初始化 進棧進棧 出棧出棧a0aiajam0maxsize-1LeftTopRightTop 數(shù)據(jù)結(jié)構(gòu)定義：數(shù)據(jù)結(jié)構(gòu)定義：typedef struct DataType stackmaxlen; int LeftTop; int RightTop; dqstack;初始化算法初始化算法void InitiDqstack(dqstack*s); s-LeftTop=-1;

9、s-RightTop=maxlen; int PushDqstack(dqstack*s,char WhichStack,DataType x) if (s-LeftTop= s-RightTop-1) printf(“棧滿棧滿”); return 0; if (WhichStack!=L& WhichStack !=R) printf(“出錯出錯”); return 0; if (WhichStack=L) s-stack+s-LeftTop=x; else s-stack-s-RightTop=x; return 1; 進棧算法進棧算法判斷是否棧判斷是否棧滿滿判斷輸判斷輸入是否入是

10、否錯錯X X入左棧入左棧X X入右棧入右棧共用堆棧的出共用堆棧的出棧算法棧算法:自編。自編。共用堆棧的算法練習(xí)共用堆棧的算法練習(xí):已知：已知：一個雙向堆棧一個雙向堆棧stackMstackM(M(M自己定義自己定義) )，編寫一個從鍵盤輸入數(shù)據(jù)，若輸入的是奇數(shù)，編寫一個從鍵盤輸入數(shù)據(jù)，若輸入的是奇數(shù)，則存入左棧；若輸入的是偶數(shù)，則存入右棧，則存入左棧；若輸入的是偶數(shù)，則存入右棧，直到棧滿為止的算法。直到棧滿為止的算法。 12EFhead130A12EFa31475130Aa210CB1475a110CB三、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)三、棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)棧頂棧頂鏈棧的結(jié)點定義鏈棧的結(jié)點定義typedef

11、int DataType;typedef struct snode DataType data; struct snode *next; LSNode; int PushStack(LSNode *head, DataType x) LSNode *p; if (p (LSNode*) malloc(sizeof(LSNode)=NULL) printf(“n失敗失敗”)； return 0； p-datax; p-nexthead-next; head-next=p; return 1; 鏈棧的進棧算法鏈棧的進棧算法產(chǎn)生一個產(chǎn)生一個新結(jié)點新結(jié)點進棧進棧headpxint PopStack(L

12、SNode *head,DataType *d) LSNode *p; p=head-next; if (p=NULL) printf(“under flown”); return 0; *dp-data; head-next p-next; free(p); return 1; 鏈棧的出棧算法鏈棧的出棧算法判?？张袟？粘鰲eadp*d總結(jié)：總結(jié)：概念：概念：堆棧，棧頂，棧底，棧滿，?？?，上溢，堆棧，棧頂，棧底，棧滿，?？?，上溢， 下溢，下溢， 順序棧，鏈棧。順序棧，鏈棧。算法：算法：初始化，入棧，出棧，取棧頂元素。初始化，入棧，出棧，取棧頂元素。 （順序棧，鏈棧）（順序棧，鏈棧） 3.3

13、3.3 隊列隊列一、隊列的定義及其操作一、隊列的定義及其操作n定義定義 隊列是一種特殊的線性表。在隊列中，僅隊列是一種特殊的線性表。在隊列中，僅允許一端進行插入，在另一端進行刪除。允許一端進行插入，在另一端進行刪除。 允許插入的一端叫做隊尾允許插入的一端叫做隊尾(rear)(rear)；允許刪除；允許刪除的另一端叫做隊頭的另一端叫做隊頭(front)(front)。 隊列又稱先進先出隊列又稱先進先出(First in First Out,(First in First Out,簡寫簡寫為為FIFO)FIFO)表。表。隊列的基本操作隊列的基本操作1、置空隊列、置空隊列2、判定隊列是否為空、判定隊

14、列是否為空3、取隊列頭元素、取隊列頭元素4、將新元素插入隊尾、將新元素插入隊尾5、隊列頭元素出隊、隊列頭元素出隊 二、隊列的順序存儲結(jié)構(gòu)二、隊列的順序存儲結(jié)構(gòu)frontfrontqueuemaxlenqueuemaxlenrearrearsqsqsq-rearsq-rearsq-frontsq-frontsq-queue0sq-queue0sq-queue1sq-queue1sq-queue2sq-queue2sq-queuemaxlen-1sq-queuemaxlen-1借助借助C語言的算法描述使用的數(shù)據(jù)類型示意圖語言的算法描述使用的數(shù)據(jù)類型示意圖順序隊列的定義順序隊列的定義#define

15、maxlen 100typedef int DataType;typedef struct DataType queuemaxlen; int front,rear; sequeue;指示隊頭元素的前一個位置指示隊頭元素的前一個位置指示隊尾元素的實際位置指示隊尾元素的實際位置frontrear空隊空隊a a入隊入隊b b入隊入隊 順序隊列入隊過程順序隊列入隊過程cdcd入隊入隊4 3 2 1 04 3 2 1 0a4 3 2 1 0ba4 3 2 1 0rearfrontfrontrearfrontrearabdc注意：入隊時，注意：入隊時，frontfront不變，不變，rearrear變變

16、gfedcbafrontrear隊滿隊滿gfedcbfrontreara a出隊出隊gfedfrontrearbcbc出隊出隊frontreardefgdefg出隊出隊 隊列出隊過程隊列出隊過程注意：出隊時，注意：出隊時，frontfront變，變，rearrear不變不變隊空隊空n 進隊時隊尾指針先進一進隊時隊尾指針先進一 rear = rear + 1， 再將新元素按再將新元素按 rear 指示位置加入。指示位置加入。n 出隊時隊頭指針先進一出隊時隊頭指針先進一 front = front + 1， 再將下標(biāo)為再將下標(biāo)為 front 的元素取出。的元素取出。n 隊滿時隊滿時( (rear

17、=maxsize-1 ) )再進隊將溢出出錯；再進隊將溢出出錯；n 隊空時隊空時( (rear = front ) )再出隊將溢出出錯。再出隊將溢出出錯。n front總是指向隊列中第一個元素的前一個位置?？偸侵赶蜿犃兄械谝粋€元素的前一個位置。n rear總是指向隊列中最后元素總是指向隊列中最后元素的位置。的位置。順序隊列的假溢出順序隊列的假溢出rearrearrearreara0a1a2a3rearrearrearrearrearrearmaxlenmaxlen個個frontfrontfrontfrontrearreara4rearreara5frontfronta6rearrear假溢出假

18、溢出1. 基本原理：基本原理： a.當(dāng)當(dāng)rear和和front達到達到maxlen-1后，在前后，在前進一個位置就自動到進一個位置就自動到0。 b.如何實現(xiàn)：如何實現(xiàn)： 用求模運算，用求模運算，rear=(rear+1)%maxlen循環(huán)隊列循環(huán)隊列frontJ6J7J8J1J2J3J4J5rearrearfront隊列滿隊列滿隊列空隊列空2. 隊空和隊滿的判斷：隊空和隊滿的判斷：循環(huán)隊列循環(huán)隊列n循環(huán)隊列的初始化循環(huán)隊列的初始化void iniqueue(sequeue void iniqueue(sequeue * *sq)sq) sq-front=0; sq-front=0; sq-re

19、ar=0; sq-rear=0; n入隊入隊int addqueue(sequeue int addqueue(sequeue * *sq,DataType x)sq,DataType x) if (sq-front=(sq-rear+1)%maxlen)if (sq-front=(sq-rear+1)%maxlen) printf(“nQueue is full”);printf(“nQueue is full”);return 0;return 0; sq-rear=(sq-rear+1)%maxlen;sq-rear=(sq-rear+1)%maxlen;sq-queuesq-rear=

20、x;sq-queuesq-rear=x;return 1;return 1; n出隊出隊int delqueue(sequeue int delqueue(sequeue * *sq, DataType sq, DataType * *d)d) if(sq-front=sq-rear)if(sq-front=sq-rear) printf(n Queue is empty!);printf(n Queue is empty!);return 0;return 0; sq-front=(sq-front+1)%maxlen;sq-front=(sq-front+1)%maxlen;* *d=sq

21、-queuesq-front;d=sq-queuesq-front;return 1;return 1; 三、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)三、隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu) 隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)12EFfront130A12EFa11475130Aa210CB1475a310CB10CBrear鏈隊列的結(jié)構(gòu)體定義鏈隊列的結(jié)構(gòu)體定義typedef struct slnode DataType data; struct slnode *next; LQNode; typedef struct LQNode *front; LQNode *rear; LQueue;初始化初始化int InitiateSLQueue(LQueue *q) if(q-front=(LQNode*)malloc(sizeof(LQNode)=NULL) printf(“n申請空間失敗！申請空間失??！”); return 0; q-rear=q-front; q-front-next=NULL; ret