棧和隊(duì)列—棧的表示與實(shí)現(xiàn)

1、13.1 堆棧（堆棧（Stack） 基本概念、抽象數(shù)據(jù)類型、順序表示和實(shí)現(xiàn)、鏈基本概念、抽象數(shù)據(jù)類型、順序表示和實(shí)現(xiàn)、鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)式表示和實(shí)現(xiàn) 3.2 堆棧應(yīng)用堆棧應(yīng)用 括號(hào)匹配問(wèn)題括號(hào)匹配問(wèn)題 3.3 隊(duì)列（隊(duì)列（Queue） 基本概念、抽象數(shù)據(jù)類型、順序隊(duì)列、順序循環(huán)基本概念、抽象數(shù)據(jù)類型、順序隊(duì)列、順序循環(huán)隊(duì)列、鏈?zhǔn)疥?duì)列、隊(duì)列的應(yīng)用隊(duì)列、鏈?zhǔn)疥?duì)列、隊(duì)列的應(yīng)用 第三章第三章 堆棧和隊(duì)列堆棧和隊(duì)列21.1. 定義定義與線性表相同，仍為一對(duì)一與線性表相同，仍為一對(duì)一( 1:1)關(guān)系關(guān)系。用用或或存儲(chǔ)均可，但以順序棧更常見(jiàn)存儲(chǔ)均可，但以順序棧更常見(jiàn)只能在只能在運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照運(yùn)算，且訪問(wèn)

2、結(jié)點(diǎn)時(shí)依照（LIFOLIFO）或）或（FILOFILO）的原則。）的原則。關(guān)鍵是編寫(xiě)關(guān)鍵是編寫(xiě)和和函數(shù)，具體實(shí)現(xiàn)依順函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。序棧或鏈棧的存儲(chǔ)結(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)方式 2. 邏輯結(jié)構(gòu)邏輯結(jié)構(gòu)限定只能在表的限定只能在表的進(jìn)行插入和刪除操作的線性表。進(jìn)行插入和刪除操作的線性表。特點(diǎn)：后進(jìn)先出。特點(diǎn)：后進(jìn)先出。基本操作有基本操作有：建棧、判斷棧滿或?？?、入棧、出棧、建棧、判斷棧滿或?？?、入棧、出棧、讀棧頂元素值等等。讀棧頂元素值等等。3在棧滿時(shí)還進(jìn)行入棧運(yùn)算，必定會(huì)產(chǎn)生空在棧滿時(shí)還進(jìn)行入棧運(yùn)算，必定會(huì)產(chǎn)

3、生空間的溢出間的溢出7 7、棧、?！跋乱缦乱纭? 6、棧、?！吧弦缟弦纭碑?dāng)?？諘r(shí)仍進(jìn)行出棧運(yùn)算，必定會(huì)產(chǎn)生當(dāng)棧空時(shí)仍進(jìn)行出棧運(yùn)算，必定會(huì)產(chǎn)生空間的溢出。空間的溢出。4 是僅在是僅在表尾表尾進(jìn)行插入、刪除操作的線性表。進(jìn)行插入、刪除操作的線性表。表尾表尾(即即 an 端端)稱為稱為棧頂棧頂 /top ; 表頭表頭(即即 a1 端端)稱為稱為棧底棧底/base例如：例如： 棧棧 = (a , a2 , a3 , .,an-1 , an )插入元素到棧頂?shù)牟迦朐氐綏ｍ數(shù)牟僮?，稱為操作，稱為入棧入棧。從棧頂刪除最后一從棧頂刪除最后一個(gè)元素的操作，稱個(gè)元素的操作，稱為為出棧出棧。a an n稱為棧頂元

4、素稱為棧頂元素a a1 1稱為棧底元素稱為棧底元素插入和刪除都只能在表插入和刪除都只能在表的一端（棧頂）進(jìn)行！的一端（棧頂）進(jìn)行！注：堆?？梢酝瓿杀容^復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。5例例1 1：堆棧是什么？它與一般線性表有什么不同？：堆棧是什么？它與一般線性表有什么不同？ 堆棧是一種特殊的線性表，它只能在表的堆棧是一種特殊的線性表，它只能在表的一端（即一端（即棧頂）棧頂）進(jìn)行插入和刪除運(yùn)算。進(jìn)行插入和刪除運(yùn)算。 與一般線性表的區(qū)別：僅在于與一般線性表的區(qū)別：僅在于不同。不同。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：1:1 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 1:1 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)

