Chapter 4 堆疊和佇列 資料結構導論 - C語言實作.

Presentation on theme: "Chapter 4 堆疊和佇列 資料結構導論 - C語言實作."— Presentation transcript:

1 Chapter 4 堆疊和佇列 資料結構導論 - C語言實作

2 4.1 前言 堆疊(Stack)結構 佇列(Queue)結構 只有單一的出入口，我們稱之為頂端(Top)。
資料的「新增」和「刪除」都從堆疊的頂端進出。 後進入堆疊的資料反而先出來。 佇列(Queue)結構 有一個入口和一個出口，我們稱入口為尾端(Rear)，出口為頭端(Front)(或稱前端)。 資料從尾端「新增」，從頭端「刪除」 。 先進入佇列的資料將先出來。 資料結構導論 - C語言實作

3 4.2 堆疊(Stack) 堆疊具有以下特徵： 堆疊是一個有順序性的資料結構。
資料的「新增」和「刪除」都從堆疊的頂端(Top)這個唯一的出入口。 具有「後進先出(Last In First Out：LIFO)」(或「先進後出」(First In Last Out： FILO))的特性。 資料結構導論 - C語言實作

4 4.2 堆疊(Stack) 資料結構導論 - C語言實作

5 4.2.1 以陣列實作堆疊 以「陣列」實作堆疊時可歸納成底下幾個基本操作：
宣告陣列stack[n]： 陣列大小n即代表堆疊容器的容量，且索引編號為0、1、2、...、n-1。 設定堆疊的頂端指標top： 一開始top=-1，表示堆疊裡空無一物。當top=n-1時，表示堆疊已滿，無法再容納資料了。 判斷堆疊是否已滿： 當top = n-1時，表示堆疊已滿。 資料結構導論 - C語言實作

6 4.2.1 以陣列實作堆疊 判斷堆疊是否已空： 當top < 0時，表示堆疊已空。
新增資料： 將資料放入堆疊的動作我們稱之為push。若堆疊未滿，則top = top + 1後再將資料存入stack [top]位置。 刪除資料： 從堆疊頂端取出資料的動作我們稱之為pop。若非空堆疊，則自堆疊頂端將stack [top]資料取出，然後top = top - 1。 資料結構導論 - C語言實作

7 4.2.1 以陣列實作堆疊 【例1】以陣列來實作堆疊的新增和刪除 資料結構導論 - C語言實作

8 4.2.2 以鏈結串列實作堆疊 以「鏈結串列」實作堆疊時可歸納成底下幾個基本操作：
建立堆疊結構： 宣告一個鏈結串列結構，一開始只有一個名為top的頭節點，它的鏈結欄指向null。 判斷堆疊是否已空： 當top節點指向null時，表示堆疊已空無一物。 資料結構導論 - C語言實作

9 4.2.2 以鏈結串列實作堆疊 新增資料： 將資料放入堆疊的動作我們稱之為push。首先，向記憶體索取一個節點空間x，然後將要新增的資料存入節點x的資料欄。接下來令top所指的節點為y，將x指向y，再將top指向x。 刪除資料： 從堆疊頂端取出資料的動作我們稱之為pop。若非空堆疊，則令top所指之節點為x，且x所指的節點為y。輸出x的資料欄，更改top鏈結指標值，將它指向y。 資料結構導論 - C語言實作

10 4.2.2 以鏈結串列實作堆疊 【例2】以鏈結串列來實作堆疊的新增和刪除 資料結構導論 - C語言實作

11 4.2.2 以鏈結串列實作堆疊 資料結構導論 - C語言實作

12 4.3 堆疊的應用 4.3.1 副程式的呼叫和返回 4.3.2 河內塔(Towers of Hanoi) 4.3.3 運算式的轉換
4.3.4 運算式的求值 資料結構導論 - C語言實作

13 4.3.1 副程式的呼叫和返回 資料結構導論 - C語言實作

14 4.3.2 河內塔(Towers of Hanoi) 河內塔問題是一個非常有趣的智力遊戲，問題描述如下：
假設有編號分別為a、b、c的三根柱子，一開始在a柱上放置了n個中間有孔的圓盤，圓盤的編號由上到下分別為 1，2，…，n，且編號愈大代表圓盤的直徑也愈大。 所謂河內塔問題乃是要將所有n個圓盤從a柱搬移到c柱，且在圓盤搬移的過程中必須遵守下列3條規則： 1.無論何時，每一根柱子上直徑較小的圓盤都要放在直徑較大的圓盤的上面，亦即須保持「上小下大」的排列方式。 2.每次僅能移動一個圓盤。 3.圓盤可以在3根柱子間任意的移動。 資料結構導論 - C語言實作

15 Some tower in Hanoi … =Hanoi Tower? 資料結構導論 - C語言實作

