第三章 堆棧和隊(duì)列

1、3.1 堆棧堆棧（Stack） 3.2 隊(duì)列隊(duì)列（Queue）1. 定義定義2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式1. 定義定義2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 存儲(chǔ)結(jié)構(gòu)存儲(chǔ)結(jié)構(gòu)4. 運(yùn)算規(guī)則運(yùn)算規(guī)則5. 實(shí)現(xiàn)方式實(shí)現(xiàn)方式本章內(nèi)容3.1 堆棧一、堆棧的基本概念一、堆棧的基本概念 定義定義 堆棧是限定只能在表的堆棧是限定只能在表的一端進(jìn)行插入和刪除的一端進(jìn)行插入和刪除的線性表。在表中允許插線性表。在表中允許插入和刪除的一端叫做入和刪除的一端叫做棧棧頂頂(top)(top)；表的另一端；表的另一端則叫做則叫做棧底棧底(base)(base)。 出?；虺鰲?/p>

2、或退棧退棧入?；蛉霔；蜻M(jìn)棧進(jìn)棧a0a1an-2an-1basetopLast In First Out一般線性表一般線性表邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：一對(duì)一一對(duì)一存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：順序表、鏈表順序表、鏈表運(yùn)算規(guī)則：運(yùn)算規(guī)則：隨機(jī)存取隨機(jī)存取堆棧堆棧邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：一對(duì)一一對(duì)一存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧順序棧、鏈棧運(yùn)算規(guī)則：運(yùn)算規(guī)則：后進(jìn)先出后進(jìn)先出(LIFO)*堆棧與一般線性表的比較*例例 一個(gè)棧的輸入序列為一個(gè)棧的輸入序列為123，若在入棧的過程中，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？允許出棧，則可能得到的出棧序列是什么？答：答： 可以通過窮舉所有可能性來求解：可以通過

3、窮舉所有可能性來求解： 1 1入入1 1出，出， 2 2入入2 2出，出，3 3入入3 3出，出， 即即123123； 1 1入入1 1出，出， 2 2、3 3入，入，3 3、2 2出，出， 即即132132； 1 1、2 2入，入，2 2出，出， 3 3入入3 3出，出，1 1出出 即即231231； 1 1、2 2入，入，2 2、1 1出，出，3 3入入3 3出，出， 即即213213； 1 1、2 2、3 3入，入，3 3、2 2、1 1出，出， 即即321321；合計(jì)有合計(jì)有5 5種可能性。種可能性。* * 不可能產(chǎn)生的輸出序列：不可能產(chǎn)生的輸出序列：3123121、初始化、初始化2、

4、進(jìn)棧、進(jìn)棧3、退棧、退棧4、取棧頂元素、取棧頂元素5、判棧是否非空、判棧是否非空二、堆棧的操作二、堆棧的操作三、棧的順序表示和實(shí)現(xiàn)三、棧的順序表示和實(shí)現(xiàn)順序堆棧順序堆棧1. 順序棧的存儲(chǔ)結(jié)構(gòu)順序棧的存儲(chǔ)結(jié)構(gòu)出?；虺鰲；蛲藯Ｍ藯Ｈ霔；蛉霔；蜻M(jìn)棧進(jìn)棧basetopa0a1a3a4a5maxlen-1543210順序棧的定義順序棧的定義typedef int DataType;#define maxlen 100 / /* *順序堆棧數(shù)組最大存儲(chǔ)單元個(gè)數(shù)順序堆棧數(shù)組最大存儲(chǔ)單元個(gè)數(shù)* */ /typedef struct / /* *順序棧定義順序棧定義* */ / DataType stackma

