【正文】 線性結(jié)構(gòu)特點(diǎn) 概念：線性表，記錄，文件，表長，空表，位序 線性表的順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ) 從 數(shù)據(jù)類型角度 看 ， 它們是和線性表大不相同的抽象數(shù)據(jù)類型 。 從 數(shù)據(jù)結(jié)構(gòu)角度 看，棧和隊(duì)列是兩種特殊的線性表，它們是操作受限的線性表，故也稱為限定性的數(shù)據(jù)結(jié)構(gòu)。 4 第三章棧與隊(duì)列內(nèi)容介紹 理解 棧和隊(duì)列的定義和特點(diǎn) 重點(diǎn) 熟練掌握棧類型的實(shí)現(xiàn)方法 ， 特別應(yīng)注意 棧滿和棧空的條件 以及它們的描述方法 。 熟練掌握循環(huán)隊(duì)列和鏈隊(duì)列的基本操作實(shí)現(xiàn)算法 ， 特別注意 隊(duì)滿和隊(duì)空的描述方法 。 難點(diǎn) 能在相應(yīng)的應(yīng)用問題中正確選用它們 。 ? 棧 ? 棧的應(yīng)用舉例 ? 棧和遞歸的實(shí)現(xiàn) ? 隊(duì)列 第十講 數(shù)據(jù)結(jié)構(gòu) 棧及其實(shí)現(xiàn) 主講：劉立嘉 舉例 1：家里吃飯的碗，通常在洗干凈后一個(gè)一個(gè)地落在一起存放，在使用時(shí)，若一個(gè)一個(gè)地拿，一定最先拿走最上面的那只碗，而最后拿出最下面的那只碗。 舉例 2：在建筑工地上，使用的磚塊從底往上一層一層地碼放，在使用時(shí)，將從最上面一層一層地拿取。 1 生活中的棧 a1 a2 …. an 進(jìn)棧 出棧 棧頂 棧底 用鐵路調(diào)度站表示棧 1. 定義 限定只能在表的 一端 進(jìn)行插入和刪除操作的線性表。特點(diǎn)：后進(jìn)先出。 2. 邏輯結(jié)構(gòu) 與線性表相同，仍為一對(duì)一關(guān)系。 3. 存儲(chǔ)結(jié)構(gòu) 用 順序棧 或 鏈棧 存儲(chǔ)均可，但以順序棧更常見 4. 運(yùn)算規(guī)則 只能在 棧頂 運(yùn)算，且訪問結(jié)點(diǎn)依照后進(jìn)先出 （ LIFO）或 先進(jìn)后出 （ FILO）的原則。 5. 實(shí)現(xiàn)方式 關(guān)鍵是編寫 入棧 和 出棧 函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯?chǔ)結(jié)構(gòu)有別而不同。 基本操作有 ： 建棧、判斷棧滿或?？?、入棧、出棧、讀棧頂元素值等等。 2 棧的基本概念 ?！吧弦纭? 在棧滿時(shí)還進(jìn)行入棧運(yùn)算，必定會(huì)產(chǎn)生空間的溢出 棧 “ 下溢 ” 當(dāng)棧空時(shí)仍進(jìn)行出棧運(yùn)算，必定會(huì)產(chǎn)生空間的溢出。 上溢是一種出錯(cuò)狀態(tài)，應(yīng)該設(shè)法避免之；下溢則可能是正?，F(xiàn)象，因?yàn)闂Ｔ诔绦蛑惺褂脮r(shí)，其初態(tài)或終態(tài)都是空棧，所以下溢常常用來作為程序控制轉(zhuǎn)移的條件。 棧 是僅在 表尾 進(jìn)行插入、刪除操作的線性表。 表尾 (即 an 端 )稱為 棧頂 /top 。 表頭 (即 a1 端 )稱為 棧底 /base 例如： 棧 S= (a０ , a2 , a3 , ………., an1 , an ) 插入元素到棧頂?shù)牟僮?，稱為 入棧 。 從棧頂刪除最后一個(gè)元素的操作，稱為 出棧 。 an稱為棧頂元素 a1稱為棧底元素 強(qiáng)調(diào)： 插入和刪除都只能在表的一端（棧頂）進(jìn)行！ 注：堆?？梢酝瓿杀容^復(fù)雜的數(shù)據(jù)元素特定序列的轉(zhuǎn)換任務(wù)，但它不能完成任何輸入輸出序列的轉(zhuǎn)換任務(wù)。 例 1：堆棧是什么？它與一般線性表有什么不同？ 堆棧是一種特殊的線性表，它只能在表的 一端（即棧頂） 進(jìn)行插入和刪除運(yùn)算。 與一般線性表的區(qū)別：僅在于 運(yùn)算規(guī)則 不同。 一般線性表 堆棧 邏輯結(jié)構(gòu)： 1:1 邏輯結(jié)構(gòu)： 1:1 存儲(chǔ)結(jié)構(gòu)：順序 表 、鏈 表 存儲(chǔ)結(jié)構(gòu)：順序 棧 、鏈 棧 運(yùn)算規(guī)則： 隨機(jī)存取 運(yùn)算規(guī)則： 后 進(jìn) 先 出 (LIFO) “進(jìn) ” ＝插入 =壓入 “出 ” ＝刪除 =彈出 例 一個(gè)棧的輸入序列為 1,2,3，若在 入棧的過程中允許出棧 ，則可能得到的出棧序列是什么？ 解： 可以通過窮舉所有可能性來求解： ① 1入 1出， 2入 2出， 3入 3出， 即 123； ② 1入 1出， 3入， 2出， 即 132； ③ 2入， 2出， 3入 3出， 即 231； ④ 2入， 1出， 3入 3出， 即 213； ⑤ 3入， 1出， 即 321； 合計(jì)有 5種可能性。 例 一個(gè)棧的輸入序列是 12345，若在 入棧的過程中允許出棧 ， 則棧的輸出序列 43512可能實(shí)現(xiàn)嗎？ 12345的輸出呢？ 解： 43512不可能實(shí)現(xiàn)，主要是其中的 12順序不能實(shí)現(xiàn)； 12345的輸出可以實(shí)現(xiàn)，每壓入一數(shù)便立即彈出即可。 ADT Stack { 數(shù)據(jù)對(duì)象： D＝ { ai | ai ∈ ElemSet, i=1,2,...,n, n≥0 } 數(shù)據(jù)關(guān)系： R1＝ { ai1, ai | ai1, ai∈ D, i=2,...,n } 約定 an 端為 棧頂 ， a1 端為 棧底 。 3 棧的抽象數(shù)據(jù)類型定義 InitStack(amp。S) DestroyStack(amp。S) ClearStack(amp。S) StackEmpty(s) StackLength(S) GetTop(S, amp。e) Push(amp。S, e) Pop(amp。S, amp。e) StackTravers(S, visit()) } ADT Stack 基本操作： InitStack(amp。S) 操作結(jié)果：構(gòu)造一個(gè)空棧 S。 DestroyStack(amp。S) 初始條件：棧 S 已存在。 操作結(jié)果：棧 S 被銷毀。 StackEmpty(S) 初始條件：棧 S 已存在。 操作結(jié)果：若棧 S 為空棧，則返回 TRUE，否則 FALE。 StackLength(S) 初始條件：棧 S 已存在。 操作結(jié)果：返回 S 的元素個(gè)數(shù)，即棧的長度。 GetTop(S, amp。e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：用 e 返回 S 的棧頂元素。 a1 a2 an … … ClearStack(amp。S) 初始條件：棧 S 已存在。 操作結(jié)果：將 S 清為空棧。 Push(amp。S, e) 初始條件：棧 S 已存在。 操作結(jié)果：插入元素 e 為新的棧頂元素。 a1 a2 an e … … Pop(amp。S, amp。e) 初始條件：棧 S 已存在且非空。 操作結(jié)果：刪除 S 的棧頂元素，并用 e 返回其值。 a1 a2 an an1 … … 棧有兩種存儲(chǔ)表示方法：順序棧、鏈棧。 順序棧：即棧的順序存儲(chǔ)結(jié)構(gòu)是利用一組地址連續(xù)的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素 ， 同時(shí)附設(shè)指針 top指示棧頂元素在順序棧中的存儲(chǔ)位置 。 習(xí)慣做法是以 top＝ 0表示空棧 ， 由于 c語言中數(shù)組的下標(biāo)約定從 0開始 ， 則當(dāng)以 c作描述語言時(shí) ，如此設(shè)定會(huì)帶來很大不便 ， 另一方面 ， 由于棧在使用過程中所需最大空間的大小很難估計(jì) ，因此 ， 在初始化設(shè)空棧時(shí)不應(yīng)限定棧的最大容量 。 4 棧的順序表示和實(shí)現(xiàn) 順序（堆）棧 順序存儲(chǔ)結(jié)構(gòu)的堆棧。 順序棧的存儲(chǔ)結(jié)構(gòu) 它是利用一組地址連續(xù)的存儲(chǔ) 單元依次存放自棧底到棧頂?shù)臄?shù) 據(jù)元素，同時(shí)設(shè)指針 top指示棧頂 元素的當(dāng)前位置。用 C語言定義： typedef struct { DataType stack[MaxStackSize]。 int top。 }SeqStack。 a0 a1 …… an1 順序棧 S ai …… an 棧底 base 棧頂 top a0 a1 …… an1 順序棧 S ai …… 問：順序表和順序棧的操作有何區(qū)別？ 表頭 表尾 低地址 高地址 寫入： S[i]= ai 讀出： e= S[i] 壓入 (PUSH): S[top++]=an 彈出 ( POP) : e=S[top] 低地址 高地址 S[i] a0 a1 ai an1 …… 順序表 S …… an 以線性表 S= (a0 , a1 , …. , an2 , an1)為例 棧底 base 棧頂 top 前提：一定要 預(yù)設(shè) 棧頂指針 top 棧頂 top top 空棧 top top top top top a 進(jìn)棧 b 進(jìn)棧 a a b a b c d e e 進(jìn)棧 a b c d e f 進(jìn)棧溢出 a b d e e 退棧 c top c 退棧 b 退棧 a b a a 退棧 空 棧 top a b d d 退棧 c top a b c top top 棧不存在的條件： base=NULL。 棧為空 的條件 ： base=top。 棧滿的條件 ： topbase=MaxSize。 a0 a1 …… an1 順序棧 S ai …… 低地址 高地址 an 棧底 base 棧頂 top 入棧 口訣：堆棧指針 top “先壓后加” : S[top++]=an 出棧 口訣：堆棧指針 top “先減后彈” : e=S[top] 順序棧的操作實(shí)現(xiàn) (1)初始化棧 void StackInitiate(SeqStack *S) /*初始化順序堆棧 S*/ { Stop = 0。 /*定義初始棧頂下標(biāo)值 */ } (2)判棧非空否 int StackNotEmpty(SeqStack S) /*判順序堆棧 S非空否，非空則返回 1，否則返回0*/ { if( = 0) return 0。 else return 1。 } (3)入棧 int StackPush(SeqStack *S, DataType x) /*把數(shù)據(jù)元素值 x壓入順序堆棧 S，入棧成功則返回 1，否則返回 0 */ { if(Stop = MaxStackSize) { printf(堆棧已滿無法插入 ! \n)。 return 0。 } else { Sstack[Stop] = x。 Stop ++。 return 1。 } } (4)出棧 int StackPop(SeqStack *S, DataType *d) /*彈出順序堆棧 S的棧頂數(shù)據(jù)元素值到參數(shù) d ，出棧成功則返回 1，否則返回 0*/ { if(Stop = 0) { printf(堆棧已空無數(shù)據(jù)元素出棧 ! \n)。 return 0。 } else { Stop 。 *d = Sstack[Stop]。 return 1。 } } (5)取棧頂數(shù)據(jù)元素 int StackTop(SeqStack S, DataType *d) /*取順序堆棧 S的當(dāng)前棧頂數(shù)據(jù)元素值到參數(shù) d ，成功則返回 1，否則返回 0*/ { if( = 0) { printf(堆棧已空 ! \n)。 return 0。 } else { *d = [ 1]。 return 1。 } } 例： 用堆棧存放（ A， B， C， D） A A C B A B A top 順序棧 入棧 函數(shù)的核心語句： Sstack[Stop] = x。 Stop ++。 top top top top 低地址 L 高地址 M B C D 例：從棧中取出 ‘ B? D C B A top top D C A B D C B A top D C B A top 低地址 L 高地址 M 順序棧出棧函數(shù)的核心語句： Stop 。 *d = Sstack[Stop