本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。

Presentation on theme: "本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。"— Presentation transcript:

1 本教學投影片係屬教科書著作之延伸，亦受著作權法之保護。
請依出版社授權使用規範利用本教學資源，非經授權許可不得以影印、拷貝、列印等方法進行重製，亦不得改作、公開展示著作內容，亦請勿對第三人公開傳輸、散布。 戴顯權 著 / 資料結構 © 滄海圖書

2 Chapter 4 堆疊和佇列 戴顯權 著 / 資料結構 © 滄海圖書

3 本章內容 4.1　堆疊 4.2　算術運算式 4.3　佇列 4.4　環狀佇列 4.5　堆疊與佇列的應用 戴顯權 著 / 資料結構 © 滄海圖書

4 堆疊和佇列 堆疊只允許資料從有序串列的同一端做輸入與輸出， 因此具有先進入的資料要等到最後面才出得來
First In Last Out (FILO) Last In First Out (LIFO) 戴顯權 著 / 資料結構 © 滄海圖書

5 堆疊和佇列 佇列規定資料的輸入必須由前端(front) 進入，而輸出則必須從後端(rear) 輸出
先存入佇列的資料會先被取出(First In First Out，簡稱 FIFO) 常見的佇列應用有： 作業系統之工作排程 印表機或作業系統的排程 排隊問題的模擬 戴顯權 著 / 資料結構 © 滄海圖書

6 堆疊和佇列 在堆疊中最後一個加入的元素將是 第一個可以刪除的元素，因此堆疊 具有後進先出(Last In First Out，簡 稱LIFO) 堆疊的應用非常多，例如： 副程式之呼叫 處理遞迴函式呼叫 算術式之轉換與求值 戴顯權 著 / 資料結構 © 滄海圖書

7 堆疊 堆疊是一個有序串列，它的加入與刪除運算都在同 一端進行，我們稱那一端為頂端(top)
加入一個元素到堆疊中的運算叫作推入(push)；從堆 疊中刪除一個元素的運算稱為彈出(pop) 戴顯權 著 / 資料結構 © 滄海圖書

8 堆疊的基本運算 推入(push) 彈出(pop) 檢查堆疊是否已經滿了(full) 或者是空的(empty)
戴顯權 著 / 資料結構 © 滄海圖書

9 推入堆疊 戴顯權 著 / 資料結構 © 滄海圖書

10 推入堆疊 戴顯權 著 / 資料結構 © 滄海圖書

11 從堆疊彈出 戴顯權 著 / 資料結構 © 滄海圖書

12 從堆疊彈出 戴顯權 著 / 資料結構 © 滄海圖書

13 系統堆疊 每當一個程式執行時，電腦都會替它準備一個堆疊， 稱為系統堆疊(system stack)
如果是函式自己呼叫自己的情況，就稱為遞迴呼叫 (recursive call) 遞迴呼叫每呼叫自己一次，就會產生一個新的資料 框 戴顯權 著 / 資料結構 © 滄海圖書

14 戴顯權 著 / 資料結構 © 滄海圖書

15 遞迴呼叫之費式數列問題 費氏數列的定義如下： 戴顯權 著 / 資料結構 © 滄海圖書

16 遞迴呼叫之河內塔問題 有一塊上面插有三根長木釘的木板，在其中一根木 釘上，從下至上放置了64 片直徑由大至小的圓環形 金屬片
如果一次只移動一片金屬片且整個移動過程中大的 金屬片永遠不能壓在比它小的金屬片上 如果要移動這64 片金屬片，那麼至少需要要搬移多 少次才能達成？在搬移的過程中，又有什麼規律會 形成呢？ 戴顯權 著 / 資料結構 © 滄海圖書

17 河內塔 - 兩片金屬片為例 以兩片金屬片為例，將它們從最左邊的初始木釘移 動至最右邊的目的木釘，並且使用中間木釘當暫存 區
戴顯權 著 / 資料結構 © 滄海圖書