5、xlen;/ /* *順序堆棧存放數(shù)據(jù)元素的數(shù)組順序堆棧存放數(shù)據(jù)元素的數(shù)組* */ / int top; / /* *順序堆棧的當(dāng)前棧頂位置順序堆棧的當(dāng)前棧頂位置* */ / seqstack; / /* *結(jié)構(gòu)類型名結(jié)構(gòu)類型名* */ /2. 順序堆棧的操作實(shí)現(xiàn)順序堆棧的操作實(shí)現(xiàn)toptopa0a1a2toptopmaxlen個(gè)空棧a0進(jìn)棧a1進(jìn)棧a2進(jìn)棧a2出棧top 初始化參數(shù)：S是指向結(jié)構(gòu)變量的指針；功能：建一個(gè)空棧S；void inistack(seqstack *s) s-top=-1;/ /* *順序堆棧數(shù)組的當(dāng)前棧頂位置順序堆棧數(shù)組的當(dāng)前棧頂位置* */ / 判棧空操作參數(shù)：S

6、是存放結(jié)構(gòu)體變量的數(shù)組；功能：判斷S是否為空，為空返回1，否則返回0；int empty(seqstack s) if(s.top=-1) return 1; else return 0; 入棧入棧功能：將數(shù)據(jù)元素x壓入順序堆棧S，入棧 成功返回1，否則返回0int push(seqstack *s, DataType x) if (s-top=maxlen-1) printf(“nStack is full”); return 0; s-top+; s-stacks-top=x; return 1;判棧滿？判棧滿？棧頂下標(biāo)棧頂下標(biāo)加加1 1入入棧棧s-stack+s-top=x; 出棧出棧功

7、能：彈出順序堆棧s的棧頂數(shù)據(jù)元素值到參數(shù) d，出棧成功返回1，否則返回0判?？眨颗袟？?？元素出元素出棧棧棧頂下標(biāo)減棧頂下標(biāo)減1else *d= s-stacks-top; (s-top)- -; return 1; int pop(seqstack *s,DataType *d) if(s-top=-1) printf(n Stack is empty!); return 0; *d=s-stacks-top-; 取棧頂元素取棧頂元素功能：取順序堆棧s的當(dāng)前棧頂數(shù)據(jù)元素值到 參數(shù)d，成功返回1，否則返回0 int gettop(seqstack s,DataType *d) if(s.top=

8、-1) printf(“nStack is empty!”); return 0; else *d=s.stacks.top; return 1; 堆棧算法練習(xí)堆棧算法練習(xí)順序棧的順序棧的C C語言描述：語言描述：typedef int elemtype;#define maxlen 10typedef struct elemtype stackmaxlen; int top;SeqStack;寫出堆棧的入棧和出棧算法寫出堆棧的入棧和出棧算法兩個(gè)堆棧共享空間目的：兩個(gè)堆棧共享空間目的：節(jié)省空間節(jié)省空間堆棧共用問題堆棧共用問題兩個(gè)堆棧共享空間的運(yùn)算：初始化兩個(gè)堆棧共享空間的運(yùn)算：初始化 進(jìn)棧進(jìn)棧

9、 出棧出棧a0aiajam0maxlen-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; s-RightTop=maxlen; int PushDqstack(dqstack*s,char WhichStack,DataType x) if (s-LeftTop= s-RightTop-1) printf(“棧滿棧滿”); ret

10、urn 0; if (WhichStack!=L& WhichStack !=R) printf(“出錯(cuò)出錯(cuò)”); return 0; if (WhichStack=L) s-stack+s-LeftTop=x; else s-stack-s-RightTop=x; return 1; 進(jìn)棧算法進(jìn)棧算法判斷是否棧判斷是否棧滿滿判斷輸判斷輸入是否入是否錯(cuò)錯(cuò)X X入左棧入左棧X X入右棧入右棧共用堆棧的出共用堆棧的出棧算法棧算法:自編。自編。共用堆棧的算法練習(xí)共用堆棧的算法練習(xí)已知：已知：一個(gè)雙向堆棧一個(gè)雙向堆棧stackMstackM(M(M自己定義自己定義) )，編寫一個(gè)算法：要求從鍵