5、結(jié)構(gòu)：順序表表、鏈、鏈表表 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序棧棧、鏈、鏈棧棧運(yùn)算規(guī)則：運(yùn)算規(guī)則： 運(yùn)算規(guī)則：運(yùn)算規(guī)則：(LIFO)“進(jìn)進(jìn)”插入插入= =壓入壓入“出出”刪除刪除= =彈彈出出6例例2 2、一個(gè)棧的輸入序列為一個(gè)棧的輸入序列為1,2,3，若在，若在入棧的過(guò)程中允入棧的過(guò)程中允許出棧許出棧，則可能得到的出棧序列是什么？，則可能得到的出棧序列是什么？解：可以通過(guò)窮舉所有可能性來(lái)求解：可以通過(guò)窮舉所有可能性來(lái)求解： 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出，出， 即即13

6、2132； 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；合計(jì)有合計(jì)有5 5種可能性。種可能性。7例例3 3、一個(gè)棧的輸入序列是一個(gè)棧的輸入序列是12345，若在，若在入棧的過(guò)入棧的過(guò)程中允許出棧程中允許出棧，則棧的輸出序列則棧的輸出序列43512可能實(shí)現(xiàn)可能實(shí)現(xiàn)嗎？嗎？12345的輸出呢？的輸出呢？解：解： 4351243512不可能實(shí)現(xiàn)，主要是其中的不可能實(shí)現(xiàn)，主要是其中的1212順序

7、不順序不能實(shí)現(xiàn)；能實(shí)現(xiàn)； 1234512345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。彈出即可。 8二、堆棧抽象數(shù)據(jù)類型二、堆棧抽象數(shù)據(jù)類型數(shù)據(jù)集合：數(shù)據(jù)集合： a a0 0, a, a1 1, , , a , an-1 n-1 a ai i的數(shù)據(jù)類型為的數(shù)據(jù)類型為 DataTypeDataType操作集合操作集合：(1)StackInitiate(S) (1)StackInitiate(S) 初始化堆棧初始化堆棧S S (2)StackNotEmpty(S) (2)StackNotEmpty(S) 堆棧堆棧S S非空否非空否 (3)StackPush(S,x

8、) (3)StackPush(S,x) 入棧入棧 (4)StackPop(S,d) (4)StackPop(S,d) 出棧出棧 (5)StackTop(S,d) (5)StackTop(S,d) 取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素 等等9三、堆棧的順序表示和實(shí)現(xiàn)三、堆棧的順序表示和實(shí)現(xiàn)1、順序（堆）棧順序（堆）棧 順序存儲(chǔ)結(jié)構(gòu)的堆棧。順序存儲(chǔ)結(jié)構(gòu)的堆棧。2、順序棧的存儲(chǔ)結(jié)構(gòu)、順序棧的存儲(chǔ)結(jié)構(gòu) 它是利用一組地址連續(xù)的存儲(chǔ)它是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)指針?biāo)?，同時(shí)設(shè)指針top指示棧頂元素的指示棧頂元素的當(dāng)前位置。用當(dāng)前位置。用C語(yǔ)言定

