第3章 棧與隊(duì)列1-棧

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

第3章棧和隊(duì)列

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

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

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

棧的概念

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

(LastInFirstOut)或先進(jìn)后出FILO

(FirstInLastOut)線性表。

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

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

空棧：當(dāng)表中沒(méi)有元素時(shí)稱為空棧。

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

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

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

棧的動(dòng)態(tài)順序存儲(chǔ)表示◆結(jié)點(diǎn)出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲(chǔ)位置，然后將棧頂元素取出。圖3-2是一個(gè)動(dòng)態(tài)棧的變化示意圖。圖3-2(動(dòng)態(tài))堆棧變化示意圖空棧bottomtop元素a進(jìn)棧bottomtopa元素b，c進(jìn)棧bottomtopabc元素c退棧bottomtopabbottomtopabdef元素d，e，f進(jìn)棧基本操作的實(shí)現(xiàn)1

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

{if(S.top-S.base>=S.stacksize){S.base=(ElemType*)realloc((S.STACKINCREMENT+STACK_SIZE)*sizeof(ElemType));/*棧滿，追加存儲(chǔ)空間*/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;

/*?？眨祷厥?biāo)志*/S.top--;e=*S.top;returnOK;}

1棧的鏈?zhǔn)奖硎?/p>

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

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

鏈棧基本操作的實(shí)現(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)壓棧(元素進(jìn)棧)Statuspush(Stack_Node*top,ElemTypee){Stack_Node*p;p=(Stack_Node*)malloc(sizeof(Stack_Node));if(!p)returnERROR;/*申請(qǐng)新結(jié)點(diǎn)失敗，返回錯(cuò)誤標(biāo)志*/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;/*棧空，返回錯(cuò)誤標(biāo)志*/p=top->next;e=p->data;/*取棧頂元素*/top->next=p->next;/*修改棧頂指針*/free(p);returnOK;}3.2

棧的應(yīng)用

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

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

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

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

3.2.2括號(hào)匹配問(wèn)題在文字處理軟件或編譯程序設(shè)計(jì)時(shí)，常常需要檢查一個(gè)字符串或一個(gè)表達(dá)式中的括號(hào)是否相匹配?匹配思想：從左至右掃描一個(gè)字符串(或表達(dá)式)，則每個(gè)右括號(hào)將與最近遇到的那個(gè)左括號(hào)相匹配。則可以在從左至右掃描過(guò)程中把所遇到的左括號(hào)存放到堆棧中。每當(dāng)遇到一個(gè)右括號(hào)時(shí)，就將它與棧頂?shù)淖罄ㄌ?hào)(如果存在)相匹配，同時(shí)從棧頂刪除該左括號(hào)。算法思想：設(shè)置一個(gè)棧，當(dāng)讀到左括號(hào)時(shí)，左括號(hào)進(jìn)棧。當(dāng)讀到右括號(hào)時(shí)，則從棧中彈出一個(gè)元素，與讀到的左括號(hào)進(jìn)行匹配，若匹配成功，繼續(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(“’[’括號(hào)不匹配”);returnFLASE;}}elseif(ch==‘)’){x=pop(S);if(x!=‘(’){printf(“’(’括號(hào)不匹配”);returnFLASE;}}}if(!StackEmpty(S)){printf(“括號(hào)數(shù)量不匹配！”);returnFLASE;}elsereturnTRUE;}3.2.2棧與遞歸調(diào)用的實(shí)現(xiàn)棧的另一個(gè)重要應(yīng)用是在程序設(shè)計(jì)語(yǔ)言中實(shí)現(xiàn)遞歸調(diào)用。

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

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