11、盤輸入數(shù)據(jù)，若輸編寫一個(gè)算法：要求從鍵盤輸入數(shù)據(jù)，若輸入的是奇數(shù)，則存入左棧；若輸入的是偶數(shù)，入的是奇數(shù)，則存入左棧；若輸入的是偶數(shù)，則存入右棧，直到棧滿為止。則存入右棧，直到棧滿為止。 12EFhead130A12EFa21475130Aa110CB1475a010CB四、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)四、棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)棧頂棧頂鏈棧的結(jié)點(diǎn)定義鏈棧的結(jié)點(diǎn)定義typedeftypedef intint DataTypeDataType; ;typedeftypedef structstruct snodesnode DataTypeDataType data; data; structstruct snod

12、esnode * *next;next; LSNodeLSNode; ; int PushStack(LSNode *head, DataType x) LSNode *p; if (p=(LSNode*) malloc(sizeof(LSNode)=NULL) printf(“n失敗失敗”)； return 0； p-data=x; p-next=head-next; head-next=p; return 1; 鏈棧的進(jìn)棧算法鏈棧的進(jìn)棧算法申請(qǐng)一個(gè)申請(qǐng)一個(gè)新結(jié)點(diǎn)新結(jié)點(diǎn)進(jìn)棧進(jìn)棧headpxint PopStack(LSNode *head,DataType *d) LSNode *p; p=

13、head-next; if (p=NULL) printf(“under flown”); return 0; *d=p-data; head-next=p-next; free(p); return 1; 鏈棧的出棧算法鏈棧的出棧算法判?？张袟？粘鰲３鰲eadp*d1：括號(hào)匹配問題括號(hào)匹配問題 設(shè)計(jì)思路：用棧暫存左括號(hào)設(shè)計(jì)思路：用棧暫存左括號(hào)2：數(shù)制轉(zhuǎn)換（十轉(zhuǎn)數(shù)制轉(zhuǎn)換（十轉(zhuǎn)N） 設(shè)計(jì)思路：用棧暫存低位值設(shè)計(jì)思路：用棧暫存低位值3：漢諾（漢諾（Hanoi）塔）塔 設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用設(shè)計(jì)思路：用棧實(shí)現(xiàn)遞歸調(diào)用4：表達(dá)式求值表達(dá)式求值 設(shè)計(jì)思路：用棧暫存運(yùn)算符設(shè)計(jì)思路：用棧暫存運(yùn)算符堆棧

14、的應(yīng)用數(shù)制轉(zhuǎn)換數(shù)制轉(zhuǎn)換N = (N div d)d + N mod d 例如：（例如：（1348)10 = (2504)8 ，其運(yùn)算過程如下：，其運(yùn)算過程如下：輸出順序輸出順序計(jì)算順序計(jì)算順序?qū)⒂鄶?shù)依次進(jìn)棧，再出棧 N N div 8 N mod 81348 168 4 168 21 0 21 2 5 2 0 2漢諾（漢諾（ Hanoi）塔）塔傳說在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫傳說在創(chuàng)世紀(jì)時(shí)，在一個(gè)叫BrahmaBrahma的寺廟里，有三個(gè)柱子，的寺廟里，有三個(gè)柱子，其中一柱上有其中一柱上有6464個(gè)盤子從小到大依次疊放，僧侶的工作是個(gè)盤子從小到大依次疊放，僧侶的工作是將這將這6464個(gè)盤子從一根柱子移

