資源描述：
《孫麗云數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(第8-10講)》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、緒言從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊(duì)列也是線性表，不過(guò)是兩種特殊的線性表。棧只允許在表的一端進(jìn)行插入或刪除操作，而隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作。因而，棧和隊(duì)列也可以被稱作為操作受限的線性表。13.1棧棧，也叫堆棧，是最常用也是最重要的數(shù)據(jù)結(jié)構(gòu)之一。棧(Stack)是限定僅在表的一端進(jìn)行插入或刪除操作的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒(méi)有元素時(shí)稱為空棧。舉例：棧操作的特點(diǎn)：后進(jìn)先出。因此，棧稱為后進(jìn)先出表（LIFO,LastInFirstOut）。2anan-1a2a1……棧頂入棧出棧進(jìn)棧出棧示意圖棧底3初始化
2、棧InitStack(S)設(shè)置一個(gè)空棧S。壓棧Push(S,x)將元素x插入棧S中，使x成為棧S的棧頂元素。出棧Pop(S,x)當(dāng)棧S不空時(shí)，由x返回棧頂元素，并從棧中刪除棧頂元素取棧頂元素GetTop(S,x)若棧S不空，則由x返回棧頂元素。判棧空Empty(S)若棧S為空棧，結(jié)果為1，否則結(jié)果為0。2．棧的基本運(yùn)算在棧頂插入元素在棧頂刪除元素43.1.2棧的順序存儲(chǔ)結(jié)構(gòu)及其基本運(yùn)算的實(shí)現(xiàn)棧有兩種存儲(chǔ)表示方法:順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)1、棧的順序存儲(chǔ)結(jié)構(gòu)棧的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序棧。是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)指針top指示棧頂元素在順序棧中的
3、位置。5（a）當(dāng)棧中沒(méi)有數(shù)據(jù)元素時(shí)，表示為?？铡ｍ斣厮鶎?duì)應(yīng)的下標(biāo)值top=-1。（b）表示在（a）基礎(chǔ)上執(zhí)行Push(S,‘A’)后得到這種狀態(tài)。（c）又有三個(gè)元素B、C、D先后入棧，此時(shí)棧頂元素的下標(biāo)值top=3。棧已滿。（d）表示在（c）狀態(tài)下，執(zhí)行一次Pop(S，x)運(yùn)算得到。（e）表示在（d）狀態(tài)下，執(zhí)行三次Pop(S，x)運(yùn)算得到。此時(shí)棧頂下標(biāo)值top=-l，又變成?？諣顟B(tài)順序棧的幾種狀態(tài)（最大長(zhǎng)度MaxSize為4）6順序棧的C語(yǔ)言描述如下：#defineMaxSize<存儲(chǔ)數(shù)據(jù)元素的最大個(gè)數(shù)>typedefstruct{ElemTypedata[MaxSize]
4、;inttop;}STACK;ElemType為棧中元素的數(shù)據(jù)類型，可以根據(jù)需要而指定為某種具體的類型。成員data:為一個(gè)一維數(shù)組，用于存儲(chǔ)棧中元素。成員top:棧頂指針。取值范圍為0～MaxSize-1。top=-1表示?？?，top=MaxSize-1表示棧滿。72．基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)（1）初始化棧InitStack(S)voidInitStack(STACK*S){S->top=-1;}（2）壓棧Push(S,x)intPush(STACK*S,ElemTypex){if(S->top==MaxSize-1){printf("Stackisfull!");re
5、turn0;}S->top++;S->data[S->top]=x;return1;}注意壓棧順序：（1）top指針加1；（2）元素壓入82．基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)（3）出棧Pop(S,x)intPop(STACK*S,ElemType*x){if(Empty(S)){printf("Stackisfree!");return0;}*x=S->data[S->top];—記住要?jiǎng)h除的元素值S->top--;return1;}傳址自定義函數(shù)一次只能有一個(gè)返回值92．基本運(yùn)算在順序存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)（4）取棧頂元素GetTop(S,x)intGetTop(STACK*S,Ele
6、mType*x){if(Empty(S)){printf("Stackisfree!");return0;}*x=S->data[S->top];return1；}（5）判?？誆mpty(S)intEmpty(STACK*S){return(S->top==-1?1:0);}101.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針，則當(dāng)出棧時(shí)，top變化為。A.top不變Ｂ.top＝-nC.top＝top-1D.top=top+1C課堂練習(xí)11C課堂練習(xí)2.若進(jìn)棧序列為1,2,3,4,進(jìn)棧過(guò)程中可以出棧，則不可能是一個(gè)出棧序列。A.3,4,2,1B.
7、2,4,3,1C.1,4,2,3D.3,2,1,43、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對(duì)輸入序列1,2,3,4,5進(jìn)行一系列棧操作SXSSXSSXXX之后，得到的輸出序列為。13542試找出所有可能的出棧序列12棧的應(yīng)用舉例——應(yīng)用棧解決數(shù)制的轉(zhuǎn)換問(wèn)題例如：（1348)10=(2504)8，其運(yùn)算過(guò)程如下：NNdiv8Nmod8 13481684 168210 2125 202計(jì)算順序輸出順序13棧的應(yīng)用舉例——應(yīng)用棧解決數(shù)制的轉(zhuǎn)換問(wèn)題charB[]=“0123456789
