數(shù)據(jù)結(jié)構(gòu) 課件 第3章 棧

第3章棧3.1棧的應(yīng)用實(shí)例及概念3.2棧的存儲(chǔ)方式3.2.1棧的順序存儲(chǔ)結(jié)構(gòu)3.2.2棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)3.3棧的有關(guān)操作3.3.1順序棧的操作實(shí)現(xiàn)3.3.2鏈棧的操作實(shí)現(xiàn)3.4棧的ADT定義3.5棧的應(yīng)用實(shí)例--算術(shù)表達(dá)式的求值3.6上機(jī)實(shí)驗(yàn)本章小結(jié)習(xí)題1總體要求：熟悉棧的定義熟悉棧的抽象數(shù)據(jù)類型描述中各種操作的含義熟練掌握順序存儲(chǔ)棧的建立、壓入、彈出算法熟練掌握鏈?zhǔn)酱鎯?chǔ)棧的建立、壓入、彈出算法

核心技能點(diǎn)：熟練掌握順序存儲(chǔ)棧的建立、壓入、彈出算法實(shí)現(xiàn)的能力熟練掌握鏈?zhǔn)酱鎯?chǔ)棧的建立、壓入、彈出算法實(shí)現(xiàn)的能力棧應(yīng)用于實(shí)際問(wèn)題的能力擴(kuò)展技能點(diǎn)：棧各種存儲(chǔ)結(jié)構(gòu)算法C語(yǔ)言環(huán)境的實(shí)現(xiàn)

2第3章棧相關(guān)知識(shí)點(diǎn)：C語(yǔ)言數(shù)組的知識(shí)C語(yǔ)言結(jié)構(gòu)體的知識(shí)C語(yǔ)言指針的知識(shí)C語(yǔ)言函數(shù)的知識(shí)學(xué)習(xí)重點(diǎn)：熟悉棧的定義

熟悉棧的抽象數(shù)據(jù)類型描述中各種操作的含義

掌握棧各種存儲(chǔ)結(jié)構(gòu)下算法的實(shí)現(xiàn)3第3章棧3.1棧的應(yīng)用實(shí)例及概念

在日常生活中，有許多后進(jìn)先出的例子。例如：在洗盤子時(shí)，我們總是把洗好的盤子逐個(gè)放在其他已洗好的盤子的上面，而在使用盤子的時(shí)候，總是從上面逐個(gè)取出。在這個(gè)例子中我們可以看到，無(wú)論是放盤子還是取盤子，都是在一疊盤子的上端進(jìn)行，而且是后放入的先取出。又如在向手槍子彈夾中推入子彈時(shí)，后推入的子彈總是壓在已有子彈的上面，而從子彈夾中取出子彈時(shí)，總是先取出最后推入的子彈。上述實(shí)例正是棧操作特點(diǎn)的形象表示。

4第3章棧

棧（Stack）是限定只能在表的一端進(jìn)行操作的線性表。在表中允許插入和刪除的一端叫做棧頂(Top)，而不允許插入和刪除的另一端叫做棧底(Bottom)，向棧頂插入一個(gè)元素的操作叫做入棧(Push)操作，從棧頂取出一個(gè)元素的操作叫做出棧(Pop)操作。棧一經(jīng)確定，則棧底便固定不變，而棧頂隨入棧、出棧操作不斷地變化。由于棧的操作具有“后進(jìn)先出”的特點(diǎn)，因此棧又稱作后進(jìn)先出表(LIFO，即LastInFirstOut)。

5第3章棧6第3章棧

在圖3.1所表示的棧中，a0是棧底元素，an-1是棧頂元素。棧中的元素以a0，a1，…，ai，…，an-1的順序進(jìn)棧，如果對(duì)這個(gè)棧執(zhí)行入棧操作，入棧的元素為an，，則該棧的棧頂元素就變?yōu)閍n；如果對(duì)這個(gè)棧執(zhí)行出棧操作，則棧頂元素an-1從棧中取出，當(dāng)前的棧頂元素就變?yōu)閍n-2。

一般，一個(gè)棧是由n個(gè)元素組成的有限序列，可記作：

