[理學(xué)]第4章棧和隊(duì)列(已修改)
2025-01-31 14:59 本頁面
【正文】 1 第 4章 棧和隊(duì)列 棧 棧的順序存儲結(jié)構(gòu)和操作實(shí)現(xiàn) 棧的鏈接存儲結(jié)構(gòu)和操作實(shí)現(xiàn) 棧的簡單應(yīng)用舉例 算術(shù)表達(dá)式的計(jì)算 棧與遞歸 隊(duì)列 隊(duì)列應(yīng)用舉例 2 1. 定義 棧 與線性表相同，仍為一對一 ( 1:1)關(guān)系。 用 順序棧 或 鏈棧 存儲均可，但以順序棧更常見 只能在 棧頂 運(yùn)算，且訪問結(jié)點(diǎn)時(shí)依照 后進(jìn)先出（ LIFO）或 先進(jìn)后出 （ FILO）的原則。 關(guān)鍵是編寫 入棧 和 出棧 函數(shù)，具體實(shí)現(xiàn)依順序?；蜴湕５拇鎯Y(jié)構(gòu)有別而不同。 3. 存儲結(jié)構(gòu) 4. 運(yùn)算規(guī)則 5. 實(shí)現(xiàn)方式 2. 邏輯結(jié)構(gòu) 限定只能在表的 一端 進(jìn)行插入和刪除運(yùn)算的線性表。 即棧頂 基本操作有 ： 建棧、判斷棧滿或棧空、入棧、出棧、讀棧頂元素值，等等。 3 棧的示意圖 a1 a2 an1 an 入棧 出棧 top bottom 棧底 棧頂 4 棧 是僅在 表尾 進(jìn)行插入、刪除操作的線性表。 表尾 (即 an 端 )稱為 棧頂 /top 。 表頭 (即 a1 端 )稱為 棧底 /base 例如： 棧 S= (a1 , a2 , a3 , ………., an1 , an ) 插入元素到棧頂?shù)牟僮?，稱為 入棧 。 從棧頂刪除最后一個(gè)元素的操作，稱為 出棧 。 an稱為棧頂元素 a1稱為棧底元素 想一想：要從棧中取出 a1，應(yīng)當(dāng)如何操作？ 強(qiáng)調(diào)： 插入和刪除都只能在表的一端（棧頂）進(jìn)行！ 5 Q1：堆棧是什么？它與一般線性表有什么不同？ 堆棧是一種特殊的線性表，它只能在表的 一端（即棧頂） 進(jìn)行插入和刪除運(yùn)算。 與一般線性表的區(qū)別：僅在于 運(yùn)算規(guī)則 不同。 一般線性表 堆棧 邏輯結(jié)構(gòu)： 1:1 邏輯結(jié)構(gòu)： 1:1 存儲結(jié)構(gòu)：順序 表 、鏈 表 存儲結(jié)構(gòu)：順序 棧 、鏈 棧 運(yùn)算規(guī)則： 隨機(jī)存取 運(yùn)算規(guī)則： 后進(jìn)先出 (LIFO) “進(jìn) ” ＝插入 =壓入 =PUSH（ an+1) “出 ” ＝刪除 =彈出 =POP(an) 6 a1 a2 …… an 順序棧 S ai …… Q2：順序表和順序棧的操作有何區(qū)別？ 表頭 表尾 低地址 高地址 寫入： S[i]= ai
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1