第3章 棧與隊列

第3章棧和隊列數(shù)據(jù)結(jié)構(gòu)案例教程Page

2案例提出——迷宮問題迷宮問題是取自心理學的一個經(jīng)典實驗。在該實驗中，把一只老鼠從一個無頂大盒子的門中放入，在盒子中設(shè)置了許多墻，對行進方向形成了多處阻擋。盒子僅有一個出口，在出口處放置以塊奶酪，吸引老鼠在迷宮中尋找道路以到達出口。對同一只老鼠重復進行上述實驗，一直到老鼠從入口走到出口，而不走錯一步。老鼠經(jīng)過多次試驗最終學會走通迷宮的路線。設(shè)計一個計算機程序?qū)θ我庠O(shè)定的矩形迷宮如下圖所示，求出一條從入口到出口的通路，或得出沒有通路的結(jié)論。Page

33.2知識點學習

3.2.1棧棧是一種特殊的線性表，用途十分廣泛。將遞歸算法轉(zhuǎn)換成非遞歸算法時常常會用到棧，實現(xiàn)二叉樹的算法中也會使用棧。棧是一種只能在一端進行插入或刪除的線性表。表中允許進行插入、刪除操作的一端稱為棧頂（top），表的另一端稱為棧底（bottom）。當棧中沒有數(shù)據(jù)元素時，稱為空棧。棧的插入操作通常稱為進?；蛉霔＃瑮５膭h除操作通常稱為退棧或出棧。Page

43.2.1.2棧的順序存儲結(jié)構(gòu)及其基本運算實現(xiàn)#defineMaxsize100;//最多元素個數(shù)typedefintElemType;//數(shù)據(jù)類型typedefstruct{ ElemTypeelem[MaxSize]; inttop; //棧頂指針}SqStack;//順序棧類型定義Page

5入棧

Page

63.2.1.3棧的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn)Page

7（鏈棧中數(shù)據(jù)結(jié)點的類型LinkStack定義如下：typedefintElemType;typedefstructlinknode{ElemTypedata;//數(shù)據(jù)域structlinknode*next;//指針域}LinkStack;Page

83.2.1.4棧的應用舉例1、算術(shù)表達式的前綴與后綴表達（任何一個表達式都是由操作數(shù)、運算符或界限符組成的。在表達式求值問題中的操作數(shù)可以是常數(shù)、被說明為變量或常量的標識符、表達式；運算符指的是“+”、“-”、“*”、“/”；界限符指的是括號等字符。在本例中的表達式求值問題就是：對于一個包含“+”、“-”、“*”、“/”、正整數(shù)和圓括號的合法數(shù)學表達式，計算該表達式的運算結(jié)果。Page

9前綴轉(zhuǎn)后綴算法演示Page

10后綴轉(zhuǎn)前綴算法演示Page

11練習A*b-cA*b+(c-d*e)/fPage

12棧解決迷宮問題算法演示Page

133.2.2隊列隊列也具有廣泛的應用。特別是在操作系統(tǒng)資源分配和排隊論中大量地使用隊列。本節(jié)介紹隊列的定義、隊列的存儲結(jié)構(gòu)和隊列的應用。Page

143.2.2.2隊列的順序存儲結(jié)構(gòu)及其基本運算的實現(xiàn)順序隊列類型SqQueue定義如下：#defineMaxSize100typedefintElemType;typedefstruct{ElemTypeelem[MaxSize];intfront,rear;//隊首和隊尾指針}SqQueue;Page

15隊列操作Page

16循環(huán)隊列Page

17循環(huán)隊列滿和空指針判斷沖突Page

183.2.2.3隊列的鏈式存儲結(jié)構(gòu)及其基本運算的實現(xiàn)隊列的鏈式存儲結(jié)構(gòu)是僅在表頭刪除和表尾插入的單鏈表，因此一個棧隊列需要使用兩個指針：指向隊頭元素的隊首指針front和指向隊尾元素的隊尾指針rear。用于存儲隊列的單鏈表簡稱鏈隊。如圖3.11所示的鏈隊列。Page

19鏈隊中數(shù)據(jù)結(jié)點的類型QNode定義typedefintElemType;typedefstructqnode{ElemTypedata;structqnode*next;}QNode;//鏈隊數(shù)據(jù)結(jié)點類型定義Page

20一個鏈隊的動態(tài)變化過程Page

213.2.2.4隊列的應用舉例

求解報數(shù)問題設(shè)有n個人站成一排，從左向右的編號分別為1~n，現(xiàn)在從左往右報數(shù)“1，2，1，2…”，數(shù)到“1”的人出列，數(shù)到“2”的立即站到隊伍的最右端。報數(shù)過程反復進行，直到n個人都出列為止。要求給出他們的出列順序。Page

223.3案例解決

3.3.1用棧來解決迷宮問題【算法思路】用棧來解決迷宮問題，本質(zhì)上是一個深度優(yōu)先算法（在教材的樹和圖時將學到）。我們設(shè)置一個數(shù)組maze來表示迷宮，其中每個元素表示一個方塊的狀態(tài)，為0時表示對應方塊是通道，為1時表示對應方塊是墻，不可走。為了算法方便，在迷宮外圍加了一道圍墻。這樣，在不影響迷宮結(jié)構(gòu)的前提下，原數(shù)組中的每個方塊都有4個方向可判斷。本算法用到的數(shù)據(jù)結(jié)構(gòu)是順序棧存儲結(jié)構(gòu)，采用“窮舉求解”的方法，即從入口出發(fā)，順某一方向向前試探，若能走通，則繼續(xù)往前走，否則，原路退回，換一個方向再繼續(xù)試探，直至所有可能的通路都試探完為止。為了保證在任何位置上都能沿原路退回（稱為回溯），需要用一個后進先出的棧來保存入口到當前位置的路徑。Page

233.3.2用隊列來解決迷宮問題【算法思路】用隊列解決迷宮問題，本質(zhì)上是一個廣度優(yōu)先算法（在教材的樹和圖章節(jié)中將學到）。這里不能