S=(a0，a1，…，ai，…，an-1)

其中，每個(gè)ai都是棧S的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類型，但必須屬于同一種數(shù)據(jù)對(duì)象。

圖3.1棧結(jié)構(gòu)示意圖

綜上所述，棧是一種數(shù)據(jù)類型，其數(shù)據(jù)元素之間呈線性關(guān)系。其操作的特點(diǎn)是“后進(jìn)先出”，主要操作有進(jìn)棧、出棧和取棧頂元素等。

7第3章棧

在計(jì)算機(jī)科學(xué)中，棧的應(yīng)用非常廣泛。棧與遞歸過(guò)程的關(guān)系也非常密切。要實(shí)現(xiàn)遞歸過(guò)程，必須設(shè)置一個(gè)數(shù)據(jù)棧來(lái)存放遞歸過(guò)程中的參數(shù)與局部變量等信息，當(dāng)遞歸調(diào)用時(shí)，遞歸深度進(jìn)一層，棧的深度也增加一層；當(dāng)遞歸返回時(shí)，遞歸深度退一層，棧的深度也減少一層，不然就無(wú)法正確地傳遞遞歸過(guò)程執(zhí)行過(guò)程中的有關(guān)信息。在編譯程序中，棧又被用于實(shí)現(xiàn)表達(dá)式的翻譯或被用于檢查表達(dá)式中的各種括號(hào)是否配對(duì)。在處理迷宮等試探性求解的問(wèn)題中，為了能到達(dá)正確的目的地，必須試探每一條可能的路徑。當(dāng)往前繼續(xù)探索無(wú)望時(shí)，需要回頭另選通路繼續(xù)試探。為此，必須設(shè)置一個(gè)棧來(lái)記錄已走過(guò)的路徑上的每一點(diǎn)的有關(guān)信息，以便正確地另選通路繼續(xù)試探。

8第3章棧3.2棧的存儲(chǔ)方式與線性表類似，棧也有順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種存儲(chǔ)方式。按順序存儲(chǔ)結(jié)構(gòu)建立起來(lái)的棧稱為順序棧，按鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)建立起來(lái)的棧稱為鏈棧。

3.2.1棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)是指使用一組地址連續(xù)的存儲(chǔ)單元來(lái)依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)置一個(gè)指針指示棧頂元素的當(dāng)前位置。在C語(yǔ)言中，通常可使用一個(gè)一維數(shù)組stack[MaxStackSize]來(lái)存儲(chǔ)棧中的數(shù)據(jù)元素，使用一個(gè)整型top來(lái)表示棧頂?shù)奈恢?。棧的順序存?chǔ)結(jié)構(gòu)如圖3.2所示。9第3章棧

圖3.2棧的順序存儲(chǔ)結(jié)構(gòu)

棧頂指示器top的取值可表示棧的當(dāng)前狀態(tài)。當(dāng)top=0時(shí)，則棧為空棧，也就是說(shuō)空棧的指針值為0；當(dāng)top=MaxStackSize-1時(shí)，則為棧滿；在棧非空的狀態(tài)下，top的值在1與MaxStackSize-1之間，這時(shí)棧中有top個(gè)數(shù)據(jù)元素。其中，stack[1]為最早進(jìn)入棧的元素，即為棧底元素，而stack[top]為最后進(jìn)入棧的元素，即為棧頂元素。圖3.3中所表示的是棧頂指針與棧中元素之間的這種關(guān)系。

10第3章棧

圖3.3棧頂指針與棧中元素之間的關(guān)系(a)空棧；(b)棧滿；(c)非空棧

在棧的順序存儲(chǔ)結(jié)構(gòu)中，應(yīng)該包括一個(gè)存儲(chǔ)數(shù)據(jù)元素的一維數(shù)組，取名為stack，其長(zhǎng)度可取為一個(gè)適當(dāng)?shù)淖畲笾礛axStackSize，另外還應(yīng)包括一個(gè)表示棧頂位置的整型變量，取其名為top，使用C語(yǔ)言，我們可以用以下的結(jié)構(gòu)類型來(lái)表示順序棧，設(shè)其類型名用SeqStack表示。

