第03章_棧和隊列A

1、第三章：棧和隊列第三章：棧和隊列13.1棧棧 (Stack) 3.2 隊列隊列 (Queue) 第三章：棧和隊列第三章：棧和隊列21. 基本概念基本概念2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 運算規(guī)則運算規(guī)則5. 實現(xiàn)方式實現(xiàn)方式1. 基本概念基本概念2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 運算規(guī)則運算規(guī)則5. 實現(xiàn)方式實現(xiàn)方式 定義定義: 限定只能在表的進行插入和刪除運算的線性表。 3與線性表相同，仍為一對一與線性表相同，仍為一對一( 1:1)關(guān)系。關(guān)系。用用或或存儲均可，但以順序棧更常見存儲均可，但以順序棧更常見只能在只能在運算，且訪問結(jié)點時依照運算，且訪問結(jié)點時依照（

2、LIFOLIFO）或）或（FILOFILO）的原則。）的原則。關(guān)鍵是編寫關(guān)鍵是編寫和和函數(shù)，具體實現(xiàn)依順函數(shù)，具體實現(xiàn)依順序棧或鏈棧的存儲結(jié)構(gòu)有別而不同。序?；蜴湕５拇鎯Y(jié)構(gòu)有別而不同。3. 存儲結(jié)構(gòu)存儲結(jié)構(gòu)4. 運算規(guī)則運算規(guī)則5. 實現(xiàn)方式實現(xiàn)方式 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)即棧頂即棧頂基本操作有：基本操作有：建棧、判斷棧滿或?？铡⑷霔?、出棧、建棧、判斷棧滿或棧空、入棧、出棧、讀棧頂元素值，等等。讀棧頂元素值，等等。 是僅在是僅在表尾表尾進行插入、刪除操作的線性表。進行插入、刪除操作的線性表。表尾表尾(即即 an 端端)稱為稱為棧頂棧頂 /top ; 表頭表頭(即即 a1 端端)稱為稱為棧底棧

3、底/base例如：例如： 棧棧 = (a1 , a2 , a3 , .,an-1 , an )插入元素到棧頂?shù)牟迦朐氐綏ｍ數(shù)牟僮鳎Q為操作，稱為入棧入棧。從棧頂刪除最后一從棧頂刪除最后一個元素的操作，稱個元素的操作，稱為為出棧出棧。a an n稱為棧頂元素稱為棧頂元素a a1 1稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能在表的一端（棧頂）進行！的一端（棧頂）進行！4a1a2an入棧入棧出棧出棧棧頂棧頂 top棧底棧底 bottom棧的示意圖棧的示意圖例例1（嚴題集3.1）一個棧的輸入序列為一個棧的輸入序列為1,2,3，若在，若在入棧的過程中允許出棧入棧的過程中允許出棧，則可

4、能得到的出棧序列是，則可能得到的出棧序列是什么？什么？5可以通過窮舉所有可能性來求解：可以通過窮舉所有可能性來求解： 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出，出， 即即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種可能性。種可能性。例