18 河內塔 - 兩片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

19 河內塔 - 兩片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

20 河內塔 - 兩片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

21 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

22 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

23 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

24 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

25 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

26 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

27 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

28 河內塔 – 三片金屬片為例 戴顯權 著 / 資料結構 © 滄海圖書

29 河內塔 – 三片金屬片為例 從圖4.7 可以得知，搬運三片鐵片就等於先將前面兩 片鐵片搬到暫存木釘上，這部分工作需要搬移3 次
然後再把第三片鐵片搬到目的木釘上，這部分的工 作需要搬移1 次 最後再把暫存木釘上的兩片鐵片搬到目的木釘上， 這部分工作又需要搬移3 次 共計搬移 = 7 次 戴顯權 著 / 資料結構 © 滄海圖書

30 河內塔 - 程序推廣 如果初始木釘上有n 片金屬片，那麼我們需要先把第 一到第n – 1 片鐵片移動到暫存木釘上
戴顯權 著 / 資料結構 © 滄海圖書

31 戴顯權 著 / 資料結構 © 滄海圖書

32 河內塔的遞迴程式 當n = 1 時，搬動的次數是T(1) = 1。當n = 2 時，T(2) = 3
當n = 3 時，T(3) = 7，而且T(n + 1) = T(n) T(n)。 因此，T(n + 1) = 2*T(n) + 1 也就是說，T(2) = 2*T(1) + 1 = 2 + 1、T(3) = 2*T(2) + 1 = 2*(2 + 1) + 1 = ，以此類推 我們因此可得到T(n + 1) = 2n + 2n –1 + … = 2n+1 – 1，即T(n) =2n – 1。因此，T(64) = 264 – 1 (次) 戴顯權 著 / 資料結構 © 滄海圖書

33 算術運算式 中置法(infix expression) 前置法(prefix expression)
在人的世界裡，們最常使用 例子：算術式A + B 前置法(prefix expression) 少用 例子： A + B 的前置表示法是+AB 後置法(postfix expression) 在電腦中最常使用 例子： A + B 的後置表示法是AB+ 戴顯權 著 / 資料結構 © 滄海圖書

34 戴顯權 著 / 資料結構 © 滄海圖書

35 後置表示法的優點 可以完全不用括號，只憑位置就能決定其運算順序 運算子之間也不再需要去判斷優先次序的關係 電腦可以直接從左到右掃描算術式
遇到運算元就推入堆疊 遇到運算子就從堆疊中彈出運算元來加以計算 戴顯權 著 / 資料結構 © 滄海圖書

36 中置轉後置 用人工將中置表示法轉後置表示法的演算法： 例子：A*B+C–D*E+F*G
在算術式上依照運算順序，針對每一個運算加上完整的 括號 例子：((((A*B)+C)–(D*E))+(F*G)) 把所有的運算子移到相對應的右括弧後面 例子：((((AB)*C)+(DE)*)–(FG)*)+ 去除所有的括弧 例子： AB*C+DE*–FG*+ 戴顯權 著 / 資料結構 © 滄海圖書

37 中置轉前置 中置表示法轉前置表示法的演算法： 例子：A*B+C–D*E+F*G 在算術式上依照運算順序，針對每一個運算加上完整的 括號
把所有運算子移到相對應的左括弧前面 例子： +(–(+(*(AB)C)*(DE))*(FG)) 去除所有的括弧 例子： +–+*ABC*DE*FG 戴顯權 著 / 資料結構 © 滄海圖書

38 算術運算式 電腦在處理算術式時所採用的是利用一個堆疊 它從左至右掃描一個算術式，如果讀到運算元就直 接輸出
如果讀到的運算子的優先順序比在堆疊頂端的運算子之優 先順序高，那麼就把它推入堆疊中 如果是比較低的或者是相等的，那麼就把堆疊中優先順序 比它高或等於它的運算子全部依序彈出來，然後再把自己 推入堆疊中 戴顯權 著 / 資料結構 © 滄海圖書