9、義為：語(yǔ)言定義為：typedef struct DataType stackMaxStackSize; int top;SeqStack; a0 a1 an-1順序棧順序棧S ai an棧底棧底棧頂棧頂10 a0 a1 an-1順序棧順序棧S ai問(wèn)：順序表和順序棧的操作有何區(qū)別？問(wèn)：順序表和順序棧的操作有何區(qū)別？表頭表頭表尾表尾低地址低地址高地址高地址寫(xiě)入：寫(xiě)入：Si= ai讀出：讀出： e= Si壓入壓入(SStop+top+=a=an n彈出彈出( e=Se=S-top-top 低地址低地址高地址高地址Si a0 a1 ai an-1 順序表順序表S an以線性表以線性表 S= (a0

10、, a1 , . , an-2 , an-1)為例為例棧底棧底棧頂棧頂前提：一定要前提：一定要棧頂指針棧頂指針棧頂棧頂11棧不存在的條件：棧不存在的條件： base=NULL;棧為空棧為空 的條件的條件 ： base=top;棧滿的條件棧滿的條件 ： top-base=MaxSize; a0 a1 an-1順序棧順序棧S ai低地址低地址高地址高地址 an棧底棧底棧頂棧頂入棧入?？谠E：堆棧指針口訣：堆棧指針top “先先加后壓加后壓” : S+S+toptop=a=an n出棧出棧口訣：堆棧指針口訣：堆棧指針top “先先彈后減彈后減” : e=Se=Stoptop- 12問(wèn)：為什么要設(shè)計(jì)堆棧

11、？它有什么獨(dú)特用途？問(wèn)：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？1.調(diào)用函數(shù)或子程序非它莫屬；調(diào)用函數(shù)或子程序非它莫屬；2.遞歸遞歸運(yùn)算的有力工具；運(yùn)算的有力工具；3.用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；用于保護(hù)現(xiàn)場(chǎng)和恢復(fù)現(xiàn)場(chǎng)；4.簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題簡(jiǎn)化了程序設(shè)計(jì)的問(wèn)題。下面用下面用3個(gè)例子來(lái)幫助理解堆棧：個(gè)例子來(lái)幫助理解堆棧：13void test(int *sum)int x;scanf(“%d”,&x);if(x=0)sum=0;else;sum+=x;printf(sum);斷點(diǎn)地址斷點(diǎn)地址入棧入棧例例1 1、閱讀下列遞歸過(guò)程，說(shuō)明其功能。閱讀下列遞歸過(guò)程，說(shuō)明其功能。輸入輸入x10輸入輸入x50輸

12、入輸入x2輸入輸入x3輸入輸入x4輸出輸出sum0輸出輸出sum0+x4輸出輸出sumx4+x3輸出輸出sum x4+x3 +x2輸出輸出sum x4+x3 +x2+x1注意：最先注意：最先輸入的數(shù)據(jù)輸入的數(shù)據(jù) x x1 1 最后才被最后才被累加累加程序功能：對(duì)鍵盤(pán)輸入數(shù)程序功能：對(duì)鍵盤(pán)輸入數(shù)據(jù)求和，直到輸入據(jù)求和，直到輸入0 0結(jié)束結(jié)束14例例2 2、一個(gè)棧的輸入序列是一個(gè)棧的輸入序列是12345，若在，若在入棧的過(guò)入棧的過(guò)程中允許出棧程中允許出棧，則棧的輸出序列則棧的輸出序列43512可能實(shí)現(xiàn)可能實(shí)現(xiàn)嗎嗎？12345的輸出呢？的輸出呢？答：答：4351243512不可能實(shí)現(xiàn)，主要是其中的不

13、可能實(shí)現(xiàn)，主要是其中的1212順序不能實(shí)順序不能實(shí)現(xiàn)；現(xiàn)；1234512345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。即可。 思考：有無(wú)通用的判別原則？思考：有無(wú)通用的判別原則？15例例3、設(shè)依次進(jìn)入一個(gè)棧的元素序列為設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：則可得到出棧的元素序列是： ）a，b，c，d ）c，d，a，b ）b，c，d，a ）a，c，d，bA）、）、D）可以，）可以， B）、）、C）不行。）不行。討論：有無(wú)通用的判別原則？討論：有無(wú)通用的判別原則？有！若輸入序列是有！若輸入序列是 ,P,Pj jP Pk kP P

14、i i (P(Pj jPPk kPtop = 0; /*定義初始棧頂下標(biāo)值*/17(2)(2)判棧非空否判棧非空否 int StackNotEmpty(SeqStack S)/*判順序堆棧S非空否，非空則返回1，否則返回0*/ if(S.top top = MaxStackSize)printf(堆棧已滿無(wú)法插入! n); return 0;else S-stackS-top = x; S-top +; return 1; 19(4)(4)出棧出棧int StackPop(SeqStack *S, DataType *d)/*彈出順序堆棧S的棧頂數(shù)據(jù)元素值到參數(shù)d ，出棧成功則返回1，否則返回

15、0*/ if(S-top top -; *d = S-stackS-top; return 1; 20(5)(5)取棧頂數(shù)據(jù)元素取棧頂數(shù)據(jù)元素int StackTop(SeqStack S, DataType *d)/*取順序堆棧S的當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù)d ，成功則返回1，否則返回0*/ if(S.top top +;S-stackS-top = x;toptoptoptop低地址低地址L高地址高地址MBCD22例：從棧中取出例：從棧中取出 DCBAtoptopDCABDCBAtopDCBAtop低地址低地址L高地址高地址MD順序棧出棧函數(shù)的核心語(yǔ)句順序棧出棧函數(shù)的核心語(yǔ)句：*d = S-

16、stackS-top; S-top -;注：DataType *d； SeqStack *S；23四、堆棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)四、堆棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1、 鏈棧的存儲(chǔ)結(jié)構(gòu)鏈棧的存儲(chǔ)結(jié)構(gòu) 以頭指針為棧頂，以頭指針為棧頂，在頭指針處在頭指針處插入或刪除插入或刪除.棧頂棧頂棧底棧底棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示，用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示的棧就是棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示，用鏈?zhǔn)浇Y(jié)構(gòu)來(lái)表示的棧就是鏈棧鏈棧 a0 a1an-2an-1nextdata鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：datadata域和域和nextnext域，其定義為：域，其定義為：typedef struct snode DataT

17、ype data; struct snode * next; LSNode;242 2、鏈?zhǔn)蕉褩５牟僮鲗?shí)現(xiàn)、鏈?zhǔn)蕉褩５牟僮鲗?shí)現(xiàn)(1) 入棧int StackPush(LSNode *head, DataType x) LSNode *p;if(p = (LSNode *)malloc(sizeof(LSNode) = NULL) printf(內(nèi)存空間不足無(wú)法插入! n);return 0; p-data = x;p-next = head-next;/*新結(jié)點(diǎn)鏈入棧頂*/head-next = p; /*新結(jié)點(diǎn)成為新的棧頂*/return 1;25(2)(2)出棧出棧int StackPop

18、(LSNode *head, DataType *d) LSNode *p = head-next;if(p = NULL) printf(堆棧已空出錯(cuò)！);return 0;head-next = p-next; /*刪除原棧頂結(jié)點(diǎn)*/*d = p-data; /*原棧頂結(jié)點(diǎn)元素賦予d*/free(p); /*釋放原棧頂結(jié)點(diǎn)內(nèi)存空間*/return 1; 注： 由此可以看出：一個(gè)鏈棧由其由此可以看出：一個(gè)鏈棧由其棧頂指針唯一指定棧頂指針唯一指定 設(shè)設(shè)headhead指向棧頂元素，則指向棧頂元素，則head=NULL head=NULL 表示?？毡硎緱？?61)1) 在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)

