佇列與推疊 (Queue and Stack)

Presentation on theme: "佇列與推疊 (Queue and Stack)"— Presentation transcript:

1 佇列與推疊 (Queue and Stack)
授課老師：蕭志明

2 佇列（ Queue ）概念

3 佇列基本觀念 資料可以在後端新增，從前端刪除。兩端皆可進行資料的擷取。 佇列的實作需要保持前端與後端的追蹤，而堆疊只要維護頂端即可。
佇列是屬於線性串列，而加入的一端稱為後端（rear），刪除的那一端為前端（front）。 資料可以在後端新增，從前端刪除。兩端皆可進行資料的擷取。 佇列的實作需要保持前端與後端的追蹤，而堆疊只要維護頂端即可。 由於佇列具有先進先出（First In First Out，FIFO）的特性，因此也稱佇列為先進先出串列。

4 佇列前端 Queue rear會檢查佇列後端的資料。

5 佇列後端

6 佇列新增作業 刪除作業會移除位於佇列前端的元素。

7 佇列刪除作業 Queue front會檢查佇列前端的資料。

8 佇列範例

9 佇列的加入與刪除（使用陣列） 佇列的操作行為是先進先出，我們可以假想在一陣列中有二端分別為front和rear端，每次加入都加在rear端，而刪除（即將被服務）的在front端。 一開始，佇列的front=-1，rear=-1，當加入一元素到佇列時，主要判斷rear是否會超過其陣列的最大容量。

10 佇列的加入與刪除（使用陣列） 當rear為MAX-1時，表示陣列已到達最大容量了，此時不能再加任何元素進來；
反之，則陣列未達最大容量，因此可以加入任何元素。以下是其片段程式

11 佇列的加入與刪除（使用陣列） 而刪除佇列的元素則需考慮佇列是空的情況，因為佇列為空時，表示沒有元素在佇列中，怎能刪除呢？當front >= rear時，則表示佇列是空的，其片段程式如下：

12 佇列的加入與刪除（使用陣列） 上述的佇列是線性佇列（linear queue），表示的方式為Q(0: MAX-1)，但此線性佇列。
不太合理的現象就是當rear到達MAX-1時 無論如何的加入皆是不允許的，因為上述的加入片段程式會印出佇列是滿的訊息，因此它沒考慮佇列的前面是否還有空的位子。

13 環狀佇列（使用陣列） 為了解決此一問題，佇列常常以環狀佇列(circle queue)來表示之，CQ(0: MAX-1)，如下圖所示：

14 環狀佇列（使用陣列） 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述 rear=(rear+1) % MAX; 求出rear，主要的用意在於能夠使rear回到前面，看看是否還有空的位置可放。如當rear為MAX-1時，((MAX-1)+1)% MAX，其餘數為0，此時便可進入環狀佇列的前端了。

15 環狀佇列（使用陣列） 以下是 片段程式

16 環狀佇列（使用陣列） 環狀佇列的刪除，乃判斷front是否和rear同在一起，若是，則印出環狀佇列是滿的訊息，
否則，將front往前移，並加入元素，以下是其片段程式： 其中, front = (front+1) % MAX ;

17 佇列（使用鍊結串列 ） 如果是以鍊結串列來實作佇列，會使用表頭 (Head) 節點與資料節點等兩種結構。
資料結構，需要兩種不同的結構來實作佇列， 一個head結構。 資料節點。 建立佇列之後，佇列會有一個haed節點與0個或1個以上的資料節點。

18 佇列資料結構 （使用鍊結串列 ）

19 佇列（使用鍊結串列 ）

20 佇列（使用鍊結串列 ）

21 佇列的應用 假如所要解決的問題是有先進先出的性質時，則宜用佇列來解決，例如作業系統的工作安排（job scheduling），若不考慮特權（priority）的話。 舉凡銀行櫃台的服務、停車場的問題、大型計算機中心列印報表的情形，以及飛機起飛與降落等等的應用。

22 堆疊（Stack）觀念 堆疊是一種先進後出的資料結構，所有的新增與刪除都要在同一端進行，我們稱此端為頂端。

23 堆疊基本觀念 堆疊是一有序串列（order list），其加入（insert）和刪除（delete）動作都在同一端，此端通常稱之為頂端（top）。 加入一元素於堆疊，此動作稱為推入（push），與之相反的是從堆疊中刪除一元素；此動作稱為彈出（pop）。 由於堆疊具有先進去的元素最後才會被搬出來的特性，所以又稱堆疊是一種後進先出（Last In First Out，LIFO）串列。

24 堆疊和佇列比較 堆疊、佇列如圖3.1之(a)、(b)所示。
其中(a)堆疊有如一容器，而(b)的佇列有如一排隊的隊伍，最前面的是front所指的地方，因此front所指的位置一定會先被服務，而rear所指的地方是新加入的位置。

