【正文】 *Top。 ? 鏈棧示意圖如右圖 : 棧頂是 Top指針，它惟一地確定一個(gè)鏈棧。 } linkstack。 鏈棧定義如下： typedef char datatype； typedef struct node { datatype data。 它是運(yùn)算 受限的單鏈表 ， 其插入和刪除操作僅在 表頭 進(jìn)行 。 *temp= Sdata[STop]。 return (temp)； 2021/11/10 17 取棧頂元素 : datatype * GetTopS (SeqStack *S) { } datatype *temp。 *temp= Sdata[STop]。 順序棧運(yùn)算的實(shí)現(xiàn)： 2021/11/10 15 元素 e進(jìn)棧 Sdata[++STop]=e； int PushS(SeqStack *S, datatype e) { } if (STop=maxsize1) { printf (―棧上溢” )； return 0； } else { } STop++； Sdata[STop]=e； return 1； 順序棧運(yùn)算的實(shí)現(xiàn)： 2021/11/10 16 出棧 ——若棧不為空，則刪除棧頂元素，并帶回指針 datatype * PopS(SeqStack *S) { } datatype *temp。 } 置空棧 void SetNuLLStack(SeqStack *S) { STop=1 (或 0)。 STop=1(或 0)。 下溢： 當(dāng)棧空時(shí)再做退棧運(yùn)算產(chǎn)生的溢出。 那么： 進(jìn)棧： S–top+ +； 退棧： S–top ； 空棧： S–top=1 ； 棧滿： S–top =maxsize1。 2021/11/10 10 設(shè) S是 SeqStack類型的指針變量?？諚?Top值為 1, 棧底位置為 0。 datatype是棧中數(shù)據(jù)元素的數(shù)據(jù)類型。 typedef char datatype。 必須設(shè)置一個(gè) 棧頂指針 永遠(yuǎn)指向棧頂元素。 必須附設(shè)一個(gè)位置指針 top（棧頂指針）來動(dòng)態(tài)地指示 棧頂元素 在順序棧中的位置。 該操作完成后 , 棧的狀態(tài)不變 。 ? 出棧 —PopS(S): 刪除棧 S的棧頂數(shù)據(jù)元素 ， 并將該數(shù)據(jù)元素 返回 。 ? 判斷?？?—EmptyS(S): 若棧 S為空則返回真 （ 1） ， 否則返 回假 （ 0） 。 a1 a2 an 棧頂元素 棧底元素 棧頂 棧底 入棧 出棧 2021/11/10 7 棧的常用運(yùn)算： ? 棧初始化 —InitStack（ S） : 完成對(duì)棧的初始化 。 ?當(dāng)棧中沒有數(shù)據(jù)元素時(shí)稱為 空棧 。允許操作的一端稱為 棧頂 ，棧頂元素的位置由一個(gè)稱為 棧頂指針 的變量給出。 ? 操作系統(tǒng)中斷管理 :當(dāng)計(jì)算機(jī)發(fā)生中斷時(shí)要保存現(xiàn)場(chǎng)信息時(shí)一般壓到棧中，當(dāng)返回時(shí)在從棧中返回來。 ? 進(jìn)制轉(zhuǎn)換 。棧就是這樣一種數(shù)據(jù)結(jié)構(gòu)。現(xiàn)在把不同編號(hào)的小球放到竹筒里面， 可以發(fā)現(xiàn)一種規(guī)律：先放進(jìn)去的小球只能后拿出來，反之，后放進(jìn)去的小球能夠先拿出來 。2021/11/10 1 第 4章 棧和隊(duì)列 2021/11/10 2 第 4章 棧和隊(duì)列 棧 隊(duì)列 2021/11/10 3 設(shè)想有一個(gè)直徑不大、一端開口一端封閉的竹筒。有若干個(gè)寫有編號(hào)的小球，小球的直徑比竹筒的直徑略小。所以 “ 先進(jìn)后出 ” 就是這種結(jié)構(gòu)的特點(diǎn)。 2021/11/10 4 為什么使用棧 ? ? 函數(shù)調(diào)用 ：給函數(shù)傳遞參數(shù)， 當(dāng)函數(shù)調(diào)用工作完成時(shí)，被調(diào)函數(shù)需要把控制權(quán)返回給調(diào)用語句之后的指令 ,等實(shí)現(xiàn)起來要靠棧的幫助。 ? 算術(shù)表達(dá)式計(jì)算 。 2021/11/10 5 棧 定義 : 棧： 是一種只允許在表的一端進(jìn)行插入操作和刪除操作的線性表。不允許操作的一端稱為 棧底 。 2021/11/10 6 假設(shè)棧 S=(a1， a2， ...， an)， 可以形象描述為右圖所示形式： ?a1是棧底元素； ?an是棧頂元素； ?入棧：指插入數(shù)據(jù)元素 ； ?出棧：指刪除棧頂?shù)臄?shù)據(jù)元素 ； ?后入棧的元素先于先入棧的元素出棧 ， 故被稱為是一種 后進(jìn)先出 的結(jié)構(gòu) ， 因此又稱 LIFO（ Last In First Out的縮寫 ） 表 。 ? 置空棧 —SetNullS(S): 將棧 S清空 。 ? 進(jìn)棧 ——PushS(S,e): 在棧 S的棧頂插入數(shù)據(jù)元素 e。 ? 取棧頂元素 —GetTopS(S): 取棧 S的棧頂數(shù)據(jù)元素 ， 并把數(shù) 據(jù)元素返回 。 2021/11/10 8 棧的存儲(chǔ)結(jié)構(gòu) 順序棧 利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，一般用 一維數(shù)組 表示。 鏈棧 采用鏈表作為存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。 2021/11/10 9 棧的順序存儲(chǔ)表示 —— 順序棧 ? 定義 : 棧的順序存儲(chǔ)結(jié)構(gòu)定義為： define maxsize 1024 。 typedef struct stack { datatype data[maxsize]； int Top； } Seqstack ； 其中： maxsize是棧的容量。 Top指示當(dāng)前棧頂位置，實(shí)際是棧中元素的 索引號(hào) ，即 數(shù)組下標(biāo) 。 0下標(biāo)單元不用時(shí) ， 空棧 Top值為 0, 棧底位置為 1。若棧底位置在向量的低 端，即 S–data[0]是棧底元素。 上溢： 當(dāng)棧滿時(shí)再做進(jìn)棧運(yùn)算必定產(chǎn)生的空間溢出 。 順序棧 : 2021/11/10 11 0 1 2 3 4 5 Top=1 Top=0 Top=4 Top=2 Top=1 A (a)空棧 (b)’A’進(jìn)棧 (c)’B’ ’C’ ’D’ ’E’進(jìn)棧 (d)’E’ ’D’出棧 (e)’C’ ’B’ ’A’ 出棧 0 1 2 3 4 5 * 數(shù)組下標(biāo)為 0的元素空間使用的情況 STop A B C D E A B C 0 1 2 3 4 5 0 1 2 3 4 5 0 1 2 3 4 5 STop STop STop STop 2021/11/10 12 (a)空棧 (b)’A’進(jìn)棧 (c)’B’ ’C’ ’D’ ’E’進(jìn)棧 (d)’E’ ’D’出棧 0 1 2 3 4 5 Top=0 Top=1 Top=5 Top=3 Top=0 A A B C D E A B C 0 1 2 3 4 5 0 1 2 3