MaxStackSize=棧中允許存放元素個(gè)數(shù)的最大值；

typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack;

在定義了順序棧的類型SeqStack之后，我們就可以定義屬于這種類型的棧，例如：SeqStacks；以后可在程序中引用順序棧s的相應(yīng)成分，例如，s．top表示棧頂指示器，s.stack[top]表示棧頂元素等等。

11第3章棧

12第3章棧

3.2.2棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

以上我們討論了棧的順序存儲(chǔ)結(jié)構(gòu)，這種存儲(chǔ)方式所存在的問(wèn)題是要預(yù)先為它確定存儲(chǔ)空間的大小，當(dāng)棧的最大容量難以事先估計(jì)時(shí)，最好采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧簡(jiǎn)稱為鏈棧，如圖3.4所示。在鏈棧中，鏈尾元素相當(dāng)于棧底元素，鏈頭元素相當(dāng)于棧頂元素，鏈頭指針相當(dāng)于棧頂指針。入棧操作相當(dāng)于從鏈頭插入一個(gè)元素，出棧操作相當(dāng)于從鏈頭刪除一個(gè)元素，因此在這種存儲(chǔ)結(jié)構(gòu)下，棧的操作非常容易實(shí)現(xiàn)。

13第3章棧

假設(shè)結(jié)點(diǎn)類型名為L(zhǎng)SNode，結(jié)點(diǎn)類型中數(shù)據(jù)域名為data，指針域名為next，數(shù)據(jù)元素的類型為DataType，則鏈棧類型LSNode可定義如下：typedefstructsnode{DataTypedata;structsnode*next;}LSNode;

鏈?？梢杂靡粋€(gè)指向棧頂?shù)闹羔樞妥兞縯op來(lái)表示，其定義如下：LSNode*top；當(dāng)top=NULL時(shí)，這個(gè)棧就成為空棧；當(dāng)top不等于NULL時(shí)，就可以通過(guò)top指針來(lái)訪問(wèn)棧頂元素。對(duì)于鏈棧，由于它是動(dòng)態(tài)地生成結(jié)點(diǎn)，因此一般不會(huì)出現(xiàn)棧滿的情形，只有當(dāng)整個(gè)可用空間都被占滿，malloc()都無(wú)法執(zhí)行的情形下才會(huì)發(fā)生上溢現(xiàn)象。

圖3.4鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的棧

14第3章棧

3.3棧的有關(guān)操作在存儲(chǔ)結(jié)構(gòu)確定以后，我們要考慮棧操作的實(shí)現(xiàn)。下面我們分別按棧的順序存儲(chǔ)結(jié)構(gòu)與鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)兩種方式來(lái)介紹有關(guān)算法的實(shí)現(xiàn)過(guò)程。

3.3.1順序棧的操作實(shí)現(xiàn)下面討論在順序存儲(chǔ)結(jié)構(gòu)方式下，入棧及出棧等操作的實(shí)現(xiàn)。1.

入棧操作順序棧的入棧操作可表示為：

intStackPush(SeqStack*S,DataTypex)；其中，參數(shù)S表示指定的棧，其類型為順序棧類型SeqStack，參數(shù)x表示入棧的元素，其類型為DataType，該操作返回一個(gè)函數(shù)值，表示入棧操作是否執(zhí)行成功。操作的功能為：在指定的棧*S中插入元素x，并使x成為棧頂。若棧S不滿，則從棧頂插入x并返回函數(shù)值1，否則棧的狀態(tài)不變且返回函數(shù)值0。處理過(guò)程為：判定是否棧滿，若棧滿，則返回0；否則，棧頂指針加1，將x送入棧頂并返回1。

15第3章棧

程序如下：intStackPush(SeqStack*S,DataTypex)/*把數(shù)據(jù)元素值x壓入順序堆棧S，入棧成功則返回1，否則返回0*/{if(S->top>=MaxStackSize-1){printf("堆棧已滿無(wú)法插入!\n");return0;}else{S->top++;S->stack[S->top]=x;return1;}}16第3章棧

