第三章棧和隊列

第三章棧和隊列 2 教學(xué)目標(biāo)掌握棧和隊列的基本概念 ADT描述方法 掌握棧的順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的基本操作及其實現(xiàn)算法 掌握循環(huán)隊列和鏈隊列的基本操作實現(xiàn)算法 學(xué)會運用棧和隊列解決實際問題 3 1棧3 2棧的應(yīng)用舉例3 4隊列 3 棧和隊列是兩種常用的數(shù)據(jù)類型 棧和隊列也是兩種特殊的線性表 它們是運算時要受到某些限制的線性表 故也稱為限定性的數(shù)據(jù)結(jié)構(gòu) 通常稱 棧和隊列是限定插入和刪除只能在表的 端點 進(jìn)行的線性表 4 如果所有的操作均被限定在線性表的一端 那么就稱該線性表為棧 Stack 如果線性表的一端僅允許插入元素 而另一端僅允許刪除元素 那么該線性表被稱為隊列 Queue 棧和隊列是兩種在計算機程序設(shè)計中廣泛運用的線性表 5 一 棧的概念 3 1棧的概念 3 1棧 1 棧的定義 棧 限定只能在表的一端進(jìn)行插入和刪除的特殊的線性表設(shè)棧s a1 a2 ai an 其中a1是棧底元素 an是棧頂元素 出棧 棧頂 top 允許插入和刪除的一端 約定top始終指向新數(shù)據(jù)元素將存放的位置 棧底 bottom 不允許插入和刪除的一端 插入 即進(jìn)棧 在n 1位置插入 刪除 即出棧 刪除第n位置元素 棧的特點后進(jìn)先出 6 2 棧的類型定義 抽象數(shù)據(jù)類型棧的定義如下 P44 3 1棧的概念 7 3 1棧的表示和實現(xiàn) 二 棧的表示和實現(xiàn) 1 順序存儲和實現(xiàn) 順序棧 用一組連續(xù)的存儲單元存放自棧底到棧頂?shù)臄?shù)據(jù)元素 一般用一維數(shù)組表示 設(shè)置一個簡單變量top指示棧頂位置 稱為棧頂指針top 約定棧頂指針指向棧頂元素的下一個位置 8 進(jìn)棧 A 出棧 B C D E F 棧滿 ?？?棧頂指針top 指向?qū)嶋H棧頂后的空位置 初值為0 當(dāng)棧滿時再做進(jìn)棧運算必定產(chǎn)生空間溢出 簡稱 上溢 overflow 當(dāng)棧空時再做退棧運算也將產(chǎn)生溢出 簡稱 下溢 underflow 3 1棧的表示實現(xiàn) 9 上溢是一種出錯狀態(tài) 應(yīng)該設(shè)法避免之 下溢則可能是正?，F(xiàn)象 因為棧在程序中使用時 其初態(tài)或終態(tài)都是空棧 所以下溢常常用來作為程序控制轉(zhuǎn)移的條件 順序棧的操作算法 順序棧的類型定義 棧的順序存儲表示 defineSTACK NINT SIZE100 存儲空間初始分配量 defineSTACKINCREMENT10 存儲空間分配增量typedefstruct SElemType base 在棧構(gòu)造之前和銷毀之后 bade的值為NULLSElemType top 棧頂指針intstacksize 當(dāng)前已分配的存儲空間 以元素為單位 SqStack 10 11 3 1棧的表示和實現(xiàn) 2 判斷棧是否為滿 3 判斷棧是否為空 12 3 1棧的表示和實現(xiàn) 4 取棧頂元素 13 3 1棧的表示和實現(xiàn) 5 進(jìn) 壓 棧push StatusPush SqStack push 分析演示 14 3 1棧的表示和實現(xiàn) statusPop SqStack Pop 6 出棧pop 分析演示 15 例1 如書中P44頁圖3 1 b 所示鐵道車廂調(diào)度 1 如果進(jìn)站的車廂序列為123 則可能得到的出站車廂序列是什么 2 如果進(jìn)站的車廂序列為123456 則能否得到435612和135426的出站序列 16 例2 如下列算法 執(zhí)行完后能輸出什么結(jié)果 Voidmain stacks charx y initstack s x c y k push s x push s a push s y pop s x push s t push s x pop s x push s s while Stackempty s pop s y printf y printf x c a y 由上算法分析 設(shè)定了棧S 棧S的元素類型為char push為進(jìn)棧 pop為出棧 棧S t c s x k 17 例3 棧S中存放了已知數(shù)組a 2 4 6 8 10 中的元素 寫一算法將數(shù)組中的值逆置 即 a 1 的值2與a 5 的值10互換 如下圖 Statusalgo1 stacks inti n a 5 n 0 While stackempty s n pop s a n for i 1 i 5 i push s a i 18 2 鏈?zhǔn)酱鎯蛯崿F(xiàn) 3 1棧的表示和實現(xiàn) 鏈棧 即棧的鏈?zhǔn)酱鎯Y(jié)構(gòu) 與線性鏈表類似 如圖所示 注意 鏈棧中指針的方向 19 3 1棧的表示和實現(xiàn) 鏈棧的操作算法 鏈棧的類型定義 typedefstructLNode 結(jié)點類型ElemTypedata structLNode next Lnode Linkstack LinkstackS StatusInitLStack Linkstack InitLStack 1 建立一個空棧 20 StatusGettopLStack Linkstack GettopLStack 2 取棧頂元素 3 1棧的表示和實現(xiàn) 21 StatusPushLStack Linkstack PushLStack 3 進(jìn) 壓 棧push 22 3 1棧的表示和實現(xiàn) StatusPopLStack Linkstack PopLStack 4 出棧push 23 3 1棧的表示和實現(xiàn) 例4 在棧頂指針為HS的鏈棧中 寫出計算該鏈棧中結(jié)點個數(shù)的函數(shù) Intcount LinkListHS LinkListp intn 0 p HS While P n p p next return n 24 例若進(jìn)棧序列為3 5 7 9 進(jìn)棧過程中可以出棧 則不可能的一個出棧次序是 7 5 3 9 b 9 7 5 3 c 7 5 9 3 d 9 5 7 3 例用一維數(shù)組設(shè)計棧 初態(tài)是?？?top 0 現(xiàn)有輸入序列是a b c d 經(jīng)過push push pop push pop push操作后 輸出序列是 棧頂指針是 b c 2 d 25 小結(jié)1棧是限定僅能在表尾一端進(jìn)行插入 刪除操作的線性表 2棧的元素具有后進(jìn)先出的特點 3棧頂元素的位置由一個稱為棧頂指針的變量指示 進(jìn)棧 出棧操作要修改棧頂指針 26 3 2棧的應(yīng)用舉例 例1數(shù)制轉(zhuǎn)換對于輸入的任意一個非負(fù)十進(jìn)制數(shù) 顯示輸出與其等值的八進(jìn)制數(shù) 3 2棧的應(yīng)用 例把十進(jìn)制數(shù)159轉(zhuǎn)換成八進(jìn)制數(shù) 27 3 2棧的應(yīng)用 voidconversion InitStack s 建空棧scanf d 28 3 2棧的應(yīng)用 例2括號匹配的檢驗 假設(shè)在表達(dá)式中 或 等為正確的格式 或 或 均為不正確的格式 則檢驗括號是否匹配的方法 可用 期待的急迫程度 這個概念來描述 例如 考慮下列括號序列 12345678 分析可能出現(xiàn)的不匹配的情況 到來的右括弧并非是所 期待 的 到來的是 不速之客 直到結(jié)束 也沒有到來所 期待 的括弧 29 3 2棧的應(yīng)用 算法的設(shè)計思想 1 凡出現(xiàn)左括弧 則進(jìn)棧 2 凡出現(xiàn)右括弧 首先檢查棧是否空若棧空 則表明該 右括弧 多余 否則和棧頂元素比較 若相匹配 則 左括弧出棧 否則表明不匹配 3 表達(dá)式檢驗結(jié)束時 若?？?則表明表達(dá)式中匹配正確 否則表明 左括弧 有余 30 3 2棧的應(yīng)用 Statusmatching string 31 例3行編輯程序問題 在用戶輸入一行的過程中 允許用戶輸入出差錯 并在發(fā)現(xiàn)有誤時可以及時更正 合理的作法是 設(shè)立一個輸入緩沖區(qū) 用以接受用戶輸入的一行字符 然后逐行存入用戶數(shù)據(jù)區(qū) 并假設(shè) 為退格符 為退行符 假設(shè)從終端接受了這樣兩行字符 whli ilr e s s outcha putchar s 則實際有效的是下列兩行 while s putchar s 3 2棧的應(yīng)用 32 while ch EOF 從終端接收下一個字符 ClearStack S 重置S為空棧if ch EOF ch getchar while ch EOF EOF為全文結(jié)束符 將從棧底到棧頂?shù)淖址麄魉椭琳{(diào)用過程的數(shù)據(jù)區(qū) 3 2棧的應(yīng)用 33 例4表達(dá)式求值 表達(dá)式的構(gòu)成操作數(shù) 運算符 界符 如括號 表達(dá)式的求值 按照四則運算法則 例5 6 1 2 4計算過程為 5 6 1 2 4 5 6 3 4 5 18 4 23 4 19 1 2 3 4 3 2棧的應(yīng)用 表達(dá)式求值是程序設(shè)計語言編譯中的一個最基本問題 它的實現(xiàn)需要借助棧來完成 介紹一種簡單直觀 廣為使用的算法 即 算符優(yōu)先法 34 表達(dá)式中任何相鄰運算符c1 c2的優(yōu)先關(guān)系有 c1c2 c1的優(yōu)先級高于c2 注 c1c2是相鄰算符 c1在左 c2在右 算符間的優(yōu)先關(guān)系表 3 2棧的應(yīng)用 35 基本思想 實現(xiàn)算符優(yōu)先算法 可以使用兩個工作棧 一個稱為OPTR 用以寄存運算符 另一個稱為OPND 用以寄存操作數(shù)或運算結(jié)果 1 首先置操作數(shù)棧為空棧 表達(dá)式起始符 為運算符的棧底元素 2 依次讀入表達(dá)式中每個字符 若是操作數(shù)則進(jìn)OPND棧 若是運算符 則和OPTR棧的棧頂運算符比較 高進(jìn)棧 否則低于或相同則作相應(yīng)操作 直至整個表達(dá)式求值完畢 即OPTR棧的棧頂元素和當(dāng)前讀入的字符均為 例 S 4 2 3 10 5 36 如下所示 操作過程 例如 利用算符優(yōu)先算法對算術(shù)表達(dá)式3 7 2 求值 37 OperandTypeEvaluateExpression 算術(shù)表達(dá)式求值設(shè)OPTR和OPND分別為運算符棧和運算數(shù)棧 InitStack OPET Push OPTR initStack OPND c getchar while c GetTop OPTR if In c OP Push OPND c c getchar 不是運算符則進(jìn)棧elseswitch Precede GetTop OPTR c case 棧頂元素優(yōu)先權(quán)低Push OPTR c c getch break 算法描述P53 38 case 脫括號并接收下一個字符Pop OPTR x c getch break case 退棧并將運算結(jié)果入棧Pop OPTR theta Pop OPND b Pop OPND a Push OPND Operate a theta b break swith whilereturnGetTop OPND EvaluateExpression 例 地圖四染色問題 四染色 定理是計算機科學(xué)中著名的定理之一 使地圖中相鄰的國家或行政區(qū)域不重色 最少可用四種顏色對地圖著色 證明此定理的結(jié)論 利用棧采用回溯法對地圖著色 思想 對每個行政區(qū)編號 1 7 對顏色編號 a b c d 從第一號行政區(qū)開始逐一染色 每一個區(qū)域逐次用四種顏色進(jìn)行試探 若所取顏色與周圍不重 則用棧記下來該區(qū)域的色數(shù) 否則依次用下一色數(shù)進(jìn)行試探 若出現(xiàn)a d均與周圍發(fā)生重色 則需退棧回溯 修改當(dāng)前棧頂?shù)纳珨?shù) 40 1 2 4 5 6 7 3 1 粉色2 黃色3 紅色4 綠色 41 例 迷宮求解 通常用的是 窮舉求解 的方法 42 求迷宮路徑算法的基本思想是 若當(dāng)前位置 可通 則納入路徑 繼續(xù)前進(jìn) 若當(dāng)前位置 不可通 則后退 換方向繼續(xù)探索 若四周 均無通路 則將當(dāng)前位置從路徑中刪除出去 43 設(shè)定當(dāng)前位置的初值為入口位置 do 若當(dāng)前位置可通 則 將當(dāng)前位置插入棧頂 若該位置是出口位置 則算法結(jié)束 否則切換當(dāng)前位置的東鄰方塊為新的當(dāng)前位置 否則 while 棧不空 求迷宮中一條從入口到出口的路徑的算法 44 若棧不空且棧頂位置尚有其他方向未被探索 則設(shè)定新的當(dāng)前位置為 沿順時針方向旋轉(zhuǎn)找到的棧頂位置的下一相鄰塊 若棧不空但棧頂位置的四周均不可通 則 刪去棧頂位置 從路徑中刪去該通道塊若棧不空 則重新測試新的棧頂位置 直至找到一個可通的相鄰塊或出棧至?？?若棧空 則表明迷宮沒有通路 45 3 4隊列一 隊列的概念二 隊列的順序存儲和實現(xiàn)三 隊列的鏈?zhǔn)酱鎯蛯崿F(xiàn) 46 一 隊列的概念定義 隊列是限定只能在表的一端進(jìn)行插入 在表的另一端進(jìn)行刪除的線性表隊尾 rear 允許插入的一端隊頭 front 允許刪除的一端隊列特點 先進(jìn)先出 FIFO 雙端隊列 47 a1a2a3an 入隊列 隊頭 隊尾 出隊列 隊列的示意圖 隊列的特點先進(jìn)先出 第一個入隊的元素在隊頭最后一個入隊的元素在隊尾第一個出隊的元素為隊頭元素最后一個出隊的元素為隊尾元素 48 隊列的類型定義 ADTQueue 數(shù)據(jù)對象 D ai ai ElemSet i 1 2 n n 0 數(shù)據(jù)關(guān)系 R1 ai 1 ai D i 2 n 約定其中a1端為隊列頭 an端為隊列尾 基本操作 P59 ADTQueue 隊列的主要運算 1 設(shè)置一個空隊列 2 插入一個新的隊尾元素 稱為進(jìn)隊 3 刪除隊頭元素 稱為出隊 4 讀取隊頭元素 49 二 隊列的順序存儲和實現(xiàn) J1 J2 J3 設(shè)兩個指針front rear 約定 Rear始終指向隊尾元素的下一個位置 front始終指向隊頭元素 空隊列條件 front rear入隊列 sq rear x 出隊列 x sq front 50 存在問題設(shè)數(shù)組維數(shù)為M 則 當(dāng)front 1 rear M 1時 再有元素入隊發(fā)生溢出 真溢出當(dāng)front 1 rear M 1時 再有元素入隊發(fā)生溢出 假溢出解決方案 循環(huán)隊列 51 2 循環(huán)隊列基本思想 把隊列設(shè)想成環(huán)形 讓sq 0 接在sq M 1 之后 若rear 1 M 則令rear 0 實現(xiàn) 利用 模 運算入隊 rear rear 1 M sq rear x 出隊 front front 1 M x sq front 隊滿 隊空判定條件 52 隊空 front rear隊滿 front rear 解決方案 1 另外設(shè)一個標(biāo)志以區(qū)別隊空 隊滿2 少用一個元素空間 隊空 front rear隊滿 rear 1 M front 53 循環(huán)隊列類型定義 defineMAXQSIZE100 最大隊列長度typedefstruct QElemType base 動態(tài)分配存儲空間intfront 頭指針 若隊列不空 指向隊列頭元素intrear 尾指針 若隊列不空 指向 隊列尾元素的下一個位置 SqQueue 54 循環(huán)隊列的主要運算 1 初始化操作功能 建一個空隊列Q StatusInitQueue SqQueue 55 2 入隊操作功能 將元素x插入隊尾 算法 StatusEnQueue SqQueue 動畫演示 56 3 出隊操作功能 刪除隊頭元素 StatusDeQueue SqQueue 動畫演示 57 三 隊列的鏈?zhǔn)酱鎯蛯崿F(xiàn) front rear 空鏈隊列 鏈隊列圖示 1 鏈隊列 58 2 鏈隊列的類型定義結(jié)點類型 typedefstructQNode QElemTypedata structQNode next QNode QueuePtr 鏈隊列類型 typedefstruct QueuePtrfront 隊頭指針QueuePtrrear 隊尾指針 LinkQueue 59 鏈隊列的主要運算 1 初始化操作功能 建一個空隊列Q StatusInitQueue LinkQueue 60 2 入隊操作功能 將元素x插入隊尾 p data e p next NULL Q rear next p Q rear p 61 算法 StatusEnQueue LinkQueue 62 3 出隊操作功能 刪除隊頭元素 p Q front next e p data Q front next p next 63 算法 StatusDeQueue LinkQueue 64 小結(jié)1隊列是限定僅能在表尾一端進(jìn)行插入 表頭一端刪除操作的線性表 2隊列中的元素具有先進(jìn)先出的特點 3隊頭 隊尾元素的位置分別由稱為隊頭指針和隊尾指針的變量指示 4入隊操作要修改隊尾指針 出隊操作要修改隊頭指針 65 例 循環(huán)隊列SQ采用數(shù)組空間SQ base 0 n 1 存放其元素值 已知其頭尾指針分別是front和rear 則判定此循環(huán)隊列Q為空的條件是 A Q rear Q front nB Q rear Q front 1 nC Q rear Q frontD Q rear Q front 1 C 例 循環(huán)隊列SQ采用數(shù)組空間SQ base 0 n 1 存放其元素值 已知其頭尾指針分別是front和rear 則判定此循環(huán)隊列Q為滿的條件是 A Q rea Q frontB Q front Q rearC Q front Q rear 1 nD Q front Q rear 1 n C 66 例 循環(huán)隊列用數(shù)組A 0 m 1 存放其元素值 已知其頭尾指針分別是front和rear則當(dāng)前隊列中的元素個數(shù)是 A rear front m m B rear front 1 C rear front 1 D rear front B 例 棧和隊列的共同點是 A 都是先進(jìn)后出 B 都是先進(jìn)先出 C 只允許在端點處插入和刪除元素 D 沒有共同點 C 67 例 以數(shù)組Q 0 m 1 存放循環(huán)隊列中的元素 變量rear和qulen分別指示循環(huán)隊列中隊尾元素的實際位置和當(dāng)前隊列中元素的個數(shù) 隊列第一個元素的實際位置是 A rear qulen B rear qulen m C m qulen D 1 rear m qulen m D 68 例 若在一個大小為6的數(shù)組上實現(xiàn)循環(huán)隊列 且當(dāng)前rear和front的值分別為0和3 當(dāng)從隊列中刪除一個元素 再加入兩個元素后 rear和front的值分別是 例 判定一個鏈隊列Q 最多元素個數(shù)為N 為空的條件是 A Q front Q rearB Q front Q rearC Q