數(shù)據(jù)結(jié)構(gòu)第03章

第3章堆棧和隊(duì)列主要知識(shí)點(diǎn)堆棧堆棧應(yīng)用隊(duì)列優(yōu)先級(jí)隊(duì)列11.

定義一、堆棧的基本概念是一種特殊的線性表，限定只能在表的一端進(jìn)行插入和刪除操作的線性表。特點(diǎn)：后進(jìn)先出。棧頂和棧底：堆棧中允許進(jìn)行插入和刪除操作的一端稱為棧頂，另一端稱為棧底。3.1

堆棧2圖3-1火車調(diào)度模型（a）車軌設(shè)置（b）駛?cè)耄╟）駛出堆棧的功能和火車調(diào)度裝置的功能類同，如圖3-1所示：3堆棧的基本概念（續(xù)）與線性表相同，仍為一對(duì)一(1:1)關(guān)系。用順序棧或鏈棧存儲(chǔ)均可，但以順序棧更常見只能在棧頂運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照后進(jìn)先出（LIFO）或先進(jìn)后出（FILO）的原則。關(guān)鍵是編寫入棧和出棧函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。3.存儲(chǔ)結(jié)構(gòu)4.運(yùn)算規(guī)則5.實(shí)現(xiàn)方式

2.邏輯結(jié)構(gòu)基本操作有：建棧、判斷棧滿或?？铡⑷霔?、出棧、讀棧頂元素值等等。4棧是僅在表尾進(jìn)行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

/top;表頭(即a1端)稱為棧底/base例如：棧S=(a０,a2,a3,……….,an-1,an

)插入元素到棧頂?shù)牟僮?，稱為入棧。從棧頂刪除最后一個(gè)元素的操作，稱為出棧。an稱為棧頂元素a0稱為棧底元素強(qiáng)調(diào)：插入和刪除都只能在表的一端（棧頂）進(jìn)行！注：堆棧可以完成比較復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。5例1：堆棧是什么？它與一般線性表有什么不同？堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進(jìn)行插入和刪除運(yùn)算。與一般線性表的區(qū)別：僅在于運(yùn)算規(guī)則不同。一般線性表堆棧邏輯結(jié)構(gòu)：1:1邏輯結(jié)構(gòu)：1:1存儲(chǔ)結(jié)構(gòu)：順序表、鏈表存儲(chǔ)結(jié)構(gòu)：順序棧、鏈棧運(yùn)算規(guī)則：隨機(jī)存取

運(yùn)算規(guī)則：后進(jìn)先出(LIFO)“進(jìn)”＝插入=壓入“出”＝刪除=彈出6例2一個(gè)棧的輸入序列為1,2,3，若在入棧的過程中允許出棧，則可能得到的出棧序列是什么？解：可以通過窮舉所有可能性來求解：①1入1出，2入2出，3入3出，即123；②1入1出，2、3入，3、2出，即132；③1、2入，2出，3入3出，即231；④1、2入，2、1出，3入3出，即213；⑤1、2、3入，3、2、1出，即321；合計(jì)有5種可能性。7例3一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？解：

43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；

12345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。8二、堆棧抽象數(shù)據(jù)類型數(shù)據(jù)集合：{a0,a1,…,an-1｝

ai的數(shù)據(jù)類型為DataType操作集合：(1)StackInitiate(S)初始化堆棧S(2)StackNotEmpty(S)堆棧S非空否

(3)StackPush(S,x)入棧(4)StackPop(S,d)出棧(5)StackTop(S,d)取棧頂數(shù)據(jù)元素

9三、堆棧的順序表示和實(shí)現(xiàn)1、順序（堆）棧順序存儲(chǔ)結(jié)構(gòu)的堆棧。2、順序棧的存儲(chǔ)結(jié)構(gòu)

它是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)設(shè)指針top指示當(dāng)前棧頂位置。a0a1……an-1順序棧S

ai……棧底棧頂top10存儲(chǔ)結(jié)構(gòu)示意圖如下圖所示：

其中：stack：為順序堆棧存放數(shù)據(jù)元素的數(shù)組；MaxStackSize：為stack的最大存儲(chǔ)單元個(gè)數(shù)；top：為堆棧的當(dāng)前棧頂位置。用C語言定義為：typedef

struct{DataTypestack[MaxStackSize];

inttop;}SeqStack;…a4a3a2a1a001234Top=5棧頂棧底Stack

MaxStackSize-111a0a1……an-1順序棧S

ai……問：順序表和順序棧的操作有何區(qū)別？表頭表尾低地址高地址寫入：S[i]=ai讀出：e=S[i]壓入(PUSH):S[top++]=an彈出(POP):e=S[--top]低地址高地址S[i]a0a1

aian-1

……順序表S

……