2.出棧操作

順序棧的出棧操作可表示為：

intStackPop(SeqStack*S,DataType*d)；其中，參數(shù)S表示指定的棧，其類型為順序棧類型SeqStack，該操作是一個(gè)函數(shù)，彈出順序堆棧S的棧頂數(shù)據(jù)元素值到參數(shù)d。操作的功能為：若指定的棧S非空，則從S中取出棧頂元素到參數(shù)d，否則返回0。處理過(guò)程為：判定棧是否為空棧。若為空棧，則返回0；否則，棧頂數(shù)據(jù)元素值到參數(shù)d，棧頂指針減1，返回1。17第3章棧

程序如下：intStackPop(SeqStack*S,DataType*d)/*彈出順序堆棧S的棧頂數(shù)據(jù)元素值到參數(shù)d，出棧成功則返回1，否則返回0*/{if(S->top==-1){printf("堆棧已空無(wú)數(shù)據(jù)元素出棧!\n");return0;}else{*d=S->stack[S->top];S->top--;return1;}}18第3章棧

3.取棧頂操作順序棧的取棧頂操作可表示為：

intStackTop(SeqStackS,DataType*d)；其中，參數(shù)S表示指定的棧，其類型為順序棧類型SeqStack，該操作是一個(gè)函數(shù)，彈出順序堆棧S的棧頂數(shù)據(jù)元素值到參數(shù)d。操作的功能為：若指定的棧S非空，則從S中取出棧頂元素到參數(shù)d，否則返回0。處理過(guò)程為：判定棧是否為空棧。若為空棧，則返回0；否則，棧頂數(shù)據(jù)元素值到參數(shù)d，返回1。19第3章棧

程序如下：intStackTop(SeqStackS,DataType*d)/*取順序堆棧S的當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù)d，成功則返回1，否則返回0*/{if(S.top==-1){printf("堆棧已空!\n");return0;}else{*d=S.stack[S.top];return1;}}20第3章棧

3.3.2鏈棧的操作實(shí)現(xiàn)下面討論在鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)方式下，入棧及出棧等操作的實(shí)現(xiàn)。

1.入棧操作鏈棧入棧操作的含義是：將一個(gè)元素壓入指定的鏈棧中。對(duì)該操作應(yīng)設(shè)置兩個(gè)參數(shù)，即在參數(shù)中指定一個(gè)鏈棧及入棧的元素。假設(shè)指定的鏈棧LSNode*top在本操作之外已說(shuō)明，而入棧元素x其類型為DataType，入棧操作取名為StackPush，則該操作可表示為：

intStackPush(LSNode*top,DataTypex)

操作的功能為：在由top指向的鏈棧中插入元素x，使x成為棧頂元素。處理過(guò)程為：⑴生成一個(gè)新的結(jié)點(diǎn)，并令其元素值為x。⑵將該結(jié)點(diǎn)從棧頂插入到鏈棧中。21第3章棧

程序如下：intStackPush(LSNode*top,DataTypex)/*把數(shù)據(jù)元素x插入鏈?zhǔn)蕉褩op的棧頂作為新的棧頂*/{LSNode*p;if((p=(LSNode*)malloc(sizeof(LSNode)))==NULL){printf("內(nèi)存空間不足無(wú)法插入!\n");return0;}p->data=x;p->next=top;/*新結(jié)點(diǎn)鏈入棧頂*/top=p;/*新結(jié)點(diǎn)成為新的棧頂*/return1;}22第3章棧

2.出棧操作鏈棧出棧操作的含義是：從鏈棧中彈出棧頂結(jié)點(diǎn)并返回該結(jié)點(diǎn)中的元素值。對(duì)該操作應(yīng)設(shè)置兩個(gè)參數(shù)，即在參數(shù)中指定一個(gè)鏈棧。假設(shè)指定的鏈棧LSNode*top在本操作之外已說(shuō)明，彈出結(jié)點(diǎn)元素值d。出棧操作取名為StackPop，則該操作可表示為：

