第3章 棧與隊列1-棧

數(shù)據(jù)結(jié)構(gòu)講義

第3章棧和隊列

棧和隊列是兩種應(yīng)用非常廣泛的數(shù)據(jù)結(jié)構(gòu)，它們都來自線性表數(shù)據(jù)結(jié)構(gòu)，都是“操作受限”的線性表。

本章將討論棧和隊列的基本概念、存儲結(jié)構(gòu)、基本操作以及這些操作的具體實現(xiàn)。3.1.1

棧的基本概念棧(Stack)：限定僅在表尾進行插入或刪除操作的線性表。表尾—棧頂，表頭—棧底。特點：先進后出（FILO）或后進先出。ana1a2……...棧底棧頂...出棧進棧棧s=(a1,a2,……,an)1

棧的概念

棧(Stack)：是限制在表的一端進行插入和刪除操作的線性表。又稱為后進先出LIFO

(LastInFirstOut)或先進后出FILO

(FirstInLastOut)線性表。

棧頂(Top)：允許進行插入、刪除操作的一端，又稱為表尾。用棧頂指針(top)來指示棧頂元素。

棧底(Base)：是固定端，又稱為表頭。

空棧：當表中沒有元素時稱為空棧。

設(shè)棧S=(a1，a2，…an)，則a1稱為棧底元素，an為棧頂元素，如圖3-1所示。棧中元素按a1，a2，…an的次序進棧，退棧的第一個元素應(yīng)為棧頂元素。即棧的修改是按后進先出的原則進行的。圖3-1順序棧示意圖a1a2aian????basetop進棧（push）出棧(pop)2棧的抽象數(shù)據(jù)類型定義ADTStack{數(shù)據(jù)對象：D={ai|ai∈ElemSet,i=1,2,…,n，n≥0}數(shù)據(jù)關(guān)系：R={<ai-1,ai>|ai-1，ai∈D,i=2,3,…,n}基本操作：初始化、進棧、出棧、取棧頂元素等}ADTStack棧的基本操作1.初始化棧：INISTACK(&S)將棧S置為一個空棧(不含任何元素)。2.進棧：PUSH(&S,X)將元素X插入到棧S中，也稱為“入?！?、“插入”、“壓入”。3.出棧：POP(&S)刪除棧S中的棧頂元素，也稱為”退棧”、“刪除”、“彈出”。4.取棧頂元素：GETTOP(S,&e)取棧S中棧頂元素。5.判?？眨篠tackEmpty(S)判斷棧S是否為空，若為空，返回值為true，否則返回值為false。棧的順序存儲結(jié)構(gòu)簡稱為順序棧，和線性表相類似，用一維數(shù)組來存儲棧。根據(jù)數(shù)組是否可以根據(jù)需要增大，又可分為靜態(tài)順序棧和動態(tài)順序棧?！綮o態(tài)順序棧實現(xiàn)簡單，但不能根據(jù)需要增大棧的存儲空間；◆動態(tài)順序?？梢愿鶕?jù)需要增大棧的存儲空間，但實現(xiàn)稍為復雜。3.1.2

棧的順序存儲表示采用動態(tài)一維數(shù)組來存儲棧。所謂動態(tài)，指的是棧的大小可以根據(jù)需要增加?！粲胋ase表示棧底指針，棧底固定不變的；棧頂則隨著進棧和退棧操作而變化。用top(稱為棧頂指針)指示當前棧頂位置?！粲胻op=base作為?？盏臉擞?，每次top指向棧頂數(shù)組中的下一個存儲位置?！?/p>

結(jié)點進棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當前位置)，然后執(zhí)行top加1，使top指向棧頂?shù)南乱粋€存儲位置;3.1.2.1

棧的動態(tài)順序存儲表示◆結(jié)點出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲位置，然后將棧頂元素取出。圖3-2是一個動態(tài)棧的變化示意圖。圖3-2(動態(tài))堆棧變化示意圖空棧bottomtop元素a進棧bottomtopa元素b，c進棧bottomtopabc元素c退棧bottomtopabbottomtopabdef元素d，e，f進?；静僮鞯膶崿F(xiàn)1

棧的類型定義#defineSTACK_SIZE100/*棧初始向量大小*/#defineSTACKINCREMENT10/*存儲空間分配增量*/typedefintElemType;typedefstructsqstack{ElemType*base;/*棧不存在時值為NULL*/ElemType*top;/*棧頂指針*/intstacksize;/*當前已分配空間，以元素為單位*/}SqStack;2棧的初始化StatusInit_Stack(SqStack&S){;S.base=(ElemType*)malloc(STACK_SIZE*sizeof(ElemType));if(!S.base)returnERROR;S.top=S.base;/*?？諘r棧頂和棧底指針相同*/S.stacksize=STACK_SIZE;returnOK;}3壓棧(元素進棧)Statuspush(SqStackS,ElemTypee)

{if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc((S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType));/*棧滿，追加存儲空間*/if(!S.base)returnERROR;

S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top=e;S.top++;/*棧頂指針加1，e成為新的棧頂*/returnOK;}4