16 4.3.2 河內塔(Towers of Hanoi) 資料結構導論 - C語言實作

17 4.3.2 河內塔(Towers of Hanoi) 當n = 2(有2個圓盤)時，一共需3次搬動，搬動的順序如下：
步驟 1：將1號圓盤從a柱搬到b柱。 步驟 2：將2號圓盤從a柱搬到c柱。 步驟 3：將1號圓盤從b柱搬到c柱。 資料結構導論 - C語言實作

18 4.3.2 河內塔(Towers of Hanoi) 當n = 3(有3個圓盤)時，一共需7次搬動，搬動的順序如下：
步驟 1：將1號圓盤從a柱搬到c柱。 步驟 2：將2號圓盤從a柱搬到b柱。 步驟 3：將1號圓盤從c柱搬到b柱。 步驟 4：將3號圓盤從a柱搬到c柱。 步驟 5：將1號圓盤從b柱搬到a柱。 步驟 6：將2號圓盤從b柱搬到c柱。 步驟 7：將1號圓盤從a柱搬到c柱。 資料結構導論 - C語言實作

19 4.3.2 河內塔(Towers of Hanoi) 資料結構導論 - C語言實作

20 4.3.3 運算式的轉換 「a+b/(c-d)*e」是一個運算式(Expression) 運算式求值必須遵守下列規則：
運算元(Operand)：a、b、c、d、e。 運算子(Operator)：+、-、*、/。 運算式求值必須遵守下列規則： 1.括號內的運算式須優先處理。 2.由左至右。 3.依運算子的優先順序處理，例如先乘除 後加減等。 資料結構導論 - C語言實作

21 4.3.3 運算式的轉換 資料結構導論 - C語言實作

22 4.3.3 運算式的轉換 運算式的表示法： 1. 前置(Prefix)運算式： 運算子放在兩個運算元前面，沒有括號， 不 易閱讀。
運算子放在兩個運算元前面，沒有括號， 不 易閱讀。 2. 中置(Infix)運算式： 運算子放在兩個運算元之間，可以有括號， 最容易閱讀。 3. 後置(Postfix)運算式： 運算子是放在兩個運算元之後，沒有括號， 不易閱讀。 資料結構導論 - C語言實作

23 4.3.3 運算式的轉換 資料結構導論 - C語言實作

24 4.3.3 運算式的轉換 中置運算式轉換成前置運算式： 依據運算式的求值規則，先用括號將相關的運算組合括起來。
將運算子取代左邊最接近的左括號 (。 移除所有的右括號 )。 資料結構導論 - C語言實作