intStackPop(LSNode*top,DataType*d)；操作的功能為：從由top指向的鏈棧中彈出棧頂結(jié)點(diǎn)并把棧頂元素由參數(shù)d帶回。處理過(guò)程為：⑴判定鏈棧是否為空。若為空棧，則返回0。⑵保存棧頂結(jié)點(diǎn)的元素值為*d，并修改棧頂指針使之指向其后繼。⑶返回1。23第3章棧

程序如下：intStackPop(LSNode*top，DataType*d)/*出棧并把棧頂元素由參數(shù)d帶回*/{LSNode*p;if(top==NULL){printf("堆棧已空出錯(cuò)！");return0;}p=top;top=p->next;/*刪除原棧頂結(jié)點(diǎn)*/*d=p->data;/*原棧頂結(jié)點(diǎn)元素賦予d*/free(p);/*釋放原棧頂結(jié)點(diǎn)內(nèi)存空間*/return1;}24第3章棧

3.取棧頂操作鏈棧取棧頂操作的含義是：返回鏈棧中棧頂結(jié)點(diǎn)中的元素值。對(duì)該操作應(yīng)設(shè)置兩個(gè)參數(shù)，即在參數(shù)中指定一個(gè)鏈棧。假設(shè)指定的鏈棧LSNode*top在本操作之外已說(shuō)明，結(jié)點(diǎn)元素值d。出棧操作取名為StackTop，則該操作可表示為：

intStackTop(LSNode*top,DataType*d)；操作的功能：為返回由top指向的鏈棧中棧頂結(jié)點(diǎn)中的元素值。處理過(guò)程為：⑴判定鏈棧top是否為空。若為空棧，則返回0。⑵保存棧頂結(jié)點(diǎn)的元素值為*d。⑶返回1。25第3章棧

程序如下：intStackTop(LSNode*top,DataType*d)/*取棧頂元素并把棧頂元素由參數(shù)d帶回*/{LSNode*p;if(top==NULL){printf("堆棧已空出錯(cuò)！");return0;}*d=top->data;return1;}26第3章棧

3.4棧的ADT定義

以上我們討論了棧的結(jié)構(gòu)特征、存儲(chǔ)方式及其相關(guān)操作的實(shí)現(xiàn)。為以后面向?qū)ο蟪绦蛟O(shè)計(jì)中的類定義奠定基礎(chǔ)。在本節(jié)中我們將給出棧的ADT定義即抽象數(shù)據(jù)類型定義。

ADT定義，即抽象數(shù)據(jù)類型定義。一種數(shù)據(jù)類型的ADT定義由數(shù)據(jù)元素、結(jié)構(gòu)及操作三部分組成。以下是棧的ADT定義：元素：可以是各種類型的數(shù)據(jù)，但必須同屬于一個(gè)數(shù)據(jù)對(duì)象。結(jié)構(gòu)：棧中的n個(gè)元素呈線性關(guān)系。27第3章棧

對(duì)?？蓤?zhí)行以下的基本操作：

⑴StackInitiate(S)，初始化操作。它可設(shè)定一個(gè)空的棧S。⑵StackSize(S)：求長(zhǎng)度函數(shù)。函數(shù)值為給定棧S中數(shù)據(jù)元素的個(gè)數(shù)。⑶StackNotEmpty(S)：判空棧函數(shù)。若S為非空棧，則返回1，否則返回0。⑷StackClear(S)：棧清空操作。操作的結(jié)果使S成為空棧。⑸StackPush(S，x)：入棧操作。該操作可將x推入棧S中。若S非空，則插入元素x為插入前棧頂元素的后繼(即x為插入后的棧頂元素)，否則插入元素為棧中的第1個(gè)元素即棧頂元素。⑹StackPop(S)：出棧函數(shù)。若棧S非空，則返回函數(shù)值為棧頂元素，且從棧中刪除棧頂元素，否則返回函數(shù)值為空元素NULL。⑺StackTop(S)：取棧頂函數(shù)。若棧S非空，則返回函數(shù)值為棧頂元素，否則返回函數(shù)值為0。數(shù)據(jù)類型的ADT定義提供了接口描述，但對(duì)某一種數(shù)據(jù)類型，需考慮具體的存儲(chǔ)方式及其實(shí)現(xiàn)方法。數(shù)據(jù)的存儲(chǔ)方式不同，其操作的實(shí)現(xiàn)方法也就不同。28第3章棧

