解決堆棧的編程問題

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

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

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

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

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

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

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

8、即調(diào)用SeqStack的構(gòu)造函數(shù)，在構(gòu)造函數(shù)中執(zhí)行下面的步驟：1. 初始化順序棧初始化順序棧用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對(duì)順序棧進(jìn)行操作對(duì)順序棧進(jìn)行操作步驟步驟操作操作1初始化maxsize為實(shí)際值2為數(shù)組申請(qǐng)可以存儲(chǔ)maxsize個(gè)數(shù)據(jù)元素的存儲(chǔ)空間，數(shù)據(jù)元素的類型由實(shí)際應(yīng)用而定3初始化top為的值為-1解決堆棧的編程問題解決堆棧的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語言版語言版)Push操作是將一個(gè)給定的項(xiàng)保存在堆棧的最頂端，頂端元素的索引保存在變量top中，因此要進(jìn)行Push操作，需要執(zhí)行下面的步驟：2.入棧操作：入棧操作：Push(T elem)用順序棧解決堆棧的編程

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

10、的編程問題解決堆棧的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語言版語言版)取棧頂元素操作與出棧操作相似，只是取棧頂元素操作不改變?cè)卸褩?，不刪除取出的元素。4. 取棧頂元素：取棧頂元素：GetTop()用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對(duì)順序棧進(jìn)行操作對(duì)順序棧進(jìn)行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執(zhí)行下面的步驟2獲取索引top中的值解決堆棧的編程問題解決堆棧的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語言版語言版)用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ)的棧稱為鏈棧(Linked Stack)。鏈棧通常用單鏈表來表示，它的實(shí)現(xiàn)是單鏈表的簡化 。鏈棧結(jié)點(diǎn)的結(jié)構(gòu)與單鏈表結(jié)點(diǎn)的結(jié)構(gòu)一樣 。

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

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

13、步驟：3. 出棧操作：出棧操作：T Pop( )用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對(duì)順序棧進(jìn)行操作對(duì)順序棧進(jìn)行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執(zhí)行下面的步驟2獲取棧頂指示器top所指向結(jié)點(diǎn)的值3將棧頂指示器top指向單鏈表中下一個(gè)結(jié)點(diǎn)4棧元素個(gè)數(shù)size減1解決堆棧的編程問題解決堆棧的編程問題數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)(C#語言版語言版)取棧頂元素操作與出棧操作相似，只是取棧頂元素操作不改變?cè)卸褩＃粍h除取出的元素。4. 取棧頂元素：取棧頂元素：GetTop()用順序棧解決堆棧的編程問題用順序棧解決堆棧的編程問題對(duì)順序棧進(jìn)行操作對(duì)順序棧進(jìn)行操作步驟步驟操作操作1檢查堆棧中是否含有元素，如果沒有，停止操作；否則執(zhí)行下面的步驟2獲取索引top中的值解決堆棧的編程問題解決堆棧的編程問題數(shù)據(jù)結(jié)