15、到另一個(gè)柱子上。當(dāng)工作做完個(gè)盤子從一根柱子移到另一個(gè)柱子上。當(dāng)工作做完之后，就標(biāo)志著世界末日到來。之后，就標(biāo)志著世界末日到來。 移動(dòng)時(shí)的規(guī)則：移動(dòng)時(shí)的規(guī)則： 每次只能移動(dòng)一個(gè)盤子；每次只能移動(dòng)一個(gè)盤子； 只能小盤子在大盤子上面；只能小盤子在大盤子上面； 可以使用任一柱子?？梢允褂萌我恢?。x y zx y znn 1分析：分析： 設(shè)三根柱子分別為設(shè)三根柱子分別為x x，y y，z z，盤子在，盤子在x x柱上，要移到柱上，要移到z z柱上。柱上。 1 1、當(dāng)、當(dāng)n=1n=1時(shí)，盤子直接從時(shí)，盤子直接從x x柱移到柱移到z z柱上；柱上； 2 2、當(dāng)、當(dāng)n1n1時(shí)，則時(shí)，則設(shè)法將前設(shè)法將前n n

16、1 1個(gè)盤子借助個(gè)盤子借助z z，從，從x x移移到到y(tǒng) y柱上，把盤子柱上，把盤子n n移到移到z z柱上；柱上； 把把n n1 1個(gè)盤子從個(gè)盤子從y y移到移到z z柱上。柱上。abc321 11213121Y YX XZ Z表達(dá)式計(jì)算表達(dá)式計(jì)算中綴表達(dá)式：中綴表達(dá)式：A + ( B A + ( B C / D) C / D) E E后綴表達(dá)式：后綴表達(dá)式：ABCD/ABCD/E E+ +后綴表達(dá)式特點(diǎn)后綴表達(dá)式特點(diǎn)1 1、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同、與相應(yīng)的中綴表達(dá)式中的操作數(shù)次序相同2 2、沒有括號(hào)、沒有括號(hào)編譯系統(tǒng)中表達(dá)式的計(jì)算分為兩個(gè)步驟：編譯系統(tǒng)中表達(dá)式的計(jì)算分為兩個(gè)步

17、驟： （1）把中綴表達(dá)式變換為相應(yīng)的后綴表達(dá)式；）把中綴表達(dá)式變換為相應(yīng)的后綴表達(dá)式； （2）根據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值。）根據(jù)后綴表達(dá)式計(jì)算表達(dá)式的值。中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的處理規(guī)則中綴表達(dá)式轉(zhuǎn)換為后綴表達(dá)式的處理規(guī)則1 1、如為、如為操作數(shù)操作數(shù)，直接輸出到隊(duì)列；，直接輸出到隊(duì)列；2 2、如當(dāng)前、如當(dāng)前運(yùn)算符運(yùn)算符高于高于棧頂運(yùn)算符，入棧；棧頂運(yùn)算符，入棧；3 3、如當(dāng)前、如當(dāng)前運(yùn)算符運(yùn)算符低于低于棧頂運(yùn)算符，棧頂運(yùn)算符退棧，并棧頂運(yùn)算符，棧頂運(yùn)算符退棧，并輸出到隊(duì)列，當(dāng)前運(yùn)算符再與棧頂運(yùn)算符比較；輸出到隊(duì)列，當(dāng)前運(yùn)算符再與棧頂運(yùn)算符比較；4 4、如當(dāng)前、如當(dāng)前運(yùn)算符運(yùn)算符等于等于

18、棧頂運(yùn)算符，且棧頂運(yùn)算符為棧頂運(yùn)算符，且棧頂運(yùn)算符為“（”，當(dāng)前運(yùn)算符為，當(dāng)前運(yùn)算符為“）”，則棧頂運(yùn)算符退棧，繼續(xù)，則棧頂運(yùn)算符退棧，繼續(xù)讀下一符號(hào)；讀下一符號(hào)；5 5、如當(dāng)前、如當(dāng)前運(yùn)算符運(yùn)算符等于等于棧頂運(yùn)算符，且棧頂運(yùn)算符為棧頂運(yùn)算符，且棧頂運(yùn)算符為“#”“#”，當(dāng)前運(yùn)算符也為，當(dāng)前運(yùn)算符也為“#”“#”，則棧頂運(yùn)算符退棧，則棧頂運(yùn)算符退棧，表示運(yùn)算結(jié)束；表示運(yùn)算結(jié)束；()#(#front=0; sq-front=0; sq-rear=0; sq-rear=0; 循環(huán)隊(duì)列的初始化循環(huán)隊(duì)列的初始化/*隊(duì)頭指針*/*隊(duì)尾指針*/intint addqueue(sequeueaddqueue

