第四章 堆疊與佇列 課前指引 資料結構學科中，堆疊(Stack)與佇列是兩種相當典型的抽象資料型態，也是一種有特定進出規則的線性串列應用，主要特性是限制了資料插入與刪除的位置和方法。本章中將會介紹堆疊與佇列的概念與特性，及在計算機領域的各種相關應用。

Presentation on theme: "第四章 堆疊與佇列 課前指引 資料結構學科中，堆疊(Stack)與佇列是兩種相當典型的抽象資料型態，也是一種有特定進出規則的線性串列應用，主要特性是限制了資料插入與刪除的位置和方法。本章中將會介紹堆疊與佇列的概念與特性，及在計算機領域的各種相關應用。"— Presentation transcript:

1 第四章 堆疊與佇列 課前指引 資料結構學科中，堆疊(Stack)與佇列是兩種相當典型的抽象資料型態，也是一種有特定進出規則的線性串列應用，主要特性是限制了資料插入與刪除的位置和方法。本章中將會介紹堆疊與佇列的概念與特性，及在計算機領域的各種相關應用。

2 章節大綱 4-1 堆疊簡介 4-3 佇列 4-2 算術運算式的表示法 4-4 佇列 的相關應用 備註：可依進度點選小節

3 4-1 堆疊簡介 堆疊(Stack) 是一群相同資料型態的組合，並擁有後進先出(Last In，Frist Out)的特性，所有的動作均在堆疊頂端進行。

4 4-1 堆疊簡介 堆疊在計算機領域的應用 包括遞迴的呼叫及返回、二元樹及森林的走訪運算、呼叫副程式及返回處理、算術式的轉換和求值、中央處理單元(CPU)的中斷處理(Interrupt Handling)與所謂的堆疊計算機(Stack Computer)等等。

5 4-1 堆疊簡介 堆疊基本工作運算 在程式設計中該如何製作一個堆疊呢？因為它只是一種抽象資料型態，不論用陣列或鏈結串列都可以，最重要是要有「後進先出」的精神，並符合五種基本工作運算：

6 4-1 堆疊簡介 陣列實作堆疊 以陣列結構來製作堆疊的好處是製作與設計的演算法都相當簡單，但因為如果堆疊本身是變動的話，陣列大小並無法事先規劃宣告，太大時浪費空間，太小則不夠使用。

7 4-1 堆疊簡介 串列實作堆疊 鍵結串列來製作堆疊的優點是隨時可以動態改變串列長度，能有效利用記憶體資源，不過缺點是設計時，演算法較為複雜。 

8 4-1 堆疊簡介 堆疊類別樣板實作 設計類別時，將資料型態以樣版參數取代，於使用時再指定資料型態，這個類別稱為類別樣版（Class Template）。 在程式中，將會依據宣告物件時所指定的資料型態，來建立適用該資料型態的類別。

