資源描述：
《SUN數(shù)據(jù)結(jié)構(gòu)第3章棧和隊(duì)列(第8-10講).ppt》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、緒言從數(shù)據(jù)結(jié)構(gòu)上看，棧和隊(duì)列也是線性表，不過是兩種特殊的線性表。棧只允許在表的一端進(jìn)行插入或刪除操作，而隊(duì)列只允許在表的一端進(jìn)行插入操作、而在另一端進(jìn)行刪除操作。因而，棧和隊(duì)列也可以被稱作為操作受限的線性表。13.1棧棧，也叫堆棧，是最常用也是最重要的數(shù)據(jù)結(jié)構(gòu)之一。棧(Stack)是限定僅在表的一端進(jìn)行插入或刪除操作的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時(shí)稱為空棧。舉例：棧操作的特點(diǎn)：后進(jìn)先出，先進(jìn)后出。因此，棧稱為后進(jìn)先出表（LIFO,
2、LastInFirstOut）。2anan-1a2a1……棧頂入棧出棧進(jìn)棧出棧示意圖棧底3初始化棧InitStack(S)設(shè)置一個空棧S。壓棧Push(S,x)將元素x插入棧S中，使x成為棧S的棧頂元素。出棧Pop(S,x)當(dāng)棧S不空時(shí)，由x返回棧頂元素，并從棧中刪除棧頂元素取棧頂元素GetTop(S,x)若棧S不空，則由x返回棧頂元素。判?？誆mpty(S)若棧S為空棧，結(jié)果為1，否則結(jié)果為0。2．棧的基本運(yùn)算在棧頂插入元素在棧頂刪除元素43.1.2棧的順序存儲結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)棧有兩種存儲
3、表示方法:順序存儲和鏈?zhǔn)酱鎯Γ?）棧的順序存儲結(jié)構(gòu)采用順序存儲結(jié)構(gòu)的棧簡稱為順序棧。是利用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，同時(shí)附設(shè)整型變量top指示棧頂元素在順序棧中的位置。5順序棧數(shù)據(jù)類型的C語言描述如下：top:棧頂指針。取值范圍為0～MaxSize-1。top==-1表示?？?，top==MaxSize-1表示棧滿。#defineMaxSize100typedefcharSElemType;typedefstruct{SElemTypedata[MaxSize];int
4、top;}STACK;6順序棧的幾種狀態(tài)（最大長度MaxSize為4）①棧空；②壓棧；③棧滿；④出棧。7棧的基本運(yùn)算在順序存儲結(jié)構(gòu)的實(shí)現(xiàn)初始化棧InitStack(S)intInitStack(STACK*S){S->top=-1;return1;}8intPush(STACK*S,SElemTypex){if(S->top==MaxSize-1){printf("Stackisfull!");exit(1);}S->top++;S->data[S->top]=x;return1;}壓棧前應(yīng)
5、先判斷是否棧滿且注意壓棧順序：（1）top指針加1；（2）元素壓入壓棧Push(S,x)9intEmpty(STACK*S){return(S->top==-1?1:0);}判?？誆mptyStack(S)10intPop(STACK*S,SElemType*x){if(EmptyStack(S)){printf("Stackisfree!");exit(1);}*x=S->data[S->top];—記住要刪除的元素值S->top--;return1;}傳址自定義函數(shù)一次只能有一個返回值出
6、棧Pop(S,x)11SElemTypeGetTop(STACK*S){SElemTypex;if(Empty(S)){printf("Stackisfree!");return0;}x=S->data[S->top];returnx；}取棧頂元素GetTopStack(S,x)exit(1);12課堂練習(xí)1.棧和隊(duì)列都是（）。A.順序存儲的線性結(jié)構(gòu)B.限制存取點(diǎn)的線性結(jié)構(gòu)C.鏈接存儲的線性結(jié)構(gòu)D.限制存取點(diǎn)的非線性結(jié)構(gòu)B132.在一個具有n個單元的順序棧中，假定以地址低端作為棧底，以top
7、作為棧頂指針，則當(dāng)出棧時(shí)，top變化為。A.top不變Ｂ.top＝-nC.top＝top-1D.top=top+1C課堂練習(xí)14C課堂練習(xí)3.若進(jìn)棧序列為1,2,3,4,進(jìn)棧過程中可以出棧，則不可能是一個出棧序列。A.3,4,2,1B.2,4,3,1C.1,4,2,3D.3,2,1,44、假設(shè)以S和X分別表示進(jìn)棧和退棧操作，則對輸入序列1,2,3,4,5進(jìn)行一系列棧操作SXSSXSSXXX之后，得到的輸出序列為。13542試找出所有可能的出棧序列共14種15課堂練習(xí)5.若已知一個棧的入棧序列是1
8、,2,3,…,n，其輸出序列為p1,p2,p3,…,pn，若p1=n，則pi為()。A.iB.n-i+1C.n-iD.不確定B16課堂練習(xí)6.判定一個棧ST（MaxSize=n）為空的條件是()。Ａ．ST->top!=-1Ｂ．ST->top==-1Ｃ．ST->top!=nＤ．ST->top==nB17棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)（1）棧的鏈?zhǔn)酱鎯Y(jié)構(gòu)通常將采用鏈?zhǔn)酱鎯Φ臈７Q為鏈棧。鏈棧結(jié)構(gòu)示意圖：top棧頂指針，惟一的確定一個鏈棧。鏈棧通常帶有一個表頭結(jié)點(diǎn)，所以top->next才指示棧頂元