19、(sequeue * *sq,DataTypesq,DataType x) x) if (sq-front=(sq-rear+1)%maxlen) if (sq-front=(sq-rear+1)%maxlen) printf(“nQueueprintf(“nQueue is full”); is full”); return 0; return 0; sq- sq-queuesqqueuesq-rear=x;-rear=x; sq-rear=(sq-rear+1)%maxlen; sq-rear=(sq-rear+1)%maxlen; return 1; return 1; 循環(huán)隊(duì)列的入隊(duì)列

20、循環(huán)隊(duì)列的入隊(duì)列判斷是否隊(duì)滿判斷是否隊(duì)滿隊(duì)尾指針后移隊(duì)尾指針后移元素入隊(duì)元素入隊(duì)intint delqueue(sequeuedelqueue(sequeue * *sq, sq, DataTypeDataType * *d)d) if (sq-front=sq-rear) if (sq-front=sq-rear) printf(nprintf(n Queue is empty!); Queue is empty!); return 0; return 0; * *d=sq-d=sq-queuesqqueuesq-front;-front; sq-front=(sq-front+1)%max

21、len; sq-front=(sq-front+1)%maxlen; return 1; return 1; 循環(huán)隊(duì)列的出隊(duì)列循環(huán)隊(duì)列的出隊(duì)列隊(duì)頭指針后移隊(duì)頭指針后移元素出隊(duì)元素出隊(duì)判斷是否隊(duì)空判斷是否隊(duì)空四、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)四、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)12EFfront130A12EFa01475130Aa110CB1475a210CB10CBrear鏈隊(duì)列的結(jié)構(gòu)體定義鏈隊(duì)列的結(jié)構(gòu)體定義typedef struct slnode DataType data; struct slnode *next; LQNode; typedef struct LQNode

22、 *front; LQNode *rear; LQueue;結(jié)點(diǎn)的結(jié)結(jié)點(diǎn)的結(jié)構(gòu)體類型構(gòu)體類型front rear隊(duì)頭指針隊(duì)頭指針隊(duì)尾指針隊(duì)尾指針初始化初始化int InitiateSLQueue(LQueue *q) if(q-front=(LQNode*)malloc(sizeof(LQNode) =NULL) printf(“n申請(qǐng)空間失??！申請(qǐng)空間失??！”); return 0; q-rear=q-front; q-front-next=NULL; return 1; 12EFfrontNULL12EFrearn鏈隊(duì)列的入隊(duì)示意鏈隊(duì)列的入隊(duì)示意12EFfront*p130ApNULL13

23、0A*p1475px1NULLx0NULL147512EFrear130Arear1475reara0fronta1 rearrear鏈隊(duì)列的入隊(duì)算法鏈隊(duì)列的入隊(duì)算法pX intint addqaddq ( (LQueueLQueue * *q,DataTypeq,DataType x) x) LQNodeLQNode * *p;p; if if (p=(p=(LQNodeLQNode* * ) ) malloc(sizeof(LQNodemalloc(sizeof(LQNode)=NULL)=NULL) printfprintf (“n (“n申請(qǐng)空間失敗申請(qǐng)空間失敗!”); return 0;!”); return 0; p-data=x; p-data=x; p-next=NULL; p-next=NULL; q-rear-next=p; q-rear-next=p; q-rear=p; q-rear=p; return 1; return 1; y1475p12EFfronta1NULL1475a0130A1