彈棧(元素出棧)Statuspop(SqStackS,ElemType*e)/*彈出棧頂元素*/{if(S.top==S.base)returnERROR;

/*?？?，返回失敗標志*/S.top--;e=*S.top;returnOK;}

1棧的鏈式表示

棧的鏈式存儲結(jié)構(gòu)稱為鏈棧，是運算受限的單鏈表。其插入和刪除操作只能在表頭位置上進行。棧頂指針top就是鏈表的頭指針圖3-4是棧的鏈式存儲表示形式。3.1.3

棧的鏈式存儲表示空棧top?非空棧topa4a3a1?a2圖3-4鏈棧存儲形式鏈棧的結(jié)點類型說明如下：typedefstructStack_Node{ElemTypedata;structStack_Node*next;}Stack_Node;2

鏈?；静僮鞯膶崿F(xiàn)(1)

棧的初始化statusInit_Link_Stack(Stack_Node*top){top=(Stack_Node*)malloc(sizeof(Stack_Node));If(top==null)returnerror;top->next=NULL;}鏈棧為空的條件：top->next=NULL

(2)壓棧(元素進棧)Statuspush(Stack_Node*top,ElemTypee){Stack_Node*p;p=(Stack_Node*)malloc(sizeof(Stack_Node));if(!p)returnERROR;/*申請新結(jié)點失敗，返回錯誤標志*/p->data=e;p->next=top->next;top->next=p;/*鉤鏈*/returnOK;}(3)

彈棧(元素出棧)Statuspop(Stack_Node*top,ElemType*e)/*將棧頂元素出棧*/{Stack_Node*p;ElemTypee;if(top->next==NULL)returnERROR;/*棧空，返回錯誤標志*/p=top->next;e=p->data;/*取棧頂元素*/top->next=p->next;/*修改棧頂指針*/free(p);returnOK;}3.2

棧的應(yīng)用

由于棧具有的“后進先出”的固有特性，因此，棧成為程序設(shè)計中常用的工具和數(shù)據(jù)結(jié)構(gòu)。以下是幾個棧應(yīng)用的例子。3.2.1數(shù)制轉(zhuǎn)換

十進制整數(shù)N向其它進制數(shù)d(二、八、十六)的轉(zhuǎn)換是計算機實現(xiàn)計算的基本問題。轉(zhuǎn)換法則：該轉(zhuǎn)換法則對應(yīng)于一個簡單算法原理:n=(ndivd)*d+nmodd其中：div為整除運算,mod為求余運算例如(1348)10=(2504)8，其運算過程如下：nndiv8nmod8134816841682102125202

采用順序棧方式實現(xiàn)voidconversion(intn,intd)/*將十進制整數(shù)N轉(zhuǎn)換為d(2或8)進制數(shù)*/{SqStackS;intk,*e;S=Init_Stack();while(n>0){k=n%d;push(S,k);n=n/d;}

/*求出所有的余數(shù)，進棧*/while(!StackEmpty(S))/*棧不空時出棧，輸出*/{pop(S,e);printf(“%1d”,*e);}}

3.2.2括號匹配問題在文字處理軟件或編譯程序設(shè)計時，常常需要檢查一個字符串或一個表達式中的括號是否相匹配?匹配思想：從左至右掃描一個字符串(或表達式)，則每個右括號將與最近遇到的那個左括號相匹配。則可以在從左至右掃描過程中把所遇到的左括號存放到堆棧中。每當遇到一個右括號時，就將它與棧頂?shù)淖罄ㄌ?如果存在)相匹配，同時從棧頂刪除該左括號。算法思想：設(shè)置一個棧，當讀到左括號時，左括號進棧。當讀到右括號時，則從棧中彈出一個元素，與讀到的左括號進行匹配，若匹配成功，繼續(xù)讀入；否則匹配失敗，返回FLASE。算法描述#defineTRUE0#defineFLASE-1SqStackS;S=Init_Stack();/*堆棧初始化*/intMatch_Brackets(){charch,x;scanf(“%c”,&ch);while(asc(ch)!=13){if((ch==‘(’)||(ch==‘[’))push(S,ch);elseif(ch==‘]’){x=pop(S);if(x!=‘[’){printf(“’[’括號不匹配”);returnFLASE;}}elseif(ch==‘)’){x=pop(S);if(x!=‘(’){printf(“’(’括號不匹配”);returnFLASE;}}}if(!StackEmpty(S)){printf(“括號數(shù)量不匹配！”);returnFLASE;}elsereturnTRUE;}3.2.2棧與遞歸調(diào)用的實現(xiàn)棧的另一個重要應(yīng)用是在程序設(shè)計語言中實現(xiàn)遞歸調(diào)用。

遞歸調(diào)用：一個函數(shù)(或過程)直接或間接地調(diào)用自己本身，簡稱遞歸(Recursive)。

遞歸是程序設(shè)計中的一個強有力的工具。因為遞歸函數(shù)結(jié)構(gòu)清晰，程序易讀，正確性很容易得到證明。為了使遞歸調(diào)用不至于無終止地進行下去，實際上有效的遞歸調(diào)用函數(shù)