第3章堆棧和隊列主要知識點堆棧堆棧應用隊列優先級隊列11.

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

堆棧2圖3-1火車調度模型（a）車軌設置（b）駛入（c）駛出堆棧的功能和火車調度裝置的功能類同，如圖3-1所示：3堆棧的基本概念（續）與線性表相同，仍為一對一(1:1)關系。用順序棧或鏈棧存儲均可，但以順序棧更常見只能在棧頂運算，且訪問結點時依照后進先出（LIFO）或先進后出（FILO）的原則。關鍵是編寫入棧和出棧函數，具體實現依順序棧或鏈棧的存儲結構有別而不同。3.存儲結構4.運算規則5.實現方式

2.邏輯結構基本操作有：建棧、判斷棧滿或棧空、入棧、出棧、讀棧頂元素值等等。4棧是僅在表尾進行插入、刪除操作的線性表。表尾(即an端)稱為棧頂

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

)插入元素到棧頂的操作，稱為入棧。從棧頂刪除最后一個元素的操作，稱為出棧。an稱為棧頂元素a0稱為棧底元素強調：插入和刪除都只能在表的一端（棧頂）進行！注：堆棧可以完成比較復雜的數據元素特定序列的轉換任務，但它不能完成任何輸入輸出序列的轉換任務。5例1：堆棧是什么？它與一般線性表有什么不同？堆棧是一種特殊的線性表，它只能在表的一端（即棧頂）進行插入和刪除運算。與一般線性表的區別：僅在于運算規則不同。一般線性表堆棧邏輯結構：1:1邏輯結構：1:1存儲結構：順序表、鏈表存儲結構：順序棧、鏈棧運算規則：隨機存取

運算規則：后進先出(LIFO)“進”＝插入=壓入“出”＝刪除=彈出6例2一個棧的輸入序列為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；合計有5種可能性。7例3一個棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實現嗎？12345的輸出呢？解：

43512不可能實現，主要是其中的12順序不能實現；

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

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

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

9三、堆棧的順序表示和實現1、順序（堆）棧順序存儲結構的堆棧。2、順序棧的存儲結構

它是利用一組地址連續的存儲單元依次存放自棧底到棧頂的數據元素，同時設指針top指示當前棧頂位置。a0a1……an-1順序棧S

ai……棧底棧頂top10存儲結構示意圖如下圖所示：

其中：stack：為順序堆棧存放數據元素的數組；MaxStackSize：為stack的最大存儲單元個數；top：為堆棧的當前棧頂位置。用C語言定義為：typedef

struct{DataTypestack[MaxStackSize];

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

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

ai……問：順序表和順序棧的操作有何區別？表頭表尾低地址高地址寫入：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前提：一定要預設棧頂指針top棧頂top12棧為空的條件：top=0;棧滿的條件：top=MaxStackSize;a0a1……an-1順序棧S

ai……低地址高地址an棧底base棧頂top入棧口訣：堆棧指針top“先壓后加”:S[top++]=an出棧口訣：堆棧指針top“先減后彈”:e=S[--top]13問：為什么要設計堆棧？它有什么獨特用途？調用函數或子程序非它莫屬；遞歸運算的有力工具；用于保護現場和恢復現場；簡化了程序設計的問題。下面用例子來幫助理解堆棧：14voidtest(int*sum){intx;scanf(“%d”,&x);if(x==0)sum=0;else{test(sum);sum+=x;}printf(sum);}斷點地址入棧例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注意：最先輸入的數據

x1

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

int

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

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

StackPush(SeqStack*S,DataTypex)/*把數據元素值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的棧頂數據元素值到參數d，出棧成功則返回1，否則返回0*/{ if(S->top<=0) { printf("堆棧已空無數據元素出棧!\n"); return0; } else { S->top--;*d=S->stack[S->top]; return1; }}19(5)取棧頂數據元素int

StackTop(SeqStackS,DataType*d)/*取順序堆棧S的當前棧頂數據元素值到參數d，成功則返回1，否則返回0*/{if(S.top<=0) { printf("堆棧已空!\n"); return0; } else{ *d=S.stack[S.top-1];return1; }}20例：用堆棧存放（A，B，C，D）AACBABAtop

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

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

#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\n",x);

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

printf("%d",x); } }輸出結果如下：當前棧頂數據元素為：10依次出棧的數據元素序列如下：1098765432124四、堆棧的鏈式表示和實現1、鏈棧的存儲結構

以頭指針為棧頂，在頭指針處插入或刪除.棧頂棧底棧也可以用鏈式結構來表示，用鏈式結構來表示的棧就是鏈棧ha0a1an-2an-1nextdata鏈棧中每個結點由兩個域構成：data域和next域，其定義為：typedef

struct

snode{DataTypedata;

structsnode*next;}LSNode;252、鏈式堆棧的操作實現 （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; /*新結點鏈入棧頂*/

head->next=p;

/*新結點成為新的棧頂*/}27(4)出棧int

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

return0; }

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

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

StackTop(LSNode*head,DataType*d){

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

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

return0; }

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

LSNode*p,*p1;

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

30在鏈棧中的頭結點對操作的實現影響不大，棧頂（表頭）操作頻繁，可不設頭結點鏈棧。一般不會出現棧滿情況；除非沒有空間導致malloc分配失敗。鏈棧的入棧、出棧操作就是棧頂的插入與刪除操作，修改指針即可完成。幾點說明:311.括號匹配問題（書P55）

假設一個算法表達式中包含圓括號、方括號和花括號三種類型的括號，編寫一個判別表達式中括號是否正確配對的函數，并設計一個測試主函數。

設計思路：用棧暫存左括號括號匹配有四種情況：（1）左右括號配對次序不正確；（2）右括號多于左括號；（3）左括號多于右括號；（4）左右括號匹配正確。3.2堆棧應用32voidExpIsCorrect(charexp[],intn)//判斷有n個字符的字符串exp左右括號是否配對正確{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("左右括號配對次序不正確！\n"); return;}elseif(exp[i]==']'&&StackNotEmpty(myStack) &&StackTop(myStack,&c)&&c=='[')

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

StackPop(&myStack,&c);

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

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

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

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

其運算次序為：T1=CD/；T2=BT1-；

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