25 4.3.3 運算式的轉換 中置運算式轉換成後置運算式： 依據運算式的求值規則，先用括號將相關的運算組合括起來。
將運算子取代右邊最接近的右括號 )。 移除所有左括號 (。 資料結構導論 - C語言實作

26 4.3.3 運算式的轉換 【例1】中置運算式轉成前置運算式 將中置運算式 a+b/(c-d)*e-f 轉成對應的前置運算式之步驟如下：

27 4.3.3 運算式的轉換 【例2】中置運算式轉成後置運算式 將中置運算式 a+b/(c-d)*e-f 轉成對應的後置運算式之步驟如下：

28 4.3.3 運算式的轉換 資料結構導論 - C語言實作

29 4.3.3 運算式的轉換 資料結構導論 - C語言實作

30 4.3.3 運算式的轉換 【例3】利用堆疊將中置運算式轉換成後置運算式 資料結構導論 - C語言實作

31 4.3.3 運算式的轉換 資料結構導論 - C語言實作

32 4.3.4 運算式的求值 資料結構導論 - C語言實作

33 4.4 佇列(Queue) 佇列具有以下特徵： 佇列是一個有順序性的資料結構。
「新增」時，資料從「入口」進入佇列； 「刪除」時，離「出口」最近的資料先被刪除。 具有「先進先出(First In First Out：FIFO)」(或「後進後出」(Last In Last Out： LILO))的特性。 資料結構導論 - C語言實作

34 4.4 佇列(Queue) 佇列的實例 高速公路收費站等待繳費的車龍。 大學入學指定科目考試排隊量體溫的考生。 戲院售票口排隊買票的人潮。
資料結構導論 - C語言實作

35 4.4.1 以陣列實作佇列 以「陣列」實作佇列時可歸納成底下幾個基本操作：
宣告陣列queue[n]： 陣列大小n即代表佇列容器的容量，且索引編號為0、1、2、...、n-1。 設定佇列的頭指標(front)和尾指標(rear)： 一開始front = rear = -1，表示佇列裡空無一物。請注意！我們將front指標指向佇列中排隊排在最前面一筆資料的前一號位置，而rear指標則指向佇列最後一筆資料之位置。 資料結構導論 - C語言實作

36 4.4.1 以陣列實作佇列 判斷佇列是否已滿： 當rear = n-1時表示佇列已滿。
判斷佇列是否已空： 當front = rear 時表示佇列已空。 新增資料： 若佇列未滿，則rear = rear + 1後再將資料存入queue [rear]位置。 刪除資料： 若非空佇列，則front = front + 1，然後自佇列將資料queue [front] 取出。 資料結構導論 - C語言實作

37 4.4.1 以陣列實作佇列 【例1】以陣列來實作佇列的新增和刪除 資料結構導論 - C語言實作

38 4.4.2 以鏈結串列實作佇列 資料結構導論 - C語言實作

39 4.4.2 以鏈結串列實作佇列 以「鏈結串列 」實作佇列時可歸納成底下幾個基本操作：
宣告一個鏈結串列結構，一開始是一個空佇列，有一個頭節點front和一個尾節點rear，且這兩個節點指標都指向null，即front=rear=null。 判斷佇列是否已空： 當front節點指向null時，表示佇列已空無一物。 資料結構導論 - C語言實作

40 4.4.2 以鏈結串列實作佇列 新增資料： 首先，向記憶體索取一個節點空間x，然後將要新增的資料存入x的資料欄，將x的鏈結欄指向null。若此時為空佇列則front和rear都指向x。否則，令rear所指的節點為y，將y指向x，rear亦指向x。 刪除資料： 若非空佇列，則令front所指的節點為x，且x所指的節點為y。輸出x的資料欄，再將front指向y。 資料結構導論 - C語言實作

41 4.4.2 以鏈結串列實作佇列 資料結構導論 - C語言實作

42 4.4.2 以鏈結串列實作佇列 資料結構導論 - C語言實作

43 4.4.3 佇列的應用 作業系統(Operating System，OS)的工作(Job)排程 優先佇列 資料結構導論 - C語言實作

44 4.5 以陣列／鏈結串列實作堆疊／佇列之比較 資料結構導論 - C語言實作

45 4.5 以陣列／鏈結串列實作堆疊／佇列之比較 資料結構導論 - C語言實作

46 4.6.1 多重堆疊(Multiple Stacks)
用陣列來實作堆疊或佇列可能產生兩個主要缺點： 宣告太多而使用太少，造成記憶體的浪費。 當資料太多而宣告量不足時，造成堆疊滿溢(Overflow)。 多重佇列是採用「共用單一陣列空間」的技巧來對記憶體做更有效之應用。 資料結構導論 - C語言實作

47 4.6.1 多重堆疊(Multiple Stacks)
堆疊空了： 當t[i]=b[i]時，表示第i號堆疊已經空了。 堆疊滿溢： 當t[i]=b[i+1]時，表示第i號堆疊已經滿溢。 資料結構導論 - C語言實作

48 4.6.1 多重堆疊(Multiple Stacks)
第1號堆疊已滿 資料結構導論 - C語言實作

49 4.6.1 多重堆疊(Multiple Stacks)
重分配後便可將資料1f存放至stack[t[1]]=stack[10]號位置。 資料結構導論 - C語言實作

50 4.6.2 多重佇列(Multiple Queues)
佇列滿溢： 當r[i]=b[i]時，表示第i號佇列已經滿溢。 佇列空了： 當f[i]=r[i]時，表示第i號佇列已經空了。 資料結構導論 - C語言實作

51 4.6.2 多重佇列(Multiple Queues)
第1號佇列已經滿溢(r[1]=b[1]=9) 。 資料結構導論 - C語言實作

52 4.6.2 多重佇列(Multiple Queues)
重分配後空出queue[10]和queue[11]，便可供第1號佇列使用 資料結構導論 - C語言實作

53 4.6.3 優先佇列(Priority Queues)
優先佇列─以陣列實作 有一個頭指標f用來指向整個佇列的頭端。 有三個尾指標r_a、r_b和r_c則分別指向A、B、C級佇列的尾端。 r_a也是B級的頭端，r_b也是C級的頭端。 資料結構導論 - C語言實作

54 4.6.3 優先佇列(Priority Queues)
假設有一屬於B級的資料b6要加入佇列，，但queue[8]已經被C級佇列所佔用，因此須： 1. 將c2搬移到queue[10]，再將r_c 改成 10。 2. 將c1搬移到queue[9]。 3. 將b6存入到queue[8]，再將r_b 改成8。 資料結構導論 - C語言實作

55 4.6.3 優先佇列(Priority Queues)
若要刪除B級佇列的資料，則b1須被刪除。一旦刪除了b1，排在它後面的b2、b3、b4、b5和、c1、c2都須往前(左)移動。 資料結構導論 - C語言實作

56 4.6.3 優先佇列(Priority Queues)
優先佇列─以鏈結串列實作 資料結構導論 - C語言實作

57 4.6.3 優先佇列(Priority Queues)
優先佇列─以鏈結串列實作 加入b6的方法為： 1. 向記憶體索取一個節點，令其為x。將b6儲存到x的資料欄。 2. 沿著front找到rear_b，令rear_b的down鏈結所指之節點為y。 3. 令y的鏈結所指之節點為z。 4. 將x指向z，將y指向x。 5. 將rear_b之down鏈結指向x。 資料結構導論 - C語言實作

58 4.6.3 優先佇列(Priority Queues)
優先佇列─以鏈結串列實作 刪除b1的方法為： 1. 沿著front找到rear_a，令rear_a的down鏈結所指之節點為x。 2. 令x的鏈結所指之節點為y。 3. 令y的鏈結所指之節點為z。 4. 將x指向z。 5. 將y歸還給記憶體串列。 資料結構導論 - C語言實作

59 4.6.4 環狀佇列(Circular Queues)
以「陣列」實作「環狀佇列」時可歸納成底下幾個基本操作： 宣告陣列queue[n]： 陣列大小n即代表佇列容器的容量，且索引編號為0、1、2、...、n-1。 設定佇列的頭指標(front)和尾指標(rear)： 一開始佇列裡空無一物，front = rear = n-1，而非 -1。我們仍然將front指標指向佇列中排隊排在最前面一筆資料的前一號位置，而rear指標則指向佇列最後一筆資料之位置。 資料結構導論 - C語言實作

60 4.6.4 環狀佇列(Circular Queues)
判斷佇列是否已滿： 當front=(rear+1) mod n時，表示佇列已滿。 判斷佇列是否已空： 當front=rear 時，表示佇列已空。 新增資料： 若佇列未滿，則rear=(rear+1) mod n後，再將資料存入queue[rear]位置。 刪除資料： 若非空佇列，則front=(front+1) mod n，然後自佇列將資料queue[front]取出。 資料結構導論 - C語言實作

61 4.6.4 環狀佇列(Circular Queues)
【例1】以陣列來實作環狀佇列的新增和刪除 【解答】假設有一個陣列queue[4](即n=4)，我們運用queue陣列來模擬環狀佇列的運作過程如圖4.24所示。為方便起見，我們用f來代表front指標，用r來代表rear指標。 資料結構導論 - C語言實作

62 4.6.4 環狀佇列(Circular Queues)

63 4.6.4 環狀佇列(Circular Queues)
環狀佇列的幾個主要特徵： 環狀佇列乃用「陣列」來實作。 環狀佇列之功能在對記憶體做更有效之應用。 環狀佇列不須搬移資料。 環狀佇列queue[n]最多能存放n-1筆資料。 環狀佇列資料被刪除後所空下來的位置可以再利用。 資料結構導論 - C語言實作

64 4.6.4 環狀佇列(Circular Queues)

65 4.6.5 雙向佇列(Double Ended Queues)
雙向佇列(簡稱Deque) f[0] 用來指向左邊佇列的頭。 r[0] 用來指向左邊佇列的尾。 f[1] 用來指向右邊佇列的頭。 r[1] 用來指向右邊佇列的尾。 資料結構導論 - C語言實作

66 4.6.5 雙向佇列(Double Ended Queues)
雙向佇列(簡稱Deque) 在左邊佇列依序新增0a、0b和0c 在右邊佇列依序新增1a、1b、1c、1d和1e 資料結構導論 - C語言實作

67 4.6.5 雙向佇列(Double Ended Queues)
雙向佇列(簡稱Deque) 從左邊佇列刪除一筆資料 從右邊佇列刪除兩筆資料 資料結構導論 - C語言實作

68 4.6.5 雙向佇列(Double Ended Queues)
【例1】何種情況下表示雙向佇列已滿溢？ 【解答】 當r[0]+1=r[1]時，表示雙向佇列已滿溢。 資料結構導論 - C語言實作

69 4.6.5 雙向佇列(Double Ended Queues)
【例2】何種情況下表示雙向佇列為一空佇列？ 【解答】 當f[0]=r[0]時，表示雙向佇列的左邊為一空佇列。 當f[1]=r[1]時，表示雙向佇列的右邊為一空佇列。 當f[0]=r[0]且f[0]=r[0]時，表示整個雙向佇列為一空佇列。 資料結構導論 - C語言實作

70 4.6.5 雙向佇列(Double Ended Queues)
【例3】試說明新增資料到雙向佇列的流程？ 【解答】 minus - - 資料結構導論 - C語言實作

71 4.6.5 雙向佇列(Double Ended Queues)
【例4】試說明從雙向佇列刪除一筆資料的流程？ 【解答】 minus 資料結構導論 - C語言實作