3.5棧的應(yīng)用實(shí)例-算術(shù)表達(dá)式的求值

3.5.1表達(dá)式的構(gòu)成任一表達(dá)式都可看成是由操作數(shù)，運(yùn)算符和界限符組成的一個(gè)串。其中，操作數(shù)可以是常數(shù)也可以是變量或常量的標(biāo)識(shí)符，運(yùn)算符可以是算術(shù)運(yùn)算符，關(guān)系運(yùn)算符和邏輯運(yùn)算符等，界限符包括左右括號(hào)和表達(dá)式結(jié)束符等，例表達(dá)式7+4*（8-3）。為論述方便，這里僅介紹簡(jiǎn)單算術(shù)表達(dá)式的求值問(wèn)題。29第3章棧

3.5.2運(yùn)算符的優(yōu)先關(guān)系要對(duì)表達(dá)式正確求值，必須正確的解釋表達(dá)式，將其翻譯成正確的機(jī)器指令序列。例如，要對(duì)表達(dá)式3*（7-2）求值，首先要了解算術(shù)運(yùn)算的規(guī)則。即1．從左到右；2．先括號(hào)內(nèi)，后括號(hào)外；3．先乘除，后加減；故，該表達(dá)式的計(jì)算步驟應(yīng)為3*（7-2）=3*5=15。30第3章棧

表3.1算符優(yōu)先級(jí)表

表中空白表示運(yùn)算符p1,p2不可能相遇的情況，若相遇則表明出現(xiàn)了語(yǔ)法錯(cuò)誤?！?”是表達(dá)式的結(jié)束符，為算法方便在表達(dá)式的左邊也虛設(shè)一個(gè)“#”使其配對(duì)。這樣，當(dāng)“（”=“）”時(shí)表示左右括號(hào)相遇，括號(hào)內(nèi)運(yùn)算已經(jīng)結(jié)束；同理，當(dāng)“#”=“#”時(shí)表示整個(gè)表達(dá)式求值完畢。

+-*/（）#+＞＞＜＜＜＞＞-＞＞＜＜＜＞＞*＞＞＞＞＜＞＞/＞＞＞＞＜＞＞（＜＜＜＜＜=

）＞＞＞＞

＞＞#＜＜＜＜＜

=p2p131第3章棧

3.5.3算法思路使用兩個(gè)棧S1和S2，其中，S1為運(yùn)算符棧，用以寄存運(yùn)算符，而S2為操作數(shù)棧，用以寄存操作數(shù)或運(yùn)算結(jié)果。其算法思路如下，⑴首先設(shè)置兩棧為空，將“#”作為表達(dá)式起始符壓入運(yùn)算符棧S1作為棧底元素；⑵依次讀入表達(dá)式的每個(gè)字符，若是操作數(shù)則進(jìn)入操作數(shù)棧S2；若是運(yùn)算符，則與S1的棧頂運(yùn)算符比較優(yōu)先級(jí)，若棧頂運(yùn)算符優(yōu)先級(jí)低，則進(jìn)入棧S1，若棧頂運(yùn)算符優(yōu)先級(jí)高，則彈出S1的棧頂運(yùn)算符，并從棧S2中彈出兩個(gè)操作數(shù)，作相應(yīng)運(yùn)算后，將結(jié)果壓入操作數(shù)棧S2，然后再次與S1的棧頂運(yùn)算符比較優(yōu)先級(jí)，直至棧頂運(yùn)算符優(yōu)先級(jí)低為止。⑶當(dāng)S1的棧頂運(yùn)算符為“#”時(shí)，表達(dá)式求值結(jié)束，操作數(shù)棧S2中的數(shù)即為表達(dá)式的值。32第3章棧

步驟操作符棧（S1）操作數(shù)棧（S2）讀入字符主要操作1#