39 例題一 計算A*B+C–D*E+F*G 戴顯權 著 / 資料結構 © 滄海圖書

40 例題一 戴顯權 著 / 資料結構 © 滄海圖書

41 例題二 計算A+B*(C+D)–E 1.（無條件推入堆疊。 2.）堆疊中的運算子一直彈出，直到彈出一個（。 3.（）可以忽略不輸出。
戴顯權 著 / 資料結構 © 滄海圖書

42 例題二 戴顯權 著 / 資料結構 © 滄海圖書

43 算術運算式 中置：A/B-C+D*E-A*C 後置：AB/C-DE*+AC*- 戴顯權 著 / 資料結構 © 滄海圖書

44 戴顯權 著 / 資料結構 © 滄海圖書

45 佇列 佇列(queue) 也是一個有序串列 與堆疊不同的是：它的所有加入運算都固定在一端 進行，而所有的刪除運算則在另一端進行
戴顯權 著 / 資料結構 © 滄海圖書

46 佇列 佇列的特性是：如果我們依序加入A、B 以及C 到佇 列中，那麼A 將是第一個可以刪除的元素，其次是B， 再來才是C
戴顯權 著 / 資料結構 © 滄海圖書

47 佇列 佇列具有「第一個被加入的是第一個可以被移除」 的性質，因此佇列是一種先進先出(First In First Out， 簡稱FIFO) 的串列 使用一個一維陣列以及兩個變數front 與rear front 指向陣列中第一個元素的位置再減1 的位置，我們稱 之為前端指標(front pointer) rear 指向陣列中最後一個元素的所在位置，我們稱之為後 端指標(rear pointer) 一開始當佇列是空的時候，我們設定front = rear = –1 戴顯權 著 / 資料結構 © 滄海圖書

48 在佇列中加入一個元素 戴顯權 著 / 資料結構 © 滄海圖書

49 在佇列中加入一個元素 戴顯權 著 / 資料結構 © 滄海圖書

50 從一個佇列裡刪除一個元素 戴顯權 著 / 資料結構 © 滄海圖書

51 戴顯權 著 / 資料結構 © 滄海圖書

52 佇列 戴顯權 著 / 資料結構 © 滄海圖書

53 佇列 戴顯權 著 / 資料結構 © 滄海圖書

54 環狀佇列 當佇列不斷地從一邊加入資料，然後再從另一邊刪除元 素時，rear 很快地就到達了MaxSize – 1 的位置，佇列因 此就達到填滿的狀態，當然也就不能再加入元素了 front 指標其實很可能也隨著元素的刪除而漸漸趨近rear。 這個時候問題產生了：佇列明明有很多空位，但是卻不 能再使用了 把佇列改良成不斷將後面的元素往前移動，以使得Q[0] 一直有元素，雖然可以使得新增與刪除運算能夠繼續進 行，但是卻得花費過多的時間在移動佇列元素的動作上 戴顯權 著 / 資料結構 © 滄海圖書

55 環狀佇列 一個比較好的解決辦法是把陣列的末端給「捲繞」 起來，成為一個環狀，而非先前的線性狀態
如此一來就可以在rear 到達MaxSize – 1 時繼續往下 使用位址為0 的空間，容許這種用法的新結構就稱為 環狀佇列(circular queue) 戴顯權 著 / 資料結構 © 滄海圖書

56 環狀佇列 當陣列被視為一個環的時候，每一個陣列的位置都 會有下一個與前一個位置
位置MaxSize – 1 的下一個位置是0，而位置0 的前一 個位置就是MaxSize – 1。當佇列目前的末端位置是 MaxSize – 1 時，那麼它的下一個元素就會被插入到0 的位置(只要它是空著的) 要使用一個環狀佇列，我們必須能將變數front 與rear 由它們現在的所在位置移往下一個位置(順時鐘) 戴顯權 著 / 資料結構 © 滄海圖書

