資源描述：
《Ch3.棧和隊列-棧.ppt》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、第三章棧和隊列3.1棧3.1.1抽象數(shù)據(jù)類型棧的定義3.1.2順序棧3.1.3鏈棧本章節(jié)的基本內(nèi)容是：1棧(Stack)是限制在表的一端進行插入和刪除運算的線性表，通常稱插入、刪除的這一端為棧頂(Top)，另一端為棧底(Bottom)。當(dāng)表中沒有元素時稱為空棧。假設(shè)棧S=(a1，a2，a3，…an)，則a1稱為棧底元素，an為棧頂元素。棧中元素按a1，a2，a3，…an的次序進棧，退棧的第一個元素應(yīng)為棧頂元素。換句話說，棧的修改是按后進先出的原則進行的。因此，棧稱為后進先出（LIFO）或下推表。3.1.1棧的定義及基本運算2棧的邏輯結(jié)構(gòu)空棧：不含任何
2、數(shù)據(jù)元素的棧。（a1,a2,……,an）棧：限定僅在表尾進行插入和刪除操作的線性表。棧頂棧底允許插入和刪除的一端稱為棧頂，另一端稱為棧底。3a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧頂棧的示意圖4棧的操作特性：后進先出a1a2a3入棧出棧棧底棧頂插入：入棧、進棧、壓棧刪除：出棧、彈棧棧頂棧的示意圖5例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧底棧頂ab棧頂c棧頂情況1：棧的邏輯結(jié)構(gòu)6棧底棧頂ab棧頂c棧頂出棧序列：c出棧序列：c、b出棧序列：c、b、a例：有三個元素按a
3、、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況1：7棧底棧頂ab棧頂出棧序列：b情況2：例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)8棧底a出棧序列：b出棧序列：b、c出棧序列：b、c、ac棧頂棧頂注意：棧只是對表插入和刪除操作的位置進行了限制，并沒有限定插入和刪除操作進行的時間。例：有三個元素按a、b、c的次序依次進棧，且每個元素只允許進一次棧，則可能的出棧序列有多少種？棧的邏輯結(jié)構(gòu)情況2：9棧的抽象數(shù)據(jù)類型定義ADTStack{Data棧中
4、元素具有相同類型及后進先出特性，相鄰元素具有前驅(qū)和后繼關(guān)系OperationInitStack(S)構(gòu)造一個空棧Push(S,x)在棧頂插入一個元素x,如果插入不成功，拋出異常;否則棧頂增加了一個元素。10Pop（S,e）刪除棧頂元素,如果刪除成功，返回被刪元素值e，否則，拋出異常;否則棧減少了一個元素.Stacktop(S,e)讀取當(dāng)前的棧頂元素,若棧不空，返回當(dāng)前的棧頂元素值e,棧不變.Stackempty(S)判斷棧S是否非空，空返回1，非空返回0。}ADTStack棧的抽象數(shù)據(jù)類型定義11由于棧是運算受限的線性表，因此線性表的存儲結(jié)構(gòu)對棧也適
5、應(yīng)。棧的順序存儲結(jié)構(gòu)簡稱為順序棧，它是運算受限的線性表。因此，可用數(shù)組來實現(xiàn)順序棧。因為棧底位置是固定不變的，所以可以將棧底位置設(shè)置在數(shù)組的兩端的任何一個端點；棧頂位置是隨著進棧和退棧操作而變化的，故需用一個整型變量top來指示當(dāng)前棧頂?shù)奈恢茫ǔ７Qtop為棧頂指針。3.1.2順序棧12棧的順序存儲結(jié)構(gòu)及實現(xiàn)順序?！獥５捻樞虼鎯Y(jié)構(gòu)如何改造數(shù)組實現(xiàn)棧的順序存儲？012345678a1確定用數(shù)組的哪一端表示棧底。附設(shè)指針top指示棧頂元素在數(shù)組中的位置。top3.1.2順序棧13出棧：top減1進棧：top加1?？眨簍op=-1012345678a1
6、topa2topa3top棧滿：top=MAX_SIZE-1棧的順序存儲結(jié)構(gòu)及實現(xiàn)3.1.2順序棧14因此，順序棧的類型定義只需將順序表的類型定義中的長度屬性改為top即可。順序棧的類型定義如下：#defineStackSize100typedefchardatatype;typedefstruct{datatypedata[stacksize];inttop;}seqstack;順序棧的類型定義15設(shè)S是SeqStack類型的指針變量。若棧底位置在向量的低端，即s–>data[0]是棧底元素，那么棧頂指針s–>top是正向增加的，即進棧時需將s–>
7、top加1，退棧時需將s–>top減1。因此，s–>top<0表示空棧，s–>top=stacksize-1表示棧滿。當(dāng)棧滿時再做進棧運算必定產(chǎn)生空間溢出，簡稱“上溢”;當(dāng)?？諘r再做退棧運算也將產(chǎn)生溢出，簡稱“下溢”。為了避免溢出，在對棧進行進棧和出展運算前，應(yīng)分別判斷棧是否已滿或者是否已空。161、置空棧voidinitstack(seqstack*s){s–>top=-1;}//initstack172、判斷棧空intstackempty(seqstack*s){return(s–>top==-1);}//stackempty183、判斷棧滿in
8、tstackfull(seqstack*s){return(s–>top==stacksize-1);}19