an以線性表S=(a0,a1,….,an-2,an-1)為例棧底base棧頂top前提：一定要預(yù)設(shè)棧頂指針top棧頂top12棧為空的條件：top=0;棧滿的條件：top=MaxStackSize;a0a1……an-1順序棧S

ai……低地址高地址an棧底base棧頂top入?？谠E：堆棧指針top“先壓后加”:S[top++]=an出?？谠E：堆棧指針top“先減后彈”:e=S[--top]13問：為什么要設(shè)計(jì)堆棧？它有什么獨(dú)特用途？調(diào)用函數(shù)或子程序非它莫屬；遞歸運(yùn)算的有力工具；用于保護(hù)現(xiàn)場和恢復(fù)現(xiàn)場；簡化了程序設(shè)計(jì)的問題。下面用例子來幫助理解堆棧：14voidtest(int*sum){intx;scanf(“%d”,&x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}斷點(diǎn)地址入棧例1

閱讀下列遞歸過程，說明其功能。輸入x1≠0輸入x5＝0輸入x2輸入x3輸入x4輸出sum＝0輸出sum＝0+x4輸出sum＝x4+x3輸出sum＝x4+x3+x2輸出sum＝x4+x3+x2+x1注意：最先輸入的數(shù)據(jù)

x1

最后才被累加程序功能：對(duì)鍵盤輸入數(shù)據(jù)求和，直到輸入0結(jié)束153、順序棧的操作實(shí)現(xiàn)(1)初始化棧voidStackInitiate(SeqStack*S) /*初始化順序堆棧S*/{ S->top=0; /*定義初始棧頂下標(biāo)值*/ }16(2)判棧非空否

int

StackNotEmpty(SeqStackS)/*判順序堆棧S非空否，非空則返回1，否則返回0*/{

if(S.top<=0) return0; elsereturn1;}17(3)入棧int

StackPush(SeqStack*S,DataTypex)/*把數(shù)據(jù)元素值x壓入順序堆棧S，入棧成功則返回1，否則返回0*/{ if(S->top>=MaxStackSize) {

printf("堆棧已滿無法插入!\n"); return0; } else{ S->stack[S->top]=x; S->top++;return1;}}18(4)出棧int

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

StackTop(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; }}20例：用堆棧存放（A，B，C，D）AACBABAtop

順序棧入棧函數(shù)的核心語句：S->stack[S->top]=x; S->top++;toptoptoptop低地址L高地址MBCD21例：從棧中取出‘B’DCBAtoptopDCABDCBAtopDCBAtop低地址L高地址MD順序棧出棧函數(shù)的核心語句：S->top--;*d=S->stack[S->top];注：DataType*d；

SeqStack*S；22測試主程序：任務(wù)：建立一個(gè)順序堆棧，首先依次輸入數(shù)據(jù)元素1,2,3,......,10，然后依次出棧堆棧中的數(shù)據(jù)元素并顯示。假設(shè)該順序堆棧的數(shù)據(jù)元素個(gè)數(shù)在最壞情況下不會(huì)超過100個(gè)。

#include<stdio.h>#defineMaxStackSize100 typedef

int

DataType; #include"SeqStack.h" voidmain(void){

SeqStack

myStack;

inti,x;23

StackInitiate(&myStack); for(i=0;i<10;i++)

StackPush(&myStack,i+1)

StackTop(myStack,&x)

printf("當(dāng)前棧頂數(shù)據(jù)元素為：%d\n",x);

printf("依次出棧的數(shù)據(jù)元素序列如下：\n"); while(StackNotEmpty(myStack)) { StackPop(&myStack,&x);

printf("%d",x); } }輸出結(jié)果如下：當(dāng)前棧頂數(shù)據(jù)元素為：10依次出棧的數(shù)據(jù)元素序列如下：1098765432124四、堆棧的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)1、鏈棧的存儲(chǔ)結(jié)構(gòu)

以頭指針為棧頂，在頭指針處插入或刪除.棧頂棧底棧也可以用鏈?zhǔn)浇Y(jié)構(gòu)來表示，用鏈?zhǔn)浇Y(jié)構(gòu)來表示的棧就是鏈棧ha0a1an-2an-1nextdata鏈棧中每個(gè)結(jié)點(diǎn)由兩個(gè)域構(gòu)成：data域和next域，其定義為：typedef

struct

snode{DataTypedata;

structsnode*next;}LSNode;252、鏈?zhǔn)蕉褩５牟僮鲗?shí)現(xiàn) （1）初始化StackInitiate(head)voidStackInitiate(LSNode**head){ *head=(LSNode*)malloc(sizeof(LSNode)); (*head)->next=NULL;}（2）非空否StackNotEmpty(head)int