25 基本的堆疊作業 三個基本的堆疊操作是： 推入 (Push) 。 彈出 (Pop) 。 頂端元素(Stack Top)。

26 推入堆疊作業 推 入 (Push) 推入會在堆疊頂端加入一個項目，此項目即成為堆疊的頂端元素。 此作業只有一個要求，就是要有足夠的空間。

27 彈出堆疊作業 彈　出 (Pop) 當進行彈出作業時，將頂端的項目移除並傳回給使用者。

28 頂端元素操作 頂端元素 (Stack Top) 頂端元素就是拷貝頂端元素；但是未進行刪除。

29 堆疊實例

30 堆疊實例

31 堆疊的加入與刪除（使用陣列） 我們可以設定一陣列來表示堆疊，此堆疊是有最大容量的，如 int a[10];
表示此陣列的最大容量是10個元素。除了有一陣列外，我們也指定了一個變數top做為追蹤目前堆疊的位置。top的初始值為-1。

32 堆疊的加入與刪除（使用陣列） 加入一元素（push an item）到堆疊，主要考慮會不會因為加入此一元素而溢位（overflow），亦即加入時要考慮不可超出堆疊的最大容量。若沒有超出，則先將top加入，再將元素填入a[top]中。

33 堆疊的加入與刪除（使用陣列）

34 堆疊的加入與刪除（使用陣列） 加入一元素10於堆疊的片段程式如下：

35 堆疊的加入與刪除（使用陣列） 從堆疊刪除一元素，等於從堆疊彈出（pop）一元素，此時我們必須注意堆疊是否為空的，亦即top的值為-1。若不是空的，表示堆疊有元素存在，此時，先將a[top]的元素移除，之後將top減1。

36 堆疊的加入與刪除（使用陣列） 以下是其程式片段

37 堆疊的加入與刪除（使用連結串列） 資料結構 需要兩個不同的結構， 表頭結構包含共同資料與一個指向堆疊頂端的指標。
一個表頭節點。 一個資料節點。 表頭結構包含共同資料與一個指向堆疊頂端的指標。 資料結構包含資料與指向堆疊中下一個節點的指標。

38 堆疊的加入與刪除（使用連結串列）

39 堆疊的表頭 (Head) 一般來說，表頭有兩個屬性： 一個頂端指標 (Top Pointer) 。 與所包含元素的計數 (Count)。

40 鍊結串列的堆疊作業

41 堆疊的應用 由於堆疊具有先進後出的特性，因此凡是具有後來先處理的性質，皆可使用堆疊來解決。例如副程式的呼叫（subroutine calls）

42 堆疊的應用 堆疊的應用分為四大類： 反轉。 剖析。 展延。 回溯。

43 堆疊的應用-反轉資料 (Reversing Data)
將一組資料重新排序，使得第一個與最後 一個元素交換，其他的資料也相對地作交換。 例如，｛ ｝變成｛ ｝。

44 堆疊的應用-剖析 剖析就是將資料分解為獨立的單元，以待進一步處理。
程式中常見的錯誤是刮號的配對不正確。錯誤的型態有兩種：缺少右刮號或是左刮號，如圖所示。

45 堆疊的應用-展延 當我們使用堆疊反轉一個串列時，在輸出結果之前就已先讀取整個串列。
如果應用程式的邏輯要求在稍後才使用資料，那麼堆疊就可以派上用場了。 在此節我們要發展兩個展延(Postponement) 的應用：中序轉換為後序、與計算後序式。

46 中序轉換為後序 前序 : + a b 中序 : a + b 後序 : a b +
算術式可以有三種不同的格式來表示：中序 (Infix)、後序 (Postfix)、與前序 (Prefix)。 中序式的運算子 (Operator) 在運算元(Operand) 之間，這也是我們常用的格式。 後序式的運算子在運算元之後，而前序式的運算子在運算元之前。如下所示： 中序式的缺點是要使用刮號來控制運算子的計算，於是必須要規定刮號與兩個運算子計算時的優先權。 後序與前序式並不需要刮號，而且都只有一個計算規則。 電腦不能直接使用高階語言所使用的中序式，要將中序式轉換為後序式，再進行計算。 在前序式中，運算子在運算元之前； 在中序式中，運算子在運算元之間； 在後序式中，運算子在運算元之後。 前序 : + a b 中序 : a + b 後序 : a b +

47 中序轉換為後序三步驟 其實算術運算式由中序變為後序可依下列三步驟進行即可： (1)將式子中的運算單元適當的加以括號，
此時須考慮運算子的運算優先順序。 (2)將所有的運算子移到其對應的右括號。 (3)將所有的括號去掉。

48 中序轉換為後序-範例 A + B * C 執行第一個步驟的結果 ( A + ( B * C ) ) 執行第二個步驟將『乘』移到C之後
接著將『加』移到最後兩個右刮號之間，因為最後一個右刮號是屬於『加』的，結果為 ( A ( B C * ) + ) 最後，執行第三個步驟，得到 A B C * +

