1 57 2 第3章棧和隊列 棧和隊列被稱為操作受限的線性表 本章介紹棧和隊列的邏輯結構和存儲結構 以及棧和隊列的基本運算以及實現算法 3 a1 a2 ai 1 ai ai 1 an 3 1棧 只允許在線性表的一端進行插入和刪除操作的線性表允許插入和刪除的一端稱為棧頂 top 另一端稱為棧底 bottom 特點后進先出 LIFO 4 棧的基本操作INITSTACK s 構造一個空棧s STACKEMPTY s 判斷s是否為空棧 若s為空棧 返回1 否則返回0 PUSH s x 進棧操作 在棧s頂部插入一個新的元素x POP s x 退棧操作 若s非空 刪除s中的棧頂元素 并返回該元素 5 GETTOP s 取棧s的棧頂元素 若s非空 返回棧頂元素 但與POP s x 的區別是GETTOP s 不改變棧的狀態 CLEASTACK s 將棧s清為空棧 STACKLENGTH s 求棧的長度 返回棧s中的元素個數 6 棧的表示和實現 由于棧是運算受限的線性表 因此線性表的存儲結構對棧也適應 1 順序棧棧的順序存儲結構 順序棧 可以將棧底位置設置在數組的低地址端點 棧頂位置是隨著進棧和退棧操作而變化的 故需用一個整型變量top 指明當前棧頂的位置 同樣將data數組和top封裝在一個結構中 順序棧的類型描述如下 defineMAXSIZE1024typedefstructSeqStack datatypedata MAXSIZE inttop SeqStack 7 8 bottom bottom A A B C D E A B 棧操作圖示 A進棧 BCDE進棧 EDC出棧 C D E 棧的特點后進先出LIFO 入棧與出棧 9 約定棧頂指針指向向棧頂元素的位置 順序棧的圖示 棧空 棧滿 Top 1 Top maxlen 1 10 2 順序棧的基本運算算法 1 初始化棧voidINITSTACK seqstack s 創建一個空棧由指針S指向 s top 1 思考 voidINITSTACK seqstacks s top 1 哪個是對的 為什么 11 12 2 判棧空判定順序棧S是否空棧 S為空時 返回為1 非空時 返回為0intSTACKEMPTY seqstack s if s top 0 s top 0 return0 elsereturn1 13 3 入棧操作PUSH seqstacks datatypex if s top maxsize 1 error overflow returnNULL 上溢 退出運行 else s top 棧頂指針 1 s data s top x 將x入棧 14 4 出棧操作datatypePOP seqstacks ifSTACKEMPTY s error underflow 下溢 returnNULL else return s data s top s top 15 5 取棧頂元素操作datatypeGETTOP seqstacks if STACKEMPTY s error stackisempty returnNULL 棧空 elsereturn s data s top 取棧頂元素 16 順序棧的不足 存在棧滿以后就不能再進棧的問題 這是因為用了定長的數組存儲棧的元素 解決方法 使用鏈式存儲結構 17 2 鏈棧棧的鏈式存儲結構 也稱鏈棧 沒有頭結點的單鏈表 其各結點的結構與單鏈表中的結點結構完全相同 如圖所示 在前面學習了線性鏈表的插入刪除操作算法 不難寫出鏈式棧初始化 進棧 出棧等操作的算法 結點結構定義 Typedefstructnode elemtypedata structnode next node pointer 18 1 初始化棧Voidinitstack pointers s null 19 進棧前進棧后 2 進棧 20 進棧算法Voidpush pointers datatypex p pointer malloc sizeof node p data x p next s s p 21 出棧前出棧后 3 出棧 22 出棧算法 Datatypepop pointers if s null return null else p s x p data s p next free p return x 23 3 2隊列 隊列是只允許在一端刪除 在另一端插入的順序表允許刪除的一端叫做隊頭 front 允許插入的一端叫做隊尾 rear 特性先進先出 FIFO FirstInFirstOut 24 隊列的基本運算 隊列初始化 Init Queue q 初始條件 隊q不存在 操作結果 構造一個空隊 入隊操作 In Queue q x 初始條件 隊q存在 操作結果 對已存在的隊列q 插入一個元素x到隊尾 隊發生變化 出隊操作 Out Queue q x 初始條件 隊q存在且非空操作結果 刪除隊首元素 并返回其值 隊發生變化 讀隊頭元素 Front Queue q x 初始條件 隊q存在且非空操作結果 讀隊頭元素 并返回其值 隊不變 判隊空操作 Empty Queue q 初始條件 隊q存在操作結果 若q為空隊則返回為1 否則返回為0 25 隊列的存儲結構及操作實現 1 鏈隊列用鏈表表示的隊列簡稱為鏈隊列 在一個鏈隊列中需設定兩個指針 頭指針和尾指針 分別指向隊列的頭和尾 給鏈隊列添加一個頭結點 并設定頭指針指向頭結點 空隊列的判定條件為頭指針和尾指針都指向頭結點 26 typedefstructnode datatypedata structnode next QNode 鏈隊結點的類型 typedefstruct QNnode front rear LQueue 將頭尾指針封裝在一起的鏈隊 27 討論 空鏈隊的特征 怎樣實現鏈隊的入隊和出隊操作 鏈隊會滿嗎 front rear 一般不會 因為刪除時有free動作 除非內存不足 入隊 尾部插入 rear next S rear S 出隊 頭部刪除 front next p next 鏈隊示意圖 28 刪除 一個元素 添加一個元素 e Q front Q rear 隊頭 隊尾 Q rear 注意 linkqueueQ 29 鏈隊列的主要運算算法 置空隊列voidINITQUEUE linkqueue q 構造一個只含頭結點的空隊列 q linkqueue malloc sizeof linkqueue q rear q front 尾指針指向頭結點 q front next NULL 頭結點指針為空 置空隊列voidINITQUEUE linkqueueq 構造一個只含頭結點的空隊列 q rear q front 尾指針指向頭結點 q front next NULL 頭結點指針為空 注意 linkqueue Q 注意 linkqueueQ 30 判隊空boolEMPTYQUEUE linkqueue q 判斷隊列是否為空 為空返回TRUE 否則返回FALSE if q front q rear return TRUE elsereturn FALSE 31 入隊voidENQUEUE linkqueue q datatypee 將元素e插入鏈隊列尾部 p queuenode malloc sizeof queuenode p data e p next NULL q rear next p q rear p 32 出隊datatypeDEQUEUE linkqueue q datatype 33 取隊頭元素datatypeGETFIRST linkqueue q if EMPTYQUEUE q printf EMPTYQUEUE returnNULL 隊列空 elsereturn q front next data GETFIRST 34 2 順序隊列隊列的順序存儲結構可以簡稱為順序隊列 用一組地址連續的存儲單元依次存放隊列中的數據元素 設立兩個指示器 指向隊頭元素的指示器front 指向隊尾的元素位置的指示器rear 35 a 線性隊列 e2 c e2入隊 e0 e1出隊 rear 3 front e0 e1 b rear front b e0 e1入隊 隊空時 令rear front 0 當有新元素入隊時 尾指針加1 當有元素出隊時 頭指針加1 故在非空隊列中 頭指針始終指向隊頭元素位置 而尾指針始終指向隊尾元素的下一位置 36 順序隊列的類型定義如下 definemax100 隊列最大長度 typedefstructsequeue datatypedata max intfront intrear sequeue 順序隊列類型 sequeue sq sq為順序隊列類型的指針 37 順序隊列的缺點 當前隊列并未占滿 但隊列中元素出隊后讓出的實際可用空間卻不能得以使用 因此把這種溢出現象稱為 假溢出 解決辦法之一 將隊列元素存放數組首尾相接 形成循環 環形 隊列 38 循環隊列 在將順序隊列的存儲區假想為一個環狀的空間 假想q queue 0 接在q queue MAXNUM 1 的后面 當發生假溢出時 將新元素插入到第一個位置上 入列和出列仍按 先進先出 的原則進行 首指針front和尾指針rear沿環順時針移動 只要尾指針rear不與首指針相遇 該隊列就可繼續操作 稱這種隊列為循環隊列 sequeue sq sq為順序隊列類型的指針 sqq q為順序隊列sq類型 39 循環隊列為隊列空時 有q front q rear q front rear 隊列滿時 也有q front q rear 因此僅憑q front q rear不能判定隊列是空還是滿 規定循環隊列中少用一個元素空間 以尾指針在頭指針的前一位置作為隊列滿的條件 40 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front 0 1 2 3 4 5 6 7 front rear A A B C rear rear 空隊列 A進隊 B C進隊 0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7 A退隊 B退隊 0 1 2 3 4 5 6 7 D E F G H進隊 隊滿 front B C rear A front B C rear front C rear D E F G H I 41 隊空條件 front rear 初始化時 front rear 隊滿條件 front rear 1 N N maxsize 隊列長度 即數據元素個數 L N rear front N 令front指向實元素 rear指向空閑元素 問3 在具有N個單元的循環隊列中 隊滿時共有多少個元素 N 1個 6 問1 左圖中隊列maxsizeN 問2 左圖中隊列長度L 5 42 r f n f r n n r f n r f n 要分析4種公式哪種最合理 當r f時 A 合理 當r f時 C 合理 答 綜合2種情況 以 D 的表達最為合理 例2 在一個循環隊列中 若約定隊首指針指向隊首元素的前一個位置 那么 從循環隊列中刪除一個元素時 其操作是先 移動隊首指針 取出元素 后 例1 數組 n 用來表示一個循環隊列 f為當前隊列頭元素的前一位置 r為隊尾元素的位置 假定隊列中元素的個數小于n 計算隊列中元素的公式為 43 例3 一循環隊列如下圖所示 若先刪除4個元素 接著再插入4個元素 請問隊頭和隊尾指針分別指向哪個位置 解 由圖可知 隊頭和隊尾指針的初態分別為front 1和rear 0 刪除4個元素后f 5 再插入4個元素后 r 0 4 6 4 rear 4 44 2 循環隊列的操作實現 初始化操作 注意 這里的sq為變量 算法voidINITQUEUE sequeue sq sq sequeue malloc sizeof sequeue sq front 0 sq rear 0 頭 尾指針指向位置0 初始化操作算法voidINITQUEUE sequeuesq sq front 0 sq rear 0 頭 尾指針指向位置0 45 判隊空操作算法intEMPTYQUEUE sequeue sq 判斷循環隊列是否為空 if sq rear sq front return1 elsereturn0 46 入隊操作算法voidENQUEUE sequeue 47 出隊操作算法datatypeDEQUEUE sequeue sq datatypee 若隊列非空從隊頭刪除一個元素 if EMPTYQUEUE sq returnNULL 隊列空 else e sq data sq front sq front sq front 1 max return e 48 取隊頭元素算法datatypeGETFIRST sequeue sq if EMPTYQUEUE sq returnNULL elsereturn sq data sq front 49 停車車管理系統 設停車場內只有一個可停放n輛汽車的狹長通道 且只有一個大門可供汽車進出 汽車在停車場內按車輛到達時間的先后順序 依次由北向南排列 大門在最南端 最先到達的第一輛車停放在車場的最北端 若車場內已停滿n輛汽車 則后來的汽車只能在門外的便道上等候 一旦有車開走 則排在便道上的第一輛車即可開入 當停車場內某輛車要離開時 在它之后開入的車輛必須先退出車場為它讓路 待該輛車開出大門外 其它車輛再按原次序進入車場 每輛停放在