5、例2：設依次進入一個棧的元素序列為設依次進入一個棧的元素序列為c，a，b，d，則則可得到出棧的元素序列是：可得到出棧的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，b6解答解答 A）、）、D）可以，）可以， B）、）、C）不行。）不行。討論：有無通用的判別原則？討論：有無通用的判別原則？即對于輸入序列即對于輸入序列1，2，3，不存在輸出序列，不存在輸出序列3，1，2有！若輸入序列是有！若輸入序列是 ,P,Pj jP Pk kP Pi i (P(Pj jPPk kP=S.stacksize)/棧滿，追加存儲空間 S.base=(SElemType*) real

6、loc (S.base, (S.stacksize+ STACKINCREMENT)*sizeof(SElemType); if(!S.base) exit(OVERFLOW); /存儲分配失敗 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; /先推元素入棧頂，然后棧頂指針自增 return OK;/push 3.1 3.1 棧棧15ABCtopbasePop (&S, &e) S.top-;e = *S.top;e = Ce = CABtopbasePop(&S, &e) S.

7、Top-; e = *S.top;e = Be = BAtopbaseS.top -;e = *S.top;Pop(&S, &e) e = Ae = A( (教材教材p.47)p.47)3.1 3.1 棧棧16Status Pop(SqStack &S, SElemType &e) /若棧不為空，則刪除S的棧頂元素，用e返回其值， / 并返回OK；否則返回ERROR if(S.top=S.base) return ERROR; e=*-S.top; return OK;/Pop 3.1 3.1 棧棧17(1) 鏈棧的構(gòu)造方式鏈棧的構(gòu)造方式以頭指針為棧頂，以頭指針

8、為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除.Node *st, *p;int m=sizeof(Node); 棧也可以用鏈式結(jié)構(gòu)來表示，用鏈式結(jié)構(gòu)來表示的棧就是棧也可以用鏈式結(jié)構(gòu)來表示，用鏈式結(jié)構(gòu)來表示的棧就是鏈棧鏈棧棧頂棧頂棧底棧底 a1 a2an-1 annextdata鏈棧中每個結(jié)點由兩個域構(gòu)成：鏈棧中每個結(jié)點由兩個域構(gòu)成：datadata域和域和nextnext域，其定義為：域，其定義為：typedef Struct SNode SElemType data; Struct SNode * next; Node;鏈棧鏈棧不必設頭結(jié)點不必設頭結(jié)點，因為棧頂（表頭）操作頻繁；，因為棧

9、頂（表頭）操作頻繁；鏈棧一般鏈棧一般不會出現(xiàn)棧滿不會出現(xiàn)棧滿情況，除非沒有空間導致情況，除非沒有空間導致malloc( )malloc( )分配失敗。分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成修改指針即可完成。采用鏈棧存儲方式的優(yōu)點是，可使采用鏈棧存儲方式的優(yōu)點是，可使多個棧共享空間多個棧共享空間；當棧中元素個數(shù)變化較大，且存在多個棧的情況下，當棧中元素個數(shù)變化較大，且存在多個棧的情況下，鏈棧是棧的首選存儲方式。鏈棧是棧的首選存儲方式。幾點說明幾點說明:3.1 3.1 棧棧18Push (SElemType e) p=

10、(Node*)malloc(m); if(!p)上溢上溢 else p-data=e; p-link=st; st=p; Status Pop( ) if(st=NULL)下溢下溢 elsee=st-data;p=st;st=st-link; free(p); return(e); 插入插入表頭表頭從表頭從表頭刪除刪除由此可以看出：一個鏈棧由其由此可以看出：一個鏈棧由其棧頂指針唯一指定。棧頂指針唯一指定。 設設指向棧頂元素，當指向棧頂元素，當=NULL=NULL時表示?？諘r表示?？?.1 3.1 棧棧19Q4Q4：為什么要設計棧？它有什么實際用途？：為什么要設計棧？它有什么實際用途？20調(diào)用函

11、數(shù)或子程序非它莫屬；調(diào)用函數(shù)或子程序非它莫屬；遞歸運算的有力工具；遞歸運算的有力工具；用于保護現(xiàn)場和恢復現(xiàn)場；用于保護現(xiàn)場和恢復現(xiàn)場；簡化了程序設計的問題。簡化了程序設計的問題?！纠?編寫算法，用棧實現(xiàn)表達式編寫算法，用棧實現(xiàn)表達式求值。求值。(表達式求值表達式求值是棧應用的典型例子是棧應用的典型例子, , 參見參見( (教材教材p.52)p.52) 注：本例采用注：本例采用 “算符優(yōu)先法算符優(yōu)先法”。 一個算術(shù)表達式是由一個算術(shù)表達式是由操作數(shù)操作數(shù)（x，y，z）和）和算符算符（* ，/， + ，-，（，），（，），# ）組成）組成.教材教材P53P53中表中表3.13.1給出了算符之間

12、的優(yōu)先級給出了算符之間的優(yōu)先級表達式的表達式的起止符號起止符號 a. 從左算到右從左算到右 b. 先乘除，后加減先乘除，后加減 c. 先括號內(nèi)，后括號外先括號內(nèi)，后括號外輸入計算機的表達式為：輸入計算機的表達式為： # 3*（7 2 ）#211）首先讓表達式的起始符）首先讓表達式的起始符 為為的棧底元素，并置的棧底元素，并置為空棧為空棧 ；2）依次讀入表達式中的每個字符，）依次讀入表達式中的每個字符，若運算符是若運算符是# #且棧頂是且棧頂是# #，則結(jié)束計算，返回，則結(jié)束計算，返回棧頂值。棧頂值。 if（是操作數(shù)）（是操作數(shù)） 則則PUSH（ ，操作數(shù)）；，操作數(shù)）； if（是運算符）（是運

13、算符） 則與則與棧頂元素進行比較，按優(yōu)先級棧頂元素進行比較，按優(yōu)先級( (詳見詳見P53P53表表3.13.1的規(guī)定）的規(guī)定）進行操作；進行操作；為了實現(xiàn)算符優(yōu)先算法，可以設定兩個工作棧：為了實現(xiàn)算符優(yōu)先算法，可以設定兩個工作棧：存放運算符號，存放運算符號， 存放操作數(shù)或運算結(jié)果存放操作數(shù)或運算結(jié)果 。3）直到整個表達式求值完畢（當前讀入的字符和）直到整個表達式求值完畢（當前讀入的字符和棧的棧頂元素均為棧的棧頂元素均為 ）if棧頂元素棧頂元素 運算符運算符，則退棧、按棧頂計算，將結(jié)果壓入則退棧、按棧頂計算，將結(jié)果壓入棧。棧。且該未入棧的運算符要保留，繼續(xù)與下一個棧頂元素比較！且該未入棧的運算符

14、要保留，繼續(xù)與下一個棧頂元素比較！o operatorperator & operand & operand22表達式求值過程表達式求值過程 機內(nèi)運算示意圖機內(nèi)運算示意圖3.1 3.1 棧棧23OPTROPNDINPUT# 3 *（7 2 ）#遇到右括號時，開始執(zhí)行教材遇到右括號時，開始執(zhí)行教材P54最上面的最上面的case 語句部分：語句部分：Pop(OPTR, theta); theta =-Pop(OPND, b); b = 2Pop(OPND, a); a = 7Push(OPND, Operate(a, theta, b); Operate(a,theta,b)=7-

15、2 = 5 OPND 372topbase#*(-topbase35topbase表達式求值過程的描述：表達式求值過程的描述：OPTROPNDINPUTOPERATE3*(7-2)#Push(opnd,3) #*(7-2)#3#Push(optr,*)#, *3(7-2)#Push(optr,()#, *, (37-2)#Push(opnd,7)#, *, (3, 7-2)#Push(optr,-)#, *, (, 3, 72)#Push(opnd,2)#, *, (, 3, 7, 2)#Operate(7-2)#, *, (3, 5)#Pop(optr)#, *3, 5#Operate(3*

16、5)#15#GetTop(opnd)# 3 *（7 2 ）#程序見程序見P53P5324Status EvaluateExpression( OperandType &result) InitStack(OPND); InitStack(OPTR);Push(OPTR ,#); =getchar(); while(c!=#)|(GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c); c=getchar(); else switch(precede(GetTop(OPTR) , c) case : Pop(OPTR ,theta); Pop(OPND,b

17、);a=Pop();thetabreak; /switch /while result=GetTop(OPND);/EvaluateExpression 棧頂與運算符比棧頂與運算符比較并查表較并查表3.13.1判判C C是否是否操作符操作符25算法算法3.43.4，教材，教材p.47p.47問：問：教材教材P53P53表表3.13.1中，中， 1 1和和 2 2哪個對應棧頂元素，哪哪個對應棧頂元素，哪個對應鍵盤輸入值？個對應鍵盤輸入值？答：答：根據(jù)根據(jù)P53 Precede()P53 Precede()函數(shù)可知，函數(shù)可知， 1 1對應棧頂元素對應棧頂元素由表由表3.1可看出，右括號可看出，右括

18、號 ) 和井號和井號 # 作為作為 2時時級別最低；級別最低；由由c 規(guī)則規(guī)則得出：得出： * ，/， + ，-為為 1時的優(yōu)先權(quán)低于時的優(yōu)先權(quán)低于，高于高于由由a規(guī)則規(guī)則得出：得出：= 表明括號內(nèi)的運算已完成；表明括號內(nèi)的運算已完成； = 表明表達式求值完畢。表明表達式求值完畢。26【例例】寫出下面寫出下面C程序段的執(zhí)行結(jié)果。程序段的執(zhí)行結(jié)果。運行結(jié)果為：運行結(jié)果為： 5 5，120120long int fact(int n) long f; if(n1) f=n*fact(n-1); else f=1; return(f); main int n; long y; n=5; y=fact

19、(n); printf(“%d,%ldn”,n,y); 什么叫遞歸？什么叫遞歸？3.1 3.1 棧棧27遞歸模型：遞歸模型：遞歸模型由遞歸出口和遞歸體組成，前者指出遞歸終止的條件，后者指出遞歸中的遞推關(guān)系。例如，計算階乘n!的遞歸模型如下： f(n)=1 n=1 f(n)=nf(n-1)n1遞歸算法設計：遞歸算法設計：遞歸算法設計一般的過程是先求出遞歸模型，然后轉(zhuǎn)換成遞歸算法。求遞歸模型的一般步驟如下：1. 對原問題f(s)進行分析，假設出合理的“較小問題”f(s)2. 假設f(s)是可解的，在此基礎上確定f(s)的解，即給出f(s)與f(s)之間的關(guān)系。3. 確定一個特殊的情況(如f(1)或

20、f(0)的解，由此作為遞歸出口)。3.1 3.1 棧棧28編制遞歸算法要注意些什么？編制遞歸算法要注意些什么？ 遞歸進行是有條件的。一般常把判斷語句加在遞歸語句以前。遞歸進行是有條件的。一般常把判斷語句加在遞歸語句以前。3.1 3.1 棧棧29遞歸的最底層應該有返回值，以供上層遞歸的調(diào)用。否則會遞歸的最底層應該有返回值，以供上層遞歸的調(diào)用。否則會死循環(huán)。死循環(huán)。遞歸調(diào)用需要利用遞歸調(diào)用需要利用堆棧堆棧。參量的初始化應該在遞歸以前。參量的初始化應該在遞歸以前。每次調(diào)用要把本次調(diào)用的參數(shù)和局部變量保存在棧頂。每次調(diào)用要把本次調(diào)用的參數(shù)和局部變量保存在棧頂。每次從下一層調(diào)用返回到上一層調(diào)用時，從棧頂

21、恢復本層調(diào)每次從下一層調(diào)用返回到上一層調(diào)用時，從棧頂恢復本層調(diào)用的參數(shù)和局部變量的值。用的參數(shù)和局部變量的值。void test(int &sum) int x; scanf(x); if(x=0) sum=0; else ; sum+=x; printf(sum);【例例】（嚴題集嚴題集3.103.10）閱讀下列遞歸過程，說明其功能。閱讀下列遞歸過程，說明其功能。注意：注意：最先最先輸入的數(shù)據(jù)輸入的數(shù)據(jù) x1最后才被最后才被累加累加程序功能：對鍵盤輸入數(shù)據(jù)程序功能：對鍵盤輸入數(shù)據(jù)求和，直到輸入求和，直到輸入0 0結(jié)束結(jié)束3.1 3.1 棧棧30輸入輸入x50輸入輸入x10輸入輸入x2輸入輸入x3輸入輸入x4輸出輸出sum0輸出輸出sum0+x4輸出輸出sumx4+x3輸出輸出sum x4+x3 +x2輸出輸出sum x4+x3 +x2+x1斷點地址斷點地址入棧入?！纠窟f歸應用遞歸應用漢諾（漢諾（ HanoiHanoi）塔問題）塔問題傳說在創(chuàng)世紀時，在一個叫Brahma的寺廟里，有三個柱子，其中一柱上有64個盤子從小到大依次