49 中序轉換為後序-範例 1. 將A-B/ C+D*E化成後序表示式，步驟如下： (1)((A-(B/C))+(D*E))
2. 將( A + B ) * C + D + E * F – G化成後序表示式： 第一個步驟將算式加上刮號 ( ( ( ( ( A + B ) * C) + D ) + (E * F ) ) – G ) 第二個步驟移動運算子 ( ( ( ( ( A B +) C * ) D + ) (E F * ) +) G - ) 第三個步驟移除刮號 A B + C * D + E F * + G –

50 中序轉換為後序（使用堆疊） 將算術運算式由中序表示改變為後序表示式，除了上述的方法，也可以利用堆疊的觀念來完成。
首先要了解算術運算子的in-stack（在堆疊中）與in-coming（在運算式中）的優先順序。

51 中序轉換為後序（使用堆疊）

52 中序轉換為後序（使用堆疊） 開始時堆疊是空的，假設稱運算式中的運算子和運算元是token，當token是運算元，不必考慮，一律輸出。
但是如果進來的token是運算子，而且若此運算子的in-stack priority（ISP）大於或等於in-coming priority(ICP)，則輸出放在堆疊的運算子，繼續執行到ISP<ICP，之後再將欲進來的運算子放入堆疊中。

53 中序轉換為後序（使用堆疊） 首先以A+B*C來說明，其情形如下：

54 中序轉換為後序（使用堆疊） A*(B+C)*D轉換為後序

55 中序轉換為後序（使用堆疊） A*(B+C)*D轉換為後序

56 中序轉換為後序（使用堆疊）

57 後序式的計算 例如以下的後序式，並假設A為2、B為4、C為6，那麼所得為何？ 使用堆疊的延遲，計算後序式。 A B C + *=246+*
第一件事是運算元在運算子之前。所以這次要延遲使用的是運算元，而不是運算子。 於是要新增至堆疊的是運算元。 當遇到一個運算子時，在堆疊頂端刪除兩個運算元，並進行運算。 接著將計算結果推入堆疊。 在計算完畢之後，最後的結果會留在堆疊之中。

58 後序式的計算

59 堆疊的應用-回溯 可應用在電腦遊戲、決策分析、與專家系統中。 在此節我們檢視兩個回溯的應用： 目標尋找。 與八皇后問題。

60 堆疊的應用-回溯 目標尋找

61 堆疊的應用-回溯 八皇后問題 將八個皇后放在西洋棋盤上，並且沒有一個皇后能吃掉另一個皇后。
方法是將一個皇后放在棋盤上，並且分析所有的可能攻擊，以確定沒有一個皇后能攻擊另一 個皇后。 分析四個皇后如何放在的棋盤上。顯示皇后的攻擊規則與一個解。 可以使用堆疊與回溯來解決這一個問題。 因為任何一列，只可以放一個皇后，所以將第一個皇后放在row1，column1。並將此位置新增至堆疊。

62 四皇后

63 放置四皇后的步驟

64 放置四皇后的步驟 接著在第2列尋找位置，不可以選擇位置2, 1，因為此位置的垂直方向有第1列的皇后。而位置2, 2也因為對角線的方向，不能放置皇后。 所以在第2列的第3行放置皇后，並將此位置新增至堆疊，如圖的步驟2。 現在要在第3列尋找位置，但是沒有一個位置符合要求，第1行會被第1列的皇后攻擊，其他3行則會被第2列的皇后攻擊。 所以我們要藉由刪除回溯到第2列，並繼續在第2列尋找一個位置。發現第4行可以放置一個皇 后，所以將此位置新增至堆疊，如圖的步驟3。

65 放置四皇后的步驟 接著要在第3列尋找位置，第1行仍然被第1列的皇后攻擊，但是第2行可以放置一個皇后，所以將此位置新增至堆疊，如圖的步驟4。
要在第4列放置一個皇后時，發現所有的位置都不行。第1行會被第1列與第3列的皇后攻擊，第2行會被第2列與第3列的皇后攻擊，第4行會被第1列與第2列的皇后攻擊。 於是回溯到第3列，可是此列的第3行與第4行都會被第2列的皇后攻擊，所以第3列已經沒有位置可以放置皇后。 所以只好再藉由彈出以進行回溯，發現第2列也沒有位置可以放置皇后，再回溯到第1列，並將此列的皇后放到第2行，如圖的步驟5所示。

66 放置四皇后的步驟 第2列唯一適合的是第4行，因為第1列的皇后會攻擊其他3個位置的皇后，於是將皇后放在此，並將此位置新增至堆疊，如圖的步驟6所示。 接著我們在第3列的第1行放一個皇后，並將此位置新增至堆疊，如圖的步驟7所示。 發現第4列的第1行會被第3列的皇后攻擊，第2行會被其他所有的3個皇后攻擊。第3行可以放 置一個皇后，所以我們在此位置放置一個皇后，終於找到一個解。