9 4-1 堆疊簡介 堆疊類別樣板實作 類別樣版的宣告格式如下：
template <class 樣版形式參數1, class 樣版形式參數2,…> class 類別名稱 { // 類別內敘述區塊 };

10 4-1 堆疊簡介 老鼠走迷宮(1/3) 老鼠行進時，必須遵守以下三個原則：
在建立走迷宮程式前，我們先來了解如何在電腦中表現一個模擬迷宮的方式。 這時可以利用二維陣列MAZE[row][col]，並符合以下規則： 一次只能走一格。 遇到牆無法往前走時，則退回一步找找看是否有其他的路可以走。 走過的路不會再走第二次。 MAZE[i][j]=1 表示[i][j]處有牆，無法通過 =0 表示[i][j]處無牆，可通行 MAZE[1][1]是入口，MAZE[m][n]是出口

11 4-1 堆疊簡介 使用10x12二維陣列的模擬迷宮地圖表示圖

12 4-1 堆疊簡介 老鼠走迷宮(2/3) 利用鏈結串列來記錄走過的位置，並且將走過的位置的陣列元素內容標示為2，然後將這個位置放入堆疊再進行下一次的選擇。 下圖是以小球來代表迷宮中的老鼠： 終於找到迷宮出口 在迷宮中搜尋出口

13 4-1 堆疊簡介 老鼠走迷宮(3/3) 利用C++演算法來加以描述： 1 if(上一格可走) 2 { 3 加入方格編號到堆疊; 4 往上走;
2 { 3 加入方格編號到堆疊; 4 往上走; 5 判斷是否為出口; 6 } 7 else if(下一格可走) 8 { 9 加入方格編號到堆疊; 10 往下走; 11 判斷是否為出口; 12 } 13 else if(左一格可走) 14 { 15 加入方格編號到堆疊;

14 4-1 堆疊簡介 16 往左走; 17 判斷是否為出口; 18 } 19 else if(右一格可走) 20 { 21 加入方格編號到堆疊;
16 往左走; 17 判斷是否為出口; 18 } 19 else if(右一格可走) 20 { 21 加入方格編號到堆疊; 22 往右走; 23 判斷是否為出口; 24 } 25 else 26 { 27 從堆疊刪除一方格編號; 28 從堆疊中取出一方格編號; 29 往回走; 30 }

15 4-1 堆疊簡介 八皇后問題 這也是一種常見的堆疊應用實例。
可以將其應用在4*4的棋盤，就稱為4-皇后問題；應用在8*8的棋盤，就稱為8-皇后問題。應用在N*N的棋盤，就稱為N-皇后問題。 要解決N-皇后問題(在此我們以8-皇后為例)，首先當於棋盤中置入一個新皇后，且這個位置不會被先前放置的皇后吃掉，就將這個新皇后的位置存入堆疊。

16 4-1 堆疊簡介 底下分別是4-皇后及8-皇后在堆疊存放的內容及對應棋盤的其中一組解。 4皇后 8皇后

17 4-2 算術運算式的表示法 在程式中經常將變數或常數等「運算元」(Operands)，利用系統預先定義好的「運算子」(Operators)來進行各種算術運算(如 ＋、－、×、÷等)、邏輯判斷(如 AND、OR、NOT 等)與關係運算(如 ＞、＜、＝ 等)，以求取一個執行結果。 對於程式中這些運算元及運算子的組合，就稱為「運算式」。 其中=、+、*及/符號稱為運算子，而變數A、B、C 及常數10、3 都屬於運算元。

18 4-2 算術運算式的表示法 算術運算式的表示法 中序法(Infix)：運算子在兩個運算元中間，例如A+B、(A+B)*(C+D)等都是中序表示法。 前序法(Prefix)：運算子在運算元的前面，例如+AB、*+AB+CD等都是前序表示法。 後序法(Postfix) ：運算子在運算元的後面，例如AB+、AB+CD+*等都是後序表示法。

19 4-2 算術運算式的表示法 中序轉為前序與後序 括號轉換法 以下是C/C++運算子中運算子的優先順序：

20 4-2 算術運算式的表示法 練習以括號把下列中序式轉成前序及後序式： 中序→前序(Infix→Prefix) 6+2*9/3+4*2-8
先把運算式依照運算子優先順序以括號括起來。 針對運算子，把括號內的運算子取代所有的左括號，以最近者為優先。 將所有右括號去掉，即得前序式結果。 前序式：-++6/*293*428 6+2*9/3+4*2-8

21 4-2 算術運算式的表示法 範例 4.2.1 請將中序式A/B**C+D*E-A*C，利用括號法轉換成前序式與後序式。
中序→後序(infix→postfix) 先把運算式依照運算子優先順序以括號括起來。 針對運算子，把括號內的運算子取代所有的右括號，以最近者為優先。 將所有左括號去掉，即得後序式結果。 後序式：629*3/+42*+8- 範例 4.2.1 請將中序式A/B**C+D*E-A*C，利用括號法轉換成前序式與後序式。

22 4-2 算術運算式的表示法 解答 首先請按照前面的括號法說明，將中序式括號後，可以得到下列式子，並移動運算子來取代左括號：
最後去掉所有右括號，可得下式： →前序式：-+/A**BC*DE*AC 接著要轉換成後序法也一樣，將中序式分別括號完後，移動運算子來取代右括號： 最後再去掉所有左括號，可得下式: →後序式:ABC**/DE*+AC*-

23 4-2 算術運算式的表示法 堆疊法 中序→前序(Infix→Prefix) 由右至左讀進中序運算式的每個字元(token)。
如果讀進的字元為運算元，則直接輸出到前序式中 如果遇到'('，則彈出堆疊內的運算子，直到彈出到一個')'，兩者互相抵銷止。 ")"的優先權在堆疊內比任何運算子都小，任何運算子都可壓過它，不過在堆疊外卻是優先權最高者。 當運算子準備進入堆疊內時，並須和堆疊頂端的運算子比較，如果外面的運算子優先權大於或等於頂端的運算子則推入，如果較小就彈出，直到遇到優先權較小者或堆疊為空時，就把外面這個運算子推入。 中序式讀完後，如果運算子堆疊不是空，則將其內的運算子逐一彈出，輸出到前序式。

24 4-2 算術運算式的表示法 以下我們將練習把中序式(A+B)*D+E/(F+A*D)+C以堆疊法轉換成前序式。首先請右至左讀取字元，並將步驟繪出表格如下：

25 4-2 算術運算式的表示法 中序->後序(Infix->Postfix) 由左至右讀進中序運算式的每個字元(token)。
如果讀進的字元為運算元，則直接輸出輸出到後序式中。 如果遇到')'，則彈出堆疊內的運算子，直到彈出到一個'('，兩者互相抵銷止。 "("的優先權在堆疊內比任何運算子都小，任何運算子都可壓過它，不過在堆疊外卻是優先權最高者。 當運算子準備進入堆疊內時，並須和堆疊頂端的運算子比較，如果外面的運算子優先權大於頂端的運算子則推入，如果較小或等於就彈出，直到遇到優先權較小者或堆疊為空時，就把外面這個運算子推入。 中序式讀完後，如果運算子堆疊不是空，則將其內的運算子逐一彈出，輸出到後序式。

26 4-2 算術運算式的表示法 以下我們將練習把中序式(A+B)*D+E/(F+A*D)+C以堆疊法轉換成後序式。首先請左至右讀取字元，並將步驟繪出表格如下：

27 4-2 算術運算式的表示法 範例 4.2.2 將下面的中序法轉成前序與後序算術式：（以下皆用堆疊法） A/B↑C+D*E-A*C 解答
中序轉前序

28 4-2 算術運算式的表示法 中序轉後序

29 4-2 算術運算式的表示法 前序與後序轉為中序 括號轉換法 前序→中序(Prefix->Infix)
適當的以「運算子+運算元」方式括號。依次將每個運算子，以最近為原則取代後方的右括號，最後再去掉所有左括號。例如:將-+/A**BC*DE*AC轉為中序法，結果是A/B**C+D*E-A*C：

30 4-2 算術運算式的表示法 前序與後序轉為中序 括號轉換法 後序→中序(Postfix->Infix)
適當的以「運算元+運算子」方式括號，依次將每個運算子，以最近為原則取代前方的左括號，最後再去掉所有右括號。例如將ABC↑/DE*+AC*-轉為中序法，結果是A/B↑C+D*E-A*C。

31 4-2 算術運算式的表示法 堆疊法 若要將前序式轉為中序式，由右至左讀進運算式的每個字元(token)；若是要將後序式轉換成中序式，則讀取方向改成由左至右。 辨別讀入字元，若為運算元則放入此堆疊中。 辨別讀入字元，若為運算子則從堆疊中取出兩個字元，結合成一個基本的中序運算式(<運算元><運算子><運算元>)後，再把結果放入堆疊。

32 4-2 算術運算式的表示法 堆疊法 在轉換過程中，前序和後序的結合方式是不同的，前序式的順序是是<運算元2><運算子><運算元1>而後序式是<運算元1><運算子><運算元2>，如下圖所示： 前序轉中序：<OP2><運算子><OP1> 後序轉中序：<OP1><運算子><OP2>

33 4-2 算術運算式的表示法 中序表示法求值 由中序表示法來求值，請依照以下五個步驟：
現在就以上述五個步驟，來求取中序表示法2+3*4+5的值。 1.建立兩個堆疊，分別存放運算子及運算元。 2.讀取運算子時，必須先比較堆疊內的運算子優先權，若堆疊內運算子的優先權較高，則先計算堆疊內運算子的值。 3.計算時，取出一個運算子及兩個運算元進行運算，運算結果直接存回運算元堆疊中，當成一個獨立的運算元。 4.當運算式處理完畢後，一步一步清除運算子堆疊，直到堆疊空了為止。 5.取出運算元堆疊中的值就是計算結果。

34 4-2 算術運算式的表示法 運算式必須使用兩個堆疊分別存放運算子及運算元，並依優先順序進行運算： 步驟1 步驟2
依序將運算式存入堆疊，遇到兩個運算子時比較優先權再決定是否要先行運算： 步驟2 遇到運算子*，與堆疊中最後一個運算子+比較，優先權較高故存入堆疊：

35 4-2 算術運算式的表示法 步驟3 遇到運算子+，與堆疊中最後一個運算子*比較，優先權較低，故先計算運算子*的值。取出運算子*及兩個運算元進行運算，運算完畢則存回運算元堆疊： 步驟4 把運算子+及運算元5存入堆疊，等運算式完全處理後，開始進行清除堆疊內運算子的動作，等運算子清理完畢結果也就完成了：

36 4-2 算術運算式的表示法 步驟5 完成 取出一個運算子及兩個運算元進行運算，運算完畢存入運算元堆疊：
取出一個運算子及兩個運算元進行運算，運算完畢存入運算元堆疊，直到運算子堆疊空了為止。

37 4-2 算術運算式的表示法 前序法的求值運算 實作前序運算式+*23*45如何使用堆疊來運算的步驟： 步驟1 步驟2 從堆疊中取出元素：
從堆疊中取出元素，遇到運算子則進行運算，結果存回運算元堆疊：

38 4-2 算術運算式的表示法 步驟3 步驟4 完成 從堆疊中取出元素：
從堆疊中取出元素，遇到運算子則從運算元取出兩個運算元進行運算，運算結果存回運算元堆疊： 完成 把堆疊中最後一個運算子取出，從運算元取出兩個運算元進行運算，運算結果存回運算元堆疊。最後取出運算元堆疊中的值即為運算結果。

39 4-2 算術運算式的表示法 後序法的求值運算 實作後序表示法23*45*+的求值運算： 步驟1 直接讀取運算式，遇到運算子則進行運算：
放入2及3後取回*，這時取回堆疊內兩個運算元進行運算，完畢後放回堆疊中。 2*3=6

40 4-2 算術運算式的表示法 步驟2 完成 接著放入4及5遇到運算子*，取回兩個運算元進行運算，運算完後放回堆疊中： 4*5=20
最後取回運算子，重複上述步驟。 6+20=26

41 4-3 佇列 佇列 是一種「先進先出」（First In, First Out）的資料結構，和堆疊一樣都是一種有序串列的抽象資料型態。
佇列的兩端都會有資料進出的動作，所以必須記錄佇列的前端與後端，如下圖所示使用front與rear這兩個註標來模擬佇列的運作：

42 4-3 佇列 佇列基本工作運算 五種基本工作運算：

43 4-3 佇列 陣列實作佇列 與堆疊不同之處是需要擁有兩種基本動作加入與刪除，而且使用front與rear兩個註標來分別指向佇列的前端與尾端，缺點是陣列大小並無法事先規劃宣告。

44 4-3 佇列 陣列實作佇列 首先我們需要宣告一個有限容量的陣列，並以下列圖示說明： #define MAXSIZE 4
int queue[MAXSIZE]; /* 佇列大小為4 */ int front=-1; int rear=-1;

45 4-3 佇列 1.當開始時，我們將front與rear都預設為-1，當front=rear時，則為空佇列。
2.加入dataA，front=-1，rear=0，每加入一個元素，將rear值加1：

46 4-3 佇列 3.加入dataB、dataC，front=-1，rear=2：
4.取出dataA，front=0，rear=2，每取出一個元素，將front值加1：

47 4-3 佇列 5.加入dataD，front=0，rear=3，此時當rear=MAXSIZE-1，表示佇列已滿。
6. 取出dataB，front=1，rear=3

48 4-4 佇列的相關應用 佇列在電腦領域的應用相當廣泛，如： 1. 如在圖形的走訪的先廣後深搜尋法(BFS)，就是利用佇列。
2. 可用於計算機的模擬(simulation)；在模擬過程中，由於各種事件(event)的輸入時間不一定，可以利用佇列來反應真實狀況。 3. 可作為CPU 的工作排程(Job Scheduling)。利用佇列來處理，可達到先到先做的要求。 4. 例如「線上同時週邊作業系統」的應用，也就是讓輸出入的資料先在高速磁碟機中完成， 也就是把磁碟當成一個大型的工作緩衝區(buffer)，如此可讓輸出入動作快速完成，也縮短了反應的時間，接下來將磁碟資料輸出到列表機是由系統軟體主動負責，這也是應用了佇列的工作原理。

49 4-4 佇列的相關應用 環狀佇列 是一種環形結構的佇列，它仍是以一種Q(0:n-1)的線性一維陣列，同時Q(0)為Q(n-1)的下一個元素，可以用來解決無法判斷佇列是否滿溢的問題。 指標front永遠以逆時鐘方向指向佇列中第一個元素的前一個位置，rear則指向佇列目前的最後位置。一開始front和rear均預設為-1，表示為空佇列，也就是說如果front=rear則為空佇列。另外有： rear(rear+1) mod n front(front+1) mod n

50 4-4 佇列的相關應用 上述方式僅允許佇列最多只能存放n-1個資料(亦即犠牲最後一個空間)，當rear指標的下一個是front的位置時，就認定佇列已滿，無法再將資料加入，如下圖便是填滿的環狀佇列外觀：

51 4-4 佇列的相關應用 底下將整個過程以下圖來說明。

52 4-4 佇列的相關應用

53 4-4 佇列的相關應用 而當rear=front時，則可代表佇列已空。所以在enqueue和dequeue的兩種工作定義和原先佇列工作定義的演算法就有不同之處了。必須改寫如下： /* 環形佇列的刪除演算法 */ void dequeue(int item) { if (front==rear) printf(“%s”, "佇列是空的!"); else front=(front+1)%MAX_SIZE; item=Queue[front]; } /* 環狀佇列的加入演算法 */ viod AddQ (int item) { rear=(rear+1)%MAX_SIZE; if (front==rear ) printf(“%s”, "佇列已滿! "); else queue[rear]=item; }

54 4-4 佇列的相關應用 範例 4.4.2 上述環形佇列演算法中，造成了任何時候佇列中最多只允許MAX_SIZE-1個元素。有沒有方法可以改進呢?試說明之與寫出修正後演算法。 解答 只要多使用一個旗標TAG來判斷，當TAG==1時表示，佇列是滿的；TAG==0時，表示佇列是空的。修正後演算法如下：

55 4-4 佇列的相關應用 /* 環狀佇列的加入修正演算法 */ viod AddQ (int item) {
rear=(rear+1)%MAX_SIZE; if(front==rear && TAG==1) printf(“%s”, "佇列已滿! "); else queue[rear]=item; if(front==rear) TAG=1; } /* 環形佇列的刪除修正演算法 */ void dequeue(int item) { if(rear==front && TAG==0) printf(“%s”, "佇列是空的!"); else front=(front+1)%MAX_SIZE; item=Queue[front]; if (front==rear) TAG=0; }

56 4-4 佇列的相關應用 雙向佇列 為一有序串列，加入與刪除可在佇列的任意一端進行， 請看下圖：
通常在一般的應用上，雙向佇列的應用可以區分為兩種：第一種是資料只能從一端加入，但可從兩端取出，另一種則是可由兩端加入，但由一端取出。

57 4-4 佇列的相關應用 優先佇列 為一種不必遵守佇列特性－FIFO(先進先出)的有序串列，其中的每一個元素都賦予一個優先權(Priority)，加入元素時可任意加入，但有最高優先權者(Highest Priority Out First, HPOF)則最先輸出。 例如假設有4個行程P1,P2,P3,P4，其在很短的時間內先後到達等待佇列，每個行程所執行時間如下表所示：

58 4-4 佇列的相關應用 在此設定每個P1、P2、P3、P4的優先次序值分別為2,8,6,4(此處假設數值越小其優先權越低；數值越大其優先權越高)，以下就是以甘特圖(Gantt Chart)繪出優先權排程(Priority Scheduling, PS)的排班情況： 以PS方法排班所繪出的甘特圖如下：

59 本章結束 Q&A討論時間