棧的定義表示實(shí)現(xiàn)

1、1數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容：23.1 3.1 棧（棧（StackStack） 3.2 3.2 隊(duì)列隊(duì)列 （Queue)Queue) 第三章第三章 棧和隊(duì)列棧和隊(duì)列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)方式3通常稱，棧和隊(duì)列是限定通常稱，棧和隊(duì)列是限定插入插入和和刪除刪除操作只能在操作只能在表的表的“端點(diǎn)端點(diǎn)”進(jìn)行的線性表。進(jìn)行的線性表。線性表線性表(L) (L) 棧棧(S) (S) 隊(duì)列隊(duì)列(Q)(Q)Insert(L,

2、 i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in棧和隊(duì)列是兩種常用的數(shù)據(jù)類型棧和隊(duì)列是兩種常用的數(shù)據(jù)類型41.1.定義定義3.1 3.1 棧棧限定只能在限定只能在進(jìn)行進(jìn)行插入插入和和刪除刪除運(yùn)算運(yùn)算的線性表。的線性表。表的尾端稱為棧頂，表頭端稱為棧底。表的尾端稱為棧頂，表頭端稱為棧底。例如：例如： 棧棧 = (a1 , a2 , a3 , .,an-1 , an )a an n稱為棧頂元素稱為棧頂元素a a1 1稱為棧底元素稱為棧底元素插入和刪除都只能插入和刪除

3、都只能在表的一端（棧頂）在表的一端（棧頂）進(jìn)行！進(jìn)行！插入元素到棧頂?shù)牟僮?，插入元素到棧頂?shù)牟僮?，稱為稱為入棧入棧。從棧頂刪除最后一個(gè)元從棧頂刪除最后一個(gè)元素的操作，稱為素的操作，稱為出棧出棧。一、概念：一、概念：56與線性表相同，仍為一對(duì)一與線性表相同，仍為一對(duì)一( 1:1)( 1:1)關(guān)系關(guān)系。用用或或存儲(chǔ)均可，但以順序棧存儲(chǔ)均可，但以順序棧更常見(jiàn)更常見(jiàn)只能在只能在運(yùn)算，且訪問(wèn)結(jié)點(diǎn)時(shí)依照運(yùn)算，且訪問(wèn)結(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)有別而不同。

4、3. 3. 存儲(chǔ)結(jié)構(gòu)：存儲(chǔ)結(jié)構(gòu)：4. 4. 運(yùn)算規(guī)則：運(yùn)算規(guī)則：5. 5. 實(shí)現(xiàn)方式：實(shí)現(xiàn)方式： 2. 2. 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：7討論討論1 1：堆棧是什么？它與一般線性表有什么不同？：堆棧是什么？它與一般線性表有什么不同？ 堆棧是一種特殊的線性表，它只能在表的堆棧是一種特殊的線性表，它只能在表的一端一端（即棧頂）（即棧頂）進(jìn)行插入和刪除運(yùn)算。進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于與一般線性表的區(qū)別：僅在于不同。不同。邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)：1:1 1:1 邏輯結(jié)構(gòu)：邏輯結(jié)構(gòu)： 1:1 1:1 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序表表、鏈、鏈表表 存儲(chǔ)結(jié)構(gòu)：順序存儲(chǔ)結(jié)構(gòu)：順序棧棧、鏈、鏈棧棧運(yùn)算

5、規(guī)則：運(yùn)算規(guī)則： 運(yùn)算規(guī)則：運(yùn)算規(guī)則：(LIFO)(LIFO)“進(jìn)進(jìn)”插入插入= =壓入壓入=PUSH=PUSH（a an+1n+1) )“出出”刪除刪除= =彈出彈出=POP(a=POP(an n) )8二、棧的抽象數(shù)據(jù)類型定義二、棧的抽象數(shù)據(jù)類型定義 ADT Stack 數(shù)據(jù)對(duì)象：數(shù)據(jù)對(duì)象： D ai | ai ElemSet, i=1,2,.,n, n0 數(shù)據(jù)關(guān)系：數(shù)據(jù)關(guān)系： R1 | ai-1, aiD, i=2,.,n 約定約定an 端為棧頂，端為棧頂，a1 端為棧底。端為棧底。 基本操作：基本操作： ADT Stack9（1 1）初始化棧）初始化棧 InitStack(&S

6、) （2 2）入棧）入棧 Push(&S,e) （3 3）出棧）出棧 Pop(&S,&e) （4 4）獲取棧頂元素內(nèi)容）獲取棧頂元素內(nèi)容 GetTop(S,&e) （5 5）判斷棧是否為空）判斷棧是否為空 StackEmpty(S)基本操作基本操作: 建棧、判斷棧滿或棧空、入棧、出棧、建棧、判斷棧滿或?？铡⑷霔?、出棧、讀棧頂元素值，等等。讀棧頂元素值，等等。10#define STACK_INIT_SIZE 100; /存儲(chǔ)空間初始分配量 #define STACKINCREMENT 10; /存儲(chǔ)空間分配增量 typedef struct SElemType