StackNotEmpty(LSNode*head){ if(head->next==NULL)return0; elsereturn1;}26(3)入棧voidStackPush(LSNode*head,DataTypex){LSNode*p; p=(LSNode*)malloc(sizeof(LSNode)))p->data=x;

p->next=head->next; /*新結(jié)點(diǎn)鏈入棧頂*/

head->next=p;

/*新結(jié)點(diǎn)成為新的棧頂*/}27(4)出棧int

StackPop(LSNode*head,DataType*d){ LSNode*p=head->next; if(p==NULL) { printf("堆棧已空出錯(cuò)！");

return0; }

head->next=p->next; /*刪除原棧頂結(jié)點(diǎn)*/ *d=p->data; /*原棧頂結(jié)點(diǎn)元素賦予d*/ free(p); /*釋放原棧頂結(jié)點(diǎn)內(nèi)存空間*/

return1;}28（5）取棧頂數(shù)據(jù)元素StackTop(head,d)int

StackTop(LSNode*head,DataType*d){

LSNode*p=head->next; if(p==NULL) {

printf("堆棧已空出錯(cuò)！");

return0; }

*d=p->data; return1;}29（6）撤消動(dòng)態(tài)申請空間Destroy(*head)voidDestroy(LSNode*head){

LSNode*p,*p1;

p=head; while(p!=NULL) { p1=p; p=p->next; free(p1); }}

30在鏈棧中的頭結(jié)點(diǎn)對(duì)操作的實(shí)現(xiàn)影響不大，棧頂（表頭）操作頻繁，可不設(shè)頭結(jié)點(diǎn)鏈棧。一般不會(huì)出現(xiàn)棧滿情況；除非沒有空間導(dǎo)致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂?shù)牟迦肱c刪除操作，修改指針即可完成。幾點(diǎn)說明:311.括號(hào)匹配問題（書P55）

假設(shè)一個(gè)算法表達(dá)式中包含圓括號(hào)、方括號(hào)和花括號(hào)三種類型的括號(hào)，編寫一個(gè)判別表達(dá)式中括號(hào)是否正確配對(duì)的函數(shù)，并設(shè)計(jì)一個(gè)測試主函數(shù)。

設(shè)計(jì)思路：用棧暫存左括號(hào)括號(hào)匹配有四種情況：（1）左右括號(hào)配對(duì)次序不正確；（2）右括號(hào)多于左括號(hào)；（3）左括號(hào)多于右括號(hào)；（4）左右括號(hào)匹配正確。3.2堆棧應(yīng)用32voidExpIsCorrect(charexp[],intn)//判斷有n個(gè)字符的字符串exp左右括號(hào)是否配對(duì)正確{SeqStack

myStack;

inti; charc;

StackInitiate(&myStack);for(i=0;i<n;i++){if((exp[i]=='(')||(exp[i]=='[')||(exp[i]=='{'))

StackPush(&myStack,exp[i]); elseif(exp[i]==')'&&StackNotEmpty(myStack)&&StackTop(myStack,&c)&&c=='(')

StackPop(&myStack,&c); 33elseif(exp[i]==')'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='('){printf("左右括號(hào)配對(duì)次序不正確！\n"); return;}elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='[')

StackPop(&myStack,&c); elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='['){printf("左右括號(hào)配對(duì)次序不正確！\n");return; }34elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='{')

StackPop(&myStack,&c);

elseif(exp[i]=='}'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c!='{'){printf("左右括號(hào)配對(duì)次序不正確！\n");return;}elseif(((exp[i]==')')||(exp[i]==']')||(exp[i]=='}'))&&!StackNotEmpty(myStack)){printf("右括號(hào)多于左括號(hào)！\n");return;}}

//for語句結(jié)束35if(StackNotEmpty(myStack))

printf("左括號(hào)多于右括號(hào)！\n");else

printf("左右括號(hào)匹配正確！\n");}362.表達(dá)式計(jì)算問題表達(dá)式計(jì)算是編譯系統(tǒng)中的基本問題，其實(shí)現(xiàn)方法是堆棧的一個(gè)典型應(yīng)用。在編譯系統(tǒng)中，要把便于人理解的表達(dá)式翻譯成能正確求值的機(jī)器指令序列，通常需要先把表達(dá)式變換成機(jī)器便于理解的形式，這就要變換表達(dá)式的表示序列。假設(shè)計(jì)算機(jī)高級(jí)語言中的一個(gè)算術(shù)表達(dá)式為:A+(B-C/D)*E這種表達(dá)式稱為中綴表達(dá)式，編譯系統(tǒng)對(duì)其處理的方法是轉(zhuǎn)成滿足四則運(yùn)算規(guī)則的相應(yīng)的后綴表達(dá)式即為:ABCD/-E*+

其運(yùn)算次序?yàn)椋篢1=CD/；T2=BT1-；

T3=T2E*；T4=AT3+。37后綴表達(dá)式的