19、現(xiàn)影響不大，棧頂（表在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)現(xiàn)影響不大，棧頂（表頭）操作頻繁，頭）操作頻繁，可可不設(shè)頭結(jié)點(diǎn)不設(shè)頭結(jié)點(diǎn)鏈棧。鏈棧。2)2) 一般一般不會(huì)出現(xiàn)棧滿不會(huì)出現(xiàn)棧滿情況；除非沒(méi)有空間導(dǎo)致情況；除非沒(méi)有空間導(dǎo)致mallocmalloc分分配失敗。配失敗。3)3) 鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成修改指針即可完成。4)4) 采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使采用鏈棧存儲(chǔ)方式的優(yōu)點(diǎn)是，可使多個(gè)棧共享空間多個(gè)棧共享空間；當(dāng)棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，當(dāng)棧中元素個(gè)數(shù)變化較大，且存在多個(gè)棧的情況下，鏈棧是棧的首

20、選存儲(chǔ)方式。鏈棧是棧的首選存儲(chǔ)方式。幾點(diǎn)說(shuō)明幾點(diǎn)說(shuō)明:27例例1：括號(hào)匹配的檢驗(yàn)括號(hào)匹配的檢驗(yàn)假設(shè)一個(gè)算法表達(dá)式中包含圓括號(hào)、方括號(hào)和假設(shè)一個(gè)算法表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫(xiě)一個(gè)判別表達(dá)式花括號(hào)三種類型的括號(hào)，編寫(xiě)一個(gè)判別表達(dá)式中括號(hào)是否正確配對(duì)的函數(shù)。中括號(hào)是否正確配對(duì)的函數(shù)。 設(shè)計(jì)設(shè)計(jì)思路：用棧暫存左括號(hào)思路：用棧暫存左括號(hào)28void ExpIsCorrect(char exp, intvoid ExpIsCorrect(char exp, int n) n)/判斷有判斷有n n個(gè)字符的字符串個(gè)字符的字符串expexp左右括號(hào)是否配對(duì)正確左右括號(hào)是否配對(duì)正確 S

21、eqStack myStack; SeqStack myStack; int int i; i;char c;char c; StackInitiate(&myStackStackInitiate(&myStack);); for(i=0;in;i+) for(i=0;in;i+) if(expiif(expi=()|(expi= )|(expi= )=()|(expi= )|(expi= ) StackPush(&myStack, expi StackPush(&myStack, expi);/);/入棧入棧else if(expi = ) & StackNotEmpty(myStackel

22、se if(expi = ) & StackNotEmpty(myStack) ) & StackTop(myStack & StackTop(myStack, &c) & c = () , &c) & c = () StackPop(&myStackStackPop(&myStack, &c); , &c); /出棧出棧29else if(expi = ) & StackNotEmpty(myStackelse if(expi = ) & StackNotEmpty(myStack) ) & StackTop(myStack& StackTop(myStack, &c) & c != () , &c) & c != () printfprintf(左右括號(hào)配對(duì)次序不正確！左右括號(hào)配對(duì)次序不正確！n);n);return;return; else if(expi = & StackNotEmpty(myStack else if(expi