1、使用堆棧解決編程問題數據結構(C#語言版)解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)目標目標在本章中,你將學到:識別堆棧的特性實施堆棧運用堆棧來解決編程問題解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)學習情境學習情境用堆棧解決火車車廂重排問題的編程用堆棧解決火車車廂重排問題的編程問題描述問題描述一列貨運列車共有n節車廂，每節車廂將停放在不同的車站。假定n個車站的編號分別為1 -n，貨運列車按照第n站至第1站的次序經過這些車站。車廂的編號與它們的目的地相同。為了便于從列車上卸掉相應的車廂，必須重新排列車廂，使各車廂從前至后按編號1到n的次

2、序排列。當所有的車廂都按照這種次序排列時，在每個車站只需卸掉最后一節車廂即可。我們在一個轉軌站里完成車廂的重排工作，在轉軌站中有一個入軌、一個出軌和k個緩沖鐵軌（位于入軌和出軌之間）。圖3.1a 給出了一個轉軌站，其中有k= 3個緩沖鐵軌H1，H2和H3。開始時，n節車廂的貨車從入軌處進入轉軌站，轉軌結束時各車廂從右到左按照編號1至編號n的次序離開轉軌站（通過出軌處）。在圖3.1a 中，n= 9，車廂從后至前的初始次序為5，8，1，7，4，2，9，6，3。圖3.1b 給出了按所要求的次序重新排列后的結果。解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)學習情境學習情境用

3、線性表解決學生成績表的編程用線性表解決學生成績表的編程問題描述問題描述(續續)根據上面的描述，編寫程序實現下面的功能：編寫一算法實現火車車箱的重排；編寫程序模擬圖3.1所示的具有9節車廂的火車入軌和出軌的過程。程序主界面設計如圖3.2所示。解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)讓我們來玩Rummy（拉米紙牌）的游戲。堆棧堆棧777777776666666666666666認識堆棧認識堆棧分析堆棧的邏輯結構分析堆棧的邏輯結構解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)堆棧(Stack)是一種特殊的線性表,是一種只允許在表的一端進行插入

4、或刪除操作的線性表。 堆棧就是一個只能訪問其末尾數據的數據集，這一端也叫做頂部。 數據僅能在頂部進行插入和刪除操作。 最新插入的數據將被最先刪除。因此，堆棧也被稱為后進先出數據結構（Last-In-First-Out）。認識堆棧認識堆棧分析堆棧的邏輯結構分析堆棧的邏輯結構1. 堆棧的定義堆棧的定義2. 堆棧的特征堆棧的特征堆棧也被稱為后進先出數據結構（Last-In-First-Out）。解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)初始化棧：也就是產生一個新的空棧； 入棧操作Push(T x):將指定類型元素x進到棧中； 出棧操作TPop(): 將棧中的棧頂元素取出

5、來，并在棧中刪除棧頂元素； 取棧頂元素GetTop():將棧中的棧頂元素取出來，棧中元素不變； 判斷?？誌sEmpty():若棧為空，返回true，否則返回false； 清空操作Clear ( )：從棧中清除所有的數據元素。認識堆棧認識堆棧識別堆棧的基本操作識別堆棧的基本操作堆棧的基本操作有以下幾種：堆棧的基本操作有以下幾種：解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)下面描述堆棧的進棧操作下面描述堆棧的進棧操作PUSH：它是在堆棧頂部插入新元素的過程。Empty Stack1Push an Element 1認識堆棧認識堆棧識別堆棧的基本操作識別堆棧的基本操作解決

6、堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)PUSH：它是在堆棧頂部插入新元素的過程。下面描述堆棧的進棧操作下面描述堆棧的進棧操作1Push an Element 22Push an Element 33認識堆棧認識堆棧識別堆棧的基本操作識別堆棧的基本操作解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)POP：它是從堆棧頂部刪除元素的過程。下面描述堆棧的出棧操作下面描述堆棧的出棧操作1POP an Element 323POP an Element 2認識堆棧認識堆棧識別堆棧的基本操作識別堆棧的基本操作解決堆棧的編程問題解決堆棧的編程問題數據結構