57 環狀佇列 佇列在一開始時front=rear， 而且佇列是空的 戴顯權 著 / 資料結構 © 滄海圖書

58 環狀佇列 空佇列連續加入五個元 素後 戴顯權 著 / 資料結構 © 滄海圖書

59 環狀佇列 佇列再加入兩個元素， 使佇列填滿後 戴顯權 著 / 資料結構 © 滄海圖書

60 環狀佇列 佇列刪除兩個元素後又 加入兩個元素後 戴顯權 著 / 資料結構 © 滄海圖書

61 戴顯權 著 / 資料結構 © 滄海圖書

62 環狀佇列 圖4.10(a) 就是圖4.9(a) 的空佇列，而圖4.10(b) 則是圖 4.9(c) 的佇列再加入一個元素後的樣子
這兩個佇列的front 都等於rear，但是一個是空的、一 個是滿的 即便我們能測得front=rear，卻完全無從分辨到底佇 列是空的還是滿的？！ 戴顯權 著 / 資料結構 © 滄海圖書

63 環狀佇列 解決辦法 因此可確保：front == rear 若且唯若佇列是空佇列 限定任何時間佇列中頂多只能有MaxSize – 1 個元素
戴顯權 著 / 資料結構 © 滄海圖書

64 戴顯權 著 / 資料結構 © 滄海圖書

65 戴顯權 著 / 資料結構 © 滄海圖書

66 戴顯權 著 / 資料結構 © 滄海圖書

67 戴顯權 著 / 資料結構 © 滄海圖書

68 老鼠走迷宮 中灰色的部分代表牆 壁，那是老鼠不能走 的地方；而白色的部 分代表道路，表示老 鼠可以走的地方。虛 線所標示的是唯一的 一條出路
戴顯權 著 / 資料結構 © 滄海圖書

69 老鼠走迷宮 用一個 12  12 的二 維陣列maze 來表示 一個迷宮，其中元素 maze[i][ j], 0  i  11, 0  j  11 的值為1 時 表示不通，而0 則表 示這是可以走的路 戴顯權 著 / 資料結構 © 滄海圖書

70 老鼠走迷宮 利用C 語言來表示這 個迷宮 戴顯權 著 / 資料結構 © 滄海圖書

71 老鼠走迷宮 戴顯權 著 / 資料結構 © 滄海圖書

72 老鼠走迷宮 戴顯權 著 / 資料結構 © 滄海圖書

73 老鼠走迷宮 戴顯權 著 / 資料結構 © 滄海圖書

74 戴顯權 著 / 資料結構 © 滄海圖書

75 戴顯權 著 / 資料結構 © 滄海圖書

76 轉接盒繞線問題 在一個轉接盒中，我們必須把 轉接盒邊上的點配對連線
連線的規則是根據輸入的點之 配對，例如(1, 4)、(2, 3)、(5, 6) 以及(7, 8)，將這些點之配對在 繞線範圍內連線；而且這些連 線嚴格要求不可以交叉，否則 就會造成短路的現象 戴顯權 著 / 資料結構 © 滄海圖書

77 轉接盒繞線問題 轉接盒邊上有8 個點(一般也稱接 腳)。當我們想要分別連接(1, 3)、 (2, 4)、(5, 6) 以及(7, 8) 這四組接 腳時，如圖4.14(b) 所示的，我們 不可避免地會產生(2, 4) 與(1, 3) 這兩條連線的交叉現象，因此它 不是一個可接受的繞線 戴顯權 著 / 資料結構 © 滄海圖書

78 轉接盒繞線問題 在圖4.14(c) 中，我們所希望連 接的接腳配對為(1, 4)、(2, 3)、 (5, 6) 以及(7, 8)
由於我們可以做到所有連線都沒 有交叉的現象，因此它是一個符 合要求的可接受繞線 戴顯權 著 / 資料結構 © 滄海圖書

79 轉接盒繞線問題 戴顯權 著 / 資料結構 © 滄海圖書