第4章 堆疊和佇列 資料結構設計與C++程式應用

Presentation on theme: "第4章 堆疊和佇列 資料結構設計與C++程式應用"— Presentation transcript:

1 第4章 堆疊和佇列 資料結構設計與C++程式應用
Fundamentals of Data Structures and Their Applications Using C++ 第4章 堆疊和佇列 資料結構設計與C++程式應用 版權所有 禁止重製

2 堆疊及其應用 堆疊(Stack) 堆疊是一個有秩序關係的串列結構(Ordered List) 資料的插入和刪除只發生在堆疊的頂端(Top)
使得資料進出堆疊時產生「後進先出」的特性 歐式自助餐之餐盤堆放方式即是一個典型的堆疊結構

3 堆疊及其應用 堆疊的表示法及其基本運作 1. 產生堆疊結構： 利用程式語言的宣告(Declaration)指令，將堆疊宣告成陣列(假設陣
2.將資料放入堆疊(Push)： 更改Top指標後，將資料存入堆疊，但必須先判斷堆疊 是否已滿(使用陣列時)。 3.刪除資料(Pop)： 若堆疊不是空的，則將頂端資料取出，並更改Top指標值。 4.判斷堆疊是否滿溢： 判斷Top指標是否等於N-1？（使用陣列時）。 5.判斷堆疊是否是空的： Top值小於0（陣列）或Top指向NULL（鏈結串列）。

4 堆疊及其應用 堆疊的插入和刪除(採用陣列結構製作)

5 堆疊及其應用 堆疊的插入和刪除(採用鏈結串列結構製作)

6 堆疊及其應用 堆疊的插入和刪除(採用鏈結串列結構製作)

7 堆疊及其應用 堆疊的應用 1.副程式的呼叫和返回 程式A 呼叫副程式 B 副程式B再呼叫副程式C

8 堆疊及其應用 堆疊的應用 2.算術式的轉換 運算子的種類及其優先順序 算術式的三種表示法

9 堆疊及其應用 堆疊的應用 2.算術式的轉換 中置式轉前置式和後置式 【方法1】 (1). 依算術式求值規則用括號將相關運算括起來。
(2). 將運算子移到‘(’的左邊（前置式）或 ‘)’ 的右邊（後置式）。 (3). 取消所有的括號。

10 堆疊及其應用 堆疊的應用 2.算術式的轉換 中置式轉前置式和後置式 【例1】將 A-B*(C+D)/E 轉成後置式的步驟如下： (1)
(2) (3) ABCD+*E/-

11 堆疊及其應用 堆疊的應用 2.算術式的轉換 中置式轉前置式和後置式 (以後置式為例) 【方法2】
(1). 從左到右依次讀取算術式，並令讀入的元素為x。 (2). switch(x){ case('('): 將x放入堆疊; break; case(')'): x=自堆疊頂端取出的運算子; while(x !='('){ 將x輸出至後置式中; x=自堆疊頂端取出的運算子; }

12 堆疊及其應用 case('+') : case('-') : case('*') :
case('/') : y = 堆疊頂端的運算子; // 非取出堆疊資料 while(y 的優先序高於x) 取出堆疊頂端的運算子並輸出至後置式中; y = 堆疊頂端的運算子; } 將x放入堆疊; break; default : // x為運算元 將x輸出至後置式中; (3).最後將殘存於堆疊的運算子一一輸出到後置式，直到堆疊空了為止。

13 堆疊及其應用 堆疊的應用 2.算術式的轉換 【例2】中置式算術式A-B*(C+D)/E轉成後置式的過程

14 堆疊及其應用 堆疊的應用 3.後置式算術式求值 【例3】假設A＝99，B=7，C＝3，D＝5，E＝4，

15 堆疊及其應用 1.每次僅可搬移一個碟片。 2.從某一根柱子上取出之碟片一定要放到另外兩根柱子之一後才可 以再搬另一個碟片。
堆疊的應用 4.河內之塔(Towers of Hanoi) 1.每次僅可搬移一個碟片。 2.從某一根柱子上取出之碟片一定要放到另外兩根柱子之一後才可 以再搬另一個碟片。 3.無論何時，每一根柱子上之碟片都要保持上小下大的排列方式。

16 堆疊及其應用 步驟 < 1> 從 A 柱搬 1 號碟片到 C 柱 步驟 < 2> 從 A 柱搬 2 號碟片到 B 柱
堆疊的應用 4.河內之塔(Towers of Hanoi) 【例4】當 N＝3 時，整個搬移過程為： 步驟 < 1> 從 A 柱搬 1 號碟片到 C 柱 步驟 < 2> 從 A 柱搬 2 號碟片到 B 柱 步驟 < 3> 從 C 柱搬 1 號碟片到 B 柱 步驟 < 4> 從 A 柱搬 3 號碟片到 C 柱 步驟 < 5> 從 B 柱搬 1 號碟片到 A 柱 步驟 < 6> 從 B 柱搬 2 號碟片到 C 柱 步驟 < 7> 從 A 柱搬 1 號碟片到 C 柱

17 佇列及其應用 佇列(Queue) 佇列也是一個有序串列 資料的插入和刪除分別發生在佇列結構的兩端
插入資料的一端叫做尾端(Rear)，刪除資料的一端叫做前端(Front) 資料進出佇列的次序形成「先進者先出」的特性 排隊

18 佇列及其應用 佇列的表示法及基本運作 1.產生佇列結構： 宣告一個陣列結構或鏈結串列結構，並設定成空佇列， 2.將資料加入佇列：
即 Front=Rear=-1 或 Front=Rear=NULL(=0)。 2.將資料加入佇列： 若佇列未滿溢，則改變Rear指標後將資料存入佇列之Rear位置。 3.從佇列刪除一個元素： 若非空佇列，則改變Front指標後將Front所指到之佇列元素刪除。 4.判斷佇列是否滿溢： 當Rear=N-1時，表示佇列滿溢。(假設陣列之大小為N， 並且資料從第0個索引開始存放)。 5.判斷是否為空佇列： 當 Front=Rear時，為空佇列。

19 佇列及其應用 佇列的插入和刪除(以陣列製作)

20 佇列及其應用 佇列的應用 1. 環狀佇列(Circular Queues) 環狀佇列的插入和刪除

21 佇列及其應用 佇列的應用 1. 環狀佇列(Circular Queues)-續 一般佇列與環狀佇列之比較

22 佇列及其應用 佇列的應用 2.優先佇列(Priority Queues) 優先佇列結構(採用陣列實施）

23 佇列及其應用 佇列的應用 2.優先佇列(Priority Queues) 優先佇列結構（採用鏈結串列實施）

24 佇列及其應用 佇列的應用 3.雙向佇列(Double Ended Queues) 左端佇列加入A、B、C，右端佇列加入甲、乙、丙

25 多重堆疊和多重佇列(Multiple Stacks and Queues)

26 多重堆疊和多重佇列(Multiple Stacks and Queues)
多群系統

27 多重堆疊和多重佇列(Multiple Stacks and Queues)
環狀多重堆疊

28 多重堆疊和多重佇列(Multiple Stacks and Queues)