第3章棧與隊列(已修改).ppt

1 57 2 第3章棧和隊列 棧和隊列被稱為操作受限的線性表 本章介紹棧和隊列的邏輯結(jié)構(gòu)和存儲結(jié)構(gòu) 以及棧和隊列的基本運算以及實現(xiàn)算法 3 a1 a2 ai 1 ai ai 1 an 3 1棧 只允許在線性表的一端進(jìn)行插入和刪除操作的線性表允許插入和刪除的一端稱為棧頂 top 另一端稱為棧底 bottom 特點后進(jìn)先出 LIFO 4 棧的基本操作INITSTACK s 構(gòu)造一個空棧s STACKEMPTY s 判斷s是否為空棧 若s為空棧 返回1 否則返回0 PUSH s x 進(jìn)棧操作 在棧s頂部插入一個新的元素x POP s x 退棧操作 若s非空 刪除s中的棧頂元素 并返回該元素 5 GETTOP s 取棧s的棧頂元素 若s非空 返回棧頂元素 但與POP s x 的區(qū)別是GETTOP s 不改變棧的狀態(tài) CLEASTACK s 將棧s清為空棧 STACKLENGTH s 求棧的長度 返回棧s中的元素個數(shù) 6 棧的表示和實現(xiàn) 由于棧是運算受限的線性表 因此線性表的存儲結(jié)構(gòu)對棧也適應(yīng) 1 順序棧棧的順序存儲結(jié)構(gòu) 順序棧 可以將棧底位置設(shè)置在數(shù)組的低地址端點 棧頂位置是隨著進(jìn)棧和退棧操作而變化的 故需用一個整型變量top 指明當(dāng)前棧頂?shù)奈恢?同樣將data數(shù)組和top封裝在一個結(jié)構(gòu)中 順序棧的類型描述如下 defineMAXSIZE1024typedefstructSeqStack datatypedata MAXSIZE inttop SeqStack 7 8 bottom bottom A A B C D E A B 棧操作圖示 A進(jìn)棧 BCDE進(jìn)棧 EDC出棧 C D E 棧的特點后進(jìn)先出LIFO 入棧與出棧 9 約定棧頂指針指向向棧頂元素的位置 順序棧的圖示 ?？?棧滿 Top 1 Top maxlen 1 10 2 順序棧的基本運算算法 1 初始化棧voidINITSTACK seqstack s 創(chuàng)建一個空棧由指針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 順序棧的不足 存在棧滿以后就不能再進(jìn)棧的問題 這是因為用了定長的數(shù)組存儲棧的元素 解決方法 使用鏈?zhǔn)酱鎯Y(jié)構(gòu) 17 2 鏈棧棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 也稱鏈棧 沒有頭結(jié)點的單鏈表 其各結(jié)點的結(jié)構(gòu)與單鏈表中的結(jié)點結(jié)構(gòu)完全相同 如圖所示 在前面學(xué)習(xí)了線性鏈表的插入刪除操作算法 不難寫出鏈?zhǔn)綏３跏蓟?進(jìn)棧 出棧等操作的算法 結(jié)點結(jié)構(gòu)定義 Typedefstructnode elemtypedata structnode next node pointer 18 1 初始化棧Voidinitstack pointers s null 19 進(jìn)棧前進(jìn)棧后 2 進(jìn)棧 20 進(jìn)棧算法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 特性先進(jìn)先出 FIFO FirstInFirstOut 24 隊列的基本運算 隊列初始化 Init Queue q 初始條件 隊q不存在 操作結(jié)果 構(gòu)造一個空隊 入隊操作 In Queue q x 初始條件 隊q存在 操作結(jié)果 對已存在的隊列q 插入一個元素x到隊尾 隊發(fā)生變化 出隊操作 Out Queue q x 初始條件 隊q存在且非空操作結(jié)果 刪除隊首元素 并返回其值 隊發(fā)生變化 讀隊頭元素 Front Queue q x 初始條件 隊q存在且非空操作結(jié)果 讀隊頭元素 并返回其值 隊不變 判隊空操作 Empty Queue q 初始條件 隊q存在操作結(jié)果 若q為空隊則返回為1 否則返回為0 25 隊列的存儲結(jié)構(gòu)及操作實現(xiàn) 1 鏈隊列用鏈表表示的隊列簡稱為鏈隊列 在一個鏈隊列中需設(shè)定兩個指針 頭指針和尾指針 分別指向隊列的頭和尾 給鏈隊列添加一個頭結(jié)點 并設(shè)定頭指針指向頭結(jié)點 空隊列的判定條件為頭指針和尾指針都指向頭結(jié)點 26 typedefstructnode datatypedata structnode next QNode 鏈隊結(jié)點的類型 typedefstruct QNnode front rear LQueue 將頭尾指針封裝在一起的鏈隊 27 討論 空鏈隊的特征 怎樣實現(xiàn)鏈隊的入隊和出隊操作 鏈隊會滿嗎 front rear 一般不會 因為刪除時有free動作 除非內(nèi)存不足 入隊 尾部插入 rear next S rear S 出隊 頭部刪除 front next p next 鏈隊示意圖 28 刪除 一個元素 添加一個元素 e Q front Q rear 隊頭 隊尾 Q rear 注意 linkqueueQ 29 鏈隊列的主要運算算法 置空隊列voidINITQUEUE linkqueue q 構(gòu)造一個只含頭結(jié)點的空隊列 q linkqueue malloc sizeof linkqueue q rear q front 尾指針指向頭結(jié)點 q front next NULL 頭結(jié)點指針為空 置空隊列voidINITQUEUE linkqueueq 構(gòu)造一個只含頭結(jié)點的空隊列 q rear q front 尾指針指向頭結(jié)點 q front next NULL 頭結(jié)點指針為空 注意 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 順序隊列隊列的順序存儲結(jié)構(gòu)可以簡稱為順序隊列 用一組地址連續(xù)的存儲單元依次存放隊列中的數(shù)據(jù)元素 設(shè)立兩個指示器 指向隊頭元素的指示器front 指向隊尾的元素位置的指示器rear 35 a 線性隊列 e2 c e2入隊 e0 e1出隊 rear 3 front e0 e1 b rear front b e0 e1入隊 隊空時 令rear front 0 當(dāng)有新元素入隊時 尾指針加1 當(dāng)有元素出隊時 頭指針加1 故在非空隊列中 頭指針始終指向隊頭元素位置 而尾指針始終指向隊尾元素的下一位置 36 順序隊列的類型定義如下 definemax100 隊列最大長度 typedefstructsequeue datatypedata max intfront intrear sequeue 順序隊列類型 sequeue sq sq為順序隊列類型的指針 37 順序隊列的缺點 當(dāng)前隊列并未占滿 但隊列中元素出隊后讓出的實際可用空間卻不能得以使用 因此把這種溢出現(xiàn)象稱為 假溢出 解決辦法之一 將隊列元素存放數(shù)組首尾相接 形成循環(huán) 環(huán)形 隊列 38 循環(huán)隊列 在將順序隊列的存儲區(qū)假想為一個環(huán)狀的空間 假想q queue 0 接在q queue MAXNUM 1 的后面 當(dāng)發(fā)生假溢出時 將新元素插入到第一個位置上 入列和出列仍按 先進(jìn)先出 的原則進(jìn)行 首指針front和尾指針rear沿環(huán)順時針移動 只要尾指針rear不與首指針相遇 該隊列就可繼續(xù)操作 稱這種隊列為循環(huán)隊列 sequeue sq sq為順序隊列類型的指針 sqq q為順序隊列sq類型 39 循環(huán)隊列為隊列空時 有q front q rear q front rear 隊列滿時 也有q front q rear 因此僅憑q front q rear不能判定隊列是空還是滿 規(guī)定循環(huán)隊列中少用一個元素空間 以尾指針在頭指針的前一位置作為隊列滿的條件 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進(jìn)隊 B C進(jìn)隊 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進(jìn)隊 隊滿 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 隊列長度 即數(shù)據(jù)元素個數(shù) L N rear front N 令front指向?qū)嵲?rear指向空閑元素 問3 在具有N個單元的循環(huán)隊列中 隊滿時共有多少個元素 N 1個 6 問1 左圖中隊列maxsizeN 問2 左圖中隊列長度L 5 42 r f n f r n n r f n r f n 要分析4種公式哪種最合理 當(dāng)r f時 A 合理 當(dāng)r f時 C 合理 答 綜合2種情況 以 D 的表達(dá)最為合理 例2 在一個循環(huán)隊列中 若約定隊首指針指向隊首元素的前一個位置 那么 從循環(huán)隊列中刪除一個元素時 其操作是先 移動隊首指針 取出元素 后 例1 數(shù)組 n 用來表示一個循環(huán)隊列 f為當(dāng)前隊列頭元素的前一位置 r為隊尾元素的位置 假定隊列中元素的個數(shù)小于n 計算隊列中元素的公式為 43 例3 一循環(huán)隊列如下圖所示 若先刪除4個元素 接著再插入4個元素 請問隊頭和隊尾指針分別指向哪個位置 解 由圖可知 隊頭和隊尾指針的初態(tài)分別為front 1和rear 0 刪除4個元素后f 5 再插入4個元素后 r 0 4 6 4 rear 4 44 2 循環(huán)隊列的操作實現(xiàn) 初始化操作 注意 這里的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 判斷循環(huán)隊列是否為空 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 停車車管理系統(tǒng) 設(shè)停車場內(nèi)只有一個可停放n輛汽車的狹長通道 且只有一個大門可供汽車進(jìn)出 汽車在停車場內(nèi)按車輛到達(dá)時間的先后順序 依次由北向南排列 大門在最南端 最先到達(dá)的第一輛車停放在車場的最北端 若車場內(nèi)已停滿n輛汽車 則后來的汽車只能在門外的便道上等候 一旦有車開走 則排在便道上的第一輛車即可開入 當(dāng)停車場內(nèi)某輛車要離開時 在它之后開入的車輛必須先退出車場為它讓路 待該輛車開出大門外 其它車輛再按原次序進(jìn)入車場 每輛停放在