7、*base; /棧底指針 SElemType *top; /棧頂指針 int stacksize; /當(dāng)前已分配的存儲(chǔ)空間 SqStack;三、棧的表示和實(shí)現(xiàn)三、棧的表示和實(shí)現(xiàn)1. 1. 順序棧順序棧/ -棧的順序存儲(chǔ)表示棧的順序存儲(chǔ)表示-11棧不存在的條件：棧不存在的條件： base=NULL;棧為空棧為空 的條件的條件 ： base=top;棧滿的條件棧滿的條件 ： top-base=stacksize; a1 a2 an順序棧順序棧S ai低地址低地址高地址高地址棧底棧底棧頂棧頂如圖：如圖：toptop的初值指向棧底，在非的初值指向棧底，在非空棧中空棧中toptop總是指向棧頂元總是指向

8、棧頂元素的下一個(gè)位置上。為浮素的下一個(gè)位置上。為浮動(dòng)端。動(dòng)端。basebase始終指向棧底的位始終指向棧底的位置。為固定端。置。為固定端。12 a1 a2 an順序棧順序棧S ai表頭表頭表尾表尾低地址低地址高地址高地址寫(xiě)入：寫(xiě)入：Si=aSi=ai i讀出：讀出： e= Sie= Si壓入壓入( (PUSH PUSH SS+ +=a+ +=an+1n+1彈出彈出( ( POP POP - - - 低地址低地址高地址高地址Si a1 a2 ai an 順序表順序表S an+1以線性表以線性表 S= (a1 , a2 , . , an-1 , an )為例為例棧底棧底棧頂棧頂棧頂棧頂討論討論2

9、2：順序表和順序棧的操作有何區(qū)別？順序表和順序棧的操作有何區(qū)別？13 Status InitStack (SqStack &S)/ 構(gòu)造一個(gè)空棧S S.base =(SElemType *) malloc (STACK_INIT_SIZE*sizeof ( SElemType); if (!S.base) exit (OVERFLOW); /存儲(chǔ)分配失敗 S.top = S.base; /空棧 S.stacksize = STACK_INIT_SIZE; return OK;/ -基本操作的算法描述基本操作的算法描述-順序棧的建棧操作順序棧的建棧操作構(gòu)造空棧構(gòu)造空棧S S14順序棧的入

10、棧操作順序棧的入棧操作例如用堆棧存放（例如用堆棧存放（A A，B B，C C，D D）AACBABAtop核心語(yǔ)句：核心語(yǔ)句：Push (B);Push (C);Push (D);topbasetoptoptop低地址低地址LPush (A);高地址高地址MBCD順序棧順序棧入棧入棧函數(shù)函數(shù)PushPush（&S, e&S, e）入棧入?？谠E：棧頂指針口訣：棧頂指針top top “ “先壓后加先壓后加” ” StopStop+ +=e+ +=e15 Status Push (SqStack &S, SElemType e) / 若棧不滿，則將元素 e 插入棧頂，并返回

11、 OK;否則返回 OVERFLOW if (S.top - S.base = S.stacksize) return OVERFLOW; *S.top+ = e; return OK;若棧滿，可追加存若棧滿，可追加存儲(chǔ)空間。儲(chǔ)空間。16順序棧出棧操作順序棧出棧操作例如從棧中取出例如從棧中取出B BAtoptopABCBAtopDCBAtop低地址低地址L高地址高地址MD核心語(yǔ)句：核心語(yǔ)句：Pop ( D);順序棧出棧函數(shù)順序棧出棧函數(shù)Pop(&S,&ePop(&S,&e ) )出棧出?？谠E：棧頂指針口訣：棧頂指針top top “ “先減后彈先減后彈”e=S-

12、-top;e=S- -top;Pop (C );Printf( Pop (B) );17Status Pop (SqStack &S, SElemType &e) / 若棧不空，則刪除S的棧頂元素，用 e 返回其值，并返回OK；否則返回ERROR if (S.top = = S.base) return ERROR;/空棧 e = *-S.top; return OK;結(jié)論：由于棧的插入和刪除操作具有它的特殊性，結(jié)論：由于棧的插入和刪除操作具有它的特殊性，所以用順序存儲(chǔ)結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)所以用順序存儲(chǔ)結(jié)構(gòu)表示的棧并不存在插入刪除數(shù)據(jù)元素時(shí)需要移動(dòng)的問(wèn)題，但棧容量難以

13、擴(kuò)充的弱據(jù)元素時(shí)需要移動(dòng)的問(wèn)題，但棧容量難以擴(kuò)充的弱點(diǎn)仍舊沒(méi)有擺脫。點(diǎn)仍舊沒(méi)有擺脫。18討論討論3 3：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？為什么要設(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)題。下面用下面用4個(gè)例子來(lái)幫助理解堆棧：個(gè)例子來(lái)幫助理解堆棧：19void test(int &sum)int x;scanf(x);if(x=0)sum=0;else;sum+=x;printf(sum);斷點(diǎn)地址斷點(diǎn)地

14、址入棧入棧例例1 1（嚴(yán)題集嚴(yán)題集3.103.10）閱讀下列遞歸過(guò)程，說(shuō)明其功能。閱讀下列遞歸過(guò)程，說(shuō)明其功能。輸入輸入x10輸入輸入x50輸入輸入x2輸入輸入x3輸入輸入x4輸出輸出sum0輸出輸出sum0+x4輸出輸出sumx4+x3輸出輸出sum x4+x3 +x2輸出輸出sum x4+x3 +x2+x1注意：最先注意：最先輸入的數(shù)據(jù)輸入的數(shù)據(jù) x1 最后才被最后才被累加累加程序功能：對(duì)鍵盤(pán)輸入數(shù)據(jù)程序功能：對(duì)鍵盤(pán)輸入數(shù)據(jù)求和，直到輸入求和，直到輸入0 0結(jié)束結(jié)束20例例2（嚴(yán)題集嚴(yán)題集3.13.1）一個(gè)棧的輸入序列為一個(gè)棧的輸入序列為1,2,3，若，若在在入棧的過(guò)程中允許出棧入棧的過(guò)程

15、中允許出棧，則可能得到的出棧序列，則可能得到的出棧序列是什么？是什么？答：答： 可以通過(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出，出， 即即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ì)有

16、合計(jì)有5 5種可能性。種可能性。例例3 3：一個(gè)棧的輸入序列是一個(gè)棧的輸入序列是1234512345，若在，若在入棧的過(guò)入棧的過(guò)程中允許出棧程中允許出棧，則棧的輸出序列則棧的輸出序列4351243512可能實(shí)現(xiàn)可能實(shí)現(xiàn)嗎嗎？1234512345的輸出呢？的輸出呢？21例例4：設(shè)依次進(jìn)入一個(gè)棧的元素序列為設(shè)依次進(jìn)入一個(gè)棧的元素序列為c c，a a，b b，d d，則可得到出棧的元素序列是：則可得到出棧的元素序列是： ）a a，b b，c c，d d ）c c，d d，a a，b b ）b b，c c，d d，a a ）a a，c c，d d，b bA）、）、D）可以，）可以， B）、）、C）不行

17、。）不行。討論：有無(wú)通用的判別原則？討論：有無(wú)通用的判別原則？有！若輸入序列有！若輸入序列 ：,P,Pi i P Pj j P Pk k ，一定不存在這樣的輸出序列：一定不存在這樣的輸出序列：, P, Pk k P Pi i P Pj j 答：答：即對(duì)于輸入序列即對(duì)于輸入序列1，2，3，不存在輸出序列，不存在輸出序列3，1，2答：答：4351243512不可能實(shí)現(xiàn)，主要是其中的不可能實(shí)現(xiàn)，主要是其中的1212順序不能實(shí)順序不能實(shí)現(xiàn)；現(xiàn)；1234512345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。即可。 222 2、若已知一個(gè)棧的進(jìn)棧序列是、若已知一個(gè)棧的進(jìn)

18、棧序列是1 1，2 2，3,3,.,n,.,n,其輸出序其輸出序 列為列為P P1 1, P, P2 2, P, P3 3, , . P. Pn n, , 若若P Pn n=n,=n,則則P Pi i(1=in)(1=in)為為 A. i B. n-iA. i B. n-i C. n-i+1 D. C. n-i+1 D. 不確定不確定1 1、若已知一個(gè)棧的進(jìn)棧序列是、若已知一個(gè)棧的進(jìn)棧序列是1 1，2 2，3,3,.,n,.,n,其輸出序其輸出序列為列為P P1 1,P,P2 2,P,P3 3, ,.P.Pn n, ,若若P P1 1=n, =n, 則則P Pi i(1=in)(1=in)為為

19、 A. i B. n-iA. i B. n-i C. n-i+1 D. C. n-i+1 D. 不確定不確定選擇選擇CD234 4、若已知一個(gè)棧的進(jìn)棧序列是、若已知一個(gè)棧的進(jìn)棧序列是P P1 1,P,P2 2,P,P3 3, ,.P.Pn n, , 其輸出序其輸出序列為列為1 1，2 2，3,3,.,n,.,n,若若P P3 3=1=1，則，則P P1 1為為 A. A. 可能是可能是2 B. 2 B. 一定是一定是2 2 C. C. 不可能是不可能是2 D. 2 D. 不可能是不可能是3 3C3 3、若已知一個(gè)棧的進(jìn)棧序列是、若已知一個(gè)棧的進(jìn)棧序列是1 1，2 2，3,3,.,n,.,n,其輸出序其輸出序列為列為P P1