7、數據結構(C#語言版語言版)堆棧中的元素按 _基礎進行添加和刪除。課間思考課間思考答案：LIFO解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)用一片連續的存儲空間來存儲棧中的數據元素，這樣的棧稱為順序棧(Sequence Stack)。 類似于順序表，用一維數組來存放順序棧中的數據元素 。 棧頂指示器top設在數組下標為0的端，top隨著插入和刪除而變化，當棧為空時，top=-1 。 用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題用順序棧表示堆棧用順序棧表示堆棧解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)初始化順序棧就是創建一個空棧，

8、即調用SeqStack的構造函數，在構造函數中執行下面的步驟：1. 初始化順序棧初始化順序棧用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1初始化maxsize為實際值2為數組申請可以存儲maxsize個數據元素的存儲空間，數據元素的類型由實際應用而定3初始化top為的值為-1解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)Push操作是將一個給定的項保存在堆棧的最頂端，頂端元素的索引保存在變量top中，因此要進行Push操作，需要執行下面的步驟：2.入棧操作：入棧操作：Push(T elem)用順序棧解決堆棧的編程

9、問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1判斷堆棧是否是滿的，如果是，停止操作；否則執行下面的步驟2將top的值加13設置索引為top的數組元素的值為elem解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)Pop操作就是從堆棧的頂部取出數據。要進行Pop操作，需要執行以下的步驟：3. 出棧操作：出棧操作：T Pop( )用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執行下面的步驟2獲取索引top中的值3將索引top的值減1解決堆棧

10、的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)取棧頂元素操作與出棧操作相似，只是取棧頂元素操作不改變原有堆棧，不刪除取出的元素。4. 取棧頂元素：取棧頂元素：GetTop()用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執行下面的步驟2獲取索引top中的值解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)用鏈式存儲結構存儲的棧稱為鏈棧(Linked Stack)。鏈棧通常用單鏈表來表示，它的實現是單鏈表的簡化 。鏈棧結點的結構與單鏈表結點的結構一樣 。

11、 LinkStack類中有一個字段top表示棧頂指示器和一個字段size表示棧的大小 。 用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題用鏈棧表示堆棧用鏈棧表示堆棧解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)初始化鏈棧就是創建一個空鏈棧，即調用LinkStack的構造函數，在構造函數中執行下面的步驟：1. 初始化鏈棧初始化鏈棧用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1棧頂指示器top為null2棧的元素個數size為0解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)Push操作

12、是將一個給定的項保存在堆棧的最頂端，在鏈棧中，就是在單鏈表的起始處插入一個結點。需要執行下面的步驟：2.入棧操作：入棧操作：Push(T elem)用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1創建一個新結點2如果棧為空，將棧頂指示器top指向新結點，否則執行下面步驟3將新結點的next指向棧頂指示器top所指向的結點4將棧頂指示器top指向新結點5棧元素個數size加1解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)Pop操作就是從堆棧的頂部取出數據，即從鏈棧的起始處刪除一個結點。要進行Pop操作，需要執行以下的

13、步驟：3. 出棧操作：出棧操作：T Pop( )用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執行下面的步驟2獲取棧頂指示器top所指向結點的值3將棧頂指示器top指向單鏈表中下一個結點4棧元素個數size減1解決堆棧的編程問題解決堆棧的編程問題數據結構數據結構(C#語言版語言版)取棧頂元素操作與出棧操作相似，只是取棧頂元素操作不改變原有堆棧，不刪除取出的元素。4. 取棧頂元素：取棧頂元素：GetTop()用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對順序棧進行操作對順序棧進行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執行下面的步驟2獲取索引top中的值解決堆棧的編程問題解決堆棧的編程問題數據結