3*（7-2）#PUSH(S2,‘3’)2#3*（7-2）#PUSH(S1，‘*’)3#*3（7-2）#PUSH(S1,‘(’)4#*（37-2）#PUSH(S2,‘7’)5#*（37-2）#PUSH(S1,‘-’)6#*（-372）#PUSH(S2,‘2’)7#*（-372）#Operate(‘7’,‘-’,‘2’)8#*（35）#POP(S1)消去一對(duì)括號(hào)9#*35#Operate(‘3’,‘*’,‘5’)10#15#Return(GetTop(s2))表3.2求表達(dá)式3*(7-2)時(shí)的棧變化

33第3章棧

3.6上機(jī)實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康模和ㄟ^(guò)上機(jī)實(shí)驗(yàn)，熟悉棧的各種存儲(chǔ)結(jié)構(gòu)，鍛煉學(xué)生應(yīng)用棧的知識(shí)解決實(shí)際問(wèn)題的能力實(shí)驗(yàn)要求：1.完成自己的棧頭文件2.完成后附范例的上機(jī)驗(yàn)證3.模仿實(shí)例，完成其它算法4.完成實(shí)驗(yàn)報(bào)告34第3章棧

實(shí)驗(yàn)步驟1.逐步完成自己的順序存儲(chǔ)的棧頭文件（1）編寫頭文件（2）編寫驗(yàn)證主函數(shù)（3）上機(jī)調(diào)試程序，上機(jī)驗(yàn)證2.逐步完成自己的鏈?zhǔn)酱鎯?chǔ)的棧頭文件（1）編寫頭文件（2）編寫驗(yàn)證主函數(shù)（3）上機(jī)調(diào)試程序，上機(jī)驗(yàn)證3.完成應(yīng)用實(shí)例程序4.撰寫實(shí)驗(yàn)報(bào)告35第3章棧

范例#defineMaxStackSize50typedefcharDataType;typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack;voidStackInitiate(SeqStack*S) /*初始化順序堆棧S*/{S->top=-1;/*定義初始棧頂下標(biāo)值*/}intStackNotEmpty(SeqStackS)/*判順序堆棧S非空否，非空則返回1，否則返回0*/{if(S.top<0) return0;elsereturn1;}36第3章棧

intStackPush(SeqStack*S,DataTypex)/*把數(shù)據(jù)元素值x壓入順序堆棧S，入棧成功則返回1，否則返回0*/{if(S->top>=MaxStackSize-1){printf("堆棧已滿無(wú)法插入!\n");return0;}else{S->top++;S->stack[S->top]=x;return1;}}37第3章棧

intStackPop(SeqStack*S,DataType*d)/*彈出順序堆棧S的棧頂數(shù)據(jù)元素值到參數(shù)d，出棧成功則返回1，否則返回0*/{if(S->top<0){printf("堆棧已空無(wú)數(shù)據(jù)元素出棧!\n");return0;}else{*d=S->stack[S->top];S->top--;return1;}}38第3章棧

intStackTop(SeqStackS,DataType*d)/*取順序堆棧S的當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù)d，成功則返回1，否則返回0*/{if(S.top<0){printf("堆棧已空!\n");return0;}else{*d=S.stack[S.top-1];return1;}}39第3章棧

voidmain(void){SeqStackst;chara[]={'s','t','a','c','k','!'},x;inti;

for(i=0;i<6;i++)printf("\n%c\n",a[i]);/*輸出壓入序列*/StackInitiate(&st);/*初始化*/for(i=0;i<6;i++){if(StackPush(&st,a[i])==0) /*入棧數(shù)據(jù)元素*/{printf("錯(cuò)誤!\n");return;}}40第3章棧

if(StackTop(st,&x)==0) /*取棧頂數(shù)據(jù)元素*/{printf("錯(cuò)誤!\n");return;}elseprintf("%c\n",x);

printf("依次出棧的數(shù)據(jù)元素序列如下：\n");while(StackNotEmpty(st)!=0){StackPop(&st,&x);/*出棧*/printf("%c",x);/*顯示數(shù)據(jù)元素*/}}41第3章棧

本章小結(jié)本章主要討論棧的邏輯結(jié)構(gòu)和物理存儲(chǔ)結(jié)構(gòu)以及各種存儲(chǔ)結(jié)構(gòu)下的算法實(shí)現(xiàn)。在后續(xù)學(xué)習(xí)中要廣泛的應(yīng)用。其主要內(nèi)容包括：

1.基本概念和術(shù)語(yǔ)①棧（stack）是由n個(gè)元素組成的有限序列，可記作：

S=(a1，a2，…，ai，…，an)

其中，每個(gè)ai都是棧S的數(shù)據(jù)元素，數(shù)據(jù)元素可以是各種類型，但必須屬于同一種數(shù)據(jù)對(duì)象。其數(shù)據(jù)元素之間呈線性關(guān)系，操作的特點(diǎn)是“后進(jìn)先出”，主要操作有進(jìn)棧、出棧和取棧頂元素等。②棧（stack）是限定只能在表的一端進(jìn)行操作的線性表。在表中允許插入和刪除的一端叫做棧頂(top)，而不允許插入和刪除的另一端叫做棧底(bottom)，向棧頂插入一個(gè)元素的操作叫做入棧(push)操作，從棧頂取出一個(gè)元素的操作叫做出棧(pop)操作。42第3章棧

2.棧的存儲(chǔ)結(jié)構(gòu)⑴順序存儲(chǔ)結(jié)構(gòu)MaxStackSize=棧中允許存放元素個(gè)數(shù)的最大值，順序棧的類型定義如下：typedefstruct{DataTypestack[MaxStackSize];inttop;}SeqStack;⑵鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈棧類型LSNode可定義如下：typedefstructsnode{DataTypedata;structsnode*next;}LSNode;43第3章棧

3.棧的有關(guān)操作對(duì)?？蓤?zhí)行以下的基本操作：；⑴StackInitiate(S)，初始化操作。它可設(shè)定一個(gè)空的棧S。⑵StackSize(S)：求長(zhǎng)度函數(shù)。函數(shù)值為給定棧S中數(shù)據(jù)元素的個(gè)數(shù)。⑶StackNotEmpty(S)：判空棧函數(shù)。若S為非空棧，則返回1，否則返回0。⑷StackClear(S)：棧清空操作。操作的結(jié)果使S成為空棧。⑸StackPush(S，x)：入棧操作。該操作可將x推入棧S中。若S非空，則插入元素x為插入前棧頂元素的后繼(即x為插入后的棧頂元素)，否則插入元素為棧中的第1個(gè)元素即棧頂元素。⑹StackPop(S)：出棧函數(shù)。若棧S非空，則返回函數(shù)值為棧頂元素，且從棧中刪除棧頂元素，否則返回函數(shù)值為空元素NULL。⑺StackTop(S)：取棧頂函數(shù)。若棧S非空，則返回函數(shù)值為棧頂元素，否則返回函數(shù)值為0。44第3章棧

習(xí)題一、填空題

1.向量(線性表)、棧都是

結(jié)構(gòu)，可以在向量的

位置插入和刪除元素；對(duì)于棧只能在

插入和刪除元素。

2.棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為

。不允許插入和刪除運(yùn)算的一端稱為

。

3.向棧中壓入元素的操作是先

，后

。

4.棧是一種線性表，它的特點(diǎn)是

。設(shè)用一維數(shù)組A[0,…,n-1]來(lái)表示一個(gè)棧，A[-1]為棧底，用整型變量top指示當(dāng)前棧頂位置，A[top]為棧頂元素。往棧中壓入（push）一個(gè)新元素時(shí)，變量top的值

；從棧中彈出（pop）一個(gè)元素時(shí)，變量top的值

。設(shè)?？諘r(shí)，有輸入序列a，b，c，經(jīng)過(guò)push，pop，push，push，pop操作后，從棧中彈出的元素的序列是

，變量top的值是

。

5.在做入棧運(yùn)算時(shí)，應(yīng)先判別棧是否

；在做出棧運(yùn)算時(shí)，應(yīng)先判別棧是否