第三章 堆棧和隊列

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

2、或退棧退棧入?；蛉霔；蜻M棧進棧a0a1an-2an-1basetopLast In First Out一般線性表一般線性表邏輯結構：邏輯結構：一對一一對一存儲結構：存儲結構：順序表、鏈表順序表、鏈表運算規(guī)則：運算規(guī)則：隨機存取隨機存取堆棧堆棧邏輯結構：邏輯結構：一對一一對一存儲結構：存儲結構：順序棧、鏈棧順序棧、鏈棧運算規(guī)則：運算規(guī)則：后進先出后進先出(LIFO)*堆棧與一般線性表的比較*例例 一個棧的輸入序列為一個棧的輸入序列為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；合計有合計有5 5種可能性。種可能性。* * 不可能產生的輸出序列：不可能產生的輸出序列：3123121、初始化、初始化2、

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

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

6、是存放結構體變量的數(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;判棧滿？判棧滿？棧頂下標棧頂下標加加1 1入入棧棧s-stack+s-top=x; 出棧出棧功

7、能：彈出順序堆棧s的棧頂數(shù)據(jù)元素值到參數(shù) d，出棧成功返回1，否則返回0判?？?？判?？?？元素出元素出棧棧棧頂下標減棧頂下標減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的當前棧頂數(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; 堆棧算法練習堆棧算法練習順序棧的順序棧的C C語言描述：語言描述：typedef int elemtype;#define maxlen 10typedef struct elemtype stackmaxlen; int top;SeqStack;寫出堆棧的入棧和出棧算法寫出堆棧的入棧和出棧算法兩個堆棧共享空間目的：兩個堆棧共享空間目的：節(jié)省空間節(jié)省空間堆棧共用問題堆棧共用問題兩個堆棧共享空間的運算：初始化兩個堆棧共享空間的運算：初始化 進棧進棧

9、 出棧出棧a0aiajam0maxlen-1LeftTopRightTop 數(shù)據(jù)結構定義：數(shù)據(jù)結構定義：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(“出錯出錯”); return 0; if (WhichStack=L) s-stack+s-LeftTop=x; else s-stack-s-RightTop=x; return 1; 進棧算法進棧算法判斷是否棧判斷是否棧滿滿判斷輸判斷輸入是否入是否錯錯X X入左棧入左棧X X入右棧入右棧共用堆棧的出共用堆棧的出棧算法棧算法:自編。自編。共用堆棧的算法練習共用堆棧的算法練習已知：已知：一個雙向堆棧一個雙向堆棧stackMstackM(M(M自己定義自己定義) )，編寫一個算法：要求從鍵

11、盤輸入數(shù)據(jù)，若輸編寫一個算法：要求從鍵盤輸入數(shù)據(jù)，若輸入的是奇數(shù)，則存入左棧；若輸入的是偶數(shù)，入的是奇數(shù)，則存入左棧；若輸入的是偶數(shù)，則存入右棧，直到棧滿為止。則存入右棧，直到棧滿為止。 12EFhead130A12EFa21475130Aa110CB1475a010CB四、棧的鏈式存儲結構四、棧的鏈式存儲結構棧頂棧頂鏈棧的結點定義鏈棧的結點定義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; 鏈棧的進棧算法鏈棧的進棧算法申請一個申請一個新結點新結點進棧進棧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：括號匹配問題括號匹配問題 設計思路：用棧暫存左括號設計思路：用棧暫存左括號2：數(shù)制轉換（十轉數(shù)制轉換（十轉N） 設計思路：用棧暫存低位值設計思路：用棧暫存低位值3：漢諾（漢諾（Hanoi）塔）塔 設計思路：用棧實現(xiàn)遞歸調用設計思路：用棧實現(xiàn)遞歸調用4：表達式求值表達式求值 設計思路：用棧暫存運算符設計思路：用棧暫存運算符堆棧

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

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

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

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

18、棧頂運算符，且棧頂運算符為棧頂運算符，且棧頂運算符為“（”，當前運算符為，當前運算符為“）”，則棧頂運算符退棧，繼續(xù)，則棧頂運算符退棧，繼續(xù)讀下一符號；讀下一符號；5 5、如當前、如當前運算符運算符等于等于棧頂運算符，且棧頂運算符為棧頂運算符，且棧頂運算符為“#”“#”，當前運算符也為，當前運算符也為“#”“#”，則棧頂運算符退棧，則棧頂運算符退棧，表示運算結束；表示運算結束；()#(#front=0; sq-front=0; sq-rear=0; sq-rear=0; 循環(huán)隊列的初始化循環(huán)隊列的初始化/*隊頭指針*/*隊尾指針*/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)隊列的入隊列

20、循環(huán)隊列的入隊列判斷是否隊滿判斷是否隊滿隊尾指針后移隊尾指針后移元素入隊元素入隊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)隊列的出隊列循環(huán)隊列的出隊列隊頭指針后移隊頭指針后移元素出隊元素出隊判斷是否隊空判斷是否隊空四、隊列的鏈式存儲結構四、隊列的鏈式存儲結構 隊列的鏈式存儲結構隊列的鏈式存儲結構12EFfront130A12EFa01475130Aa110CB1475a210CB10CBrear鏈隊列的結構體定義鏈隊列的結構體定義typedef struct slnode DataType data; struct slnode *next; LQNode; typedef struct LQNode

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

23、0A*p1475px1NULLx0NULL147512EFrear130Arear1475reara0fronta1 rearrear鏈隊列的入隊算法鏈隊列的入隊算法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申請空間失敗申請空間失敗!”); 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