Chapter 3 堆疊與佇列 3.1 堆疊和佇列基本觀念 3.2 堆疊的機入與刪除 3.3 佇列的加入與刪除 3.4 環狀佇列

Presentation on theme: "Chapter 3 堆疊與佇列 3.1 堆疊和佇列基本觀念 3.2 堆疊的機入與刪除 3.3 佇列的加入與刪除 3.4 環狀佇列"— Presentation transcript:

1 Chapter 3 堆疊與佇列 3.1 堆疊和佇列基本觀念 3.2 堆疊的機入與刪除 3.3 佇列的加入與刪除 3.4 環狀佇列
3.5 堆疊與佇列的應用 3.6 如何計算後續表示法

2 堆疊與佇列 堆疊與佇列是資料結構最基本的二個主題，您將會體會以前您所學到的副程式的呼叫，它們是怎麼處理的，為何會有條不紊，不會出差錯。中序的表示式與後序的表示式有何不同，它們之間應如何轉換。

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

4 3.1 堆疊和佇列基本觀念 佇列也是屬於線性串列，與堆疊不同的是加入和刪除不在同一端，刪除的那一端為前端（front），而加入的一端稱為後端（rear）。 由於佇列具有先進先出（First In First Out，FIFO）的特性，因此也稱佇列為先進先出串列，假若佇列兩端皆可做加入或刪除的動作，則稱之為雙佇列（double-ended queue,deque）。

5 3.1 堆疊和佇列基本觀念 堆疊、佇列如圖3.1之(a)、(b)所示。

6 3.1 堆疊和佇列基本觀念 其中(a)堆疊有如一容器，而(b)的佇列有如一排隊的隊伍，最前面的是front所指的地方，因此front所指的位置一定會先被服務，而rear所指的地方是新加入的位置。

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

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

9 3.2 堆疊的加入與刪除

10 3.2 堆疊的加入與刪除 加入一元素10於堆疊的片段程式如下：

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

12 3.2 堆疊的加入與刪除 以下是其程式片段

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

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

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

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

17 3.4 環狀佇列 為了解決此一問題，佇列常常以環狀佇列(circle queue)來表示之，CQ(0: MAX-1)，如圖所示：

18 3.4 環狀佇列 3.4.1 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述
3.4 環狀佇列 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述 rear=(rear+1) % MAX;

19 3.4 環狀佇列 求出rear，主要的用意在於能夠使rear回到前面，看看是否還有空的位置可放。如當rear為MAX-1時，((MAX-1)+1)% MAX，其餘數為0，此時便可進入環狀佇列的前端了。

20 3.4 環狀佇列 以下是我們設計的片段程式

21 3.4 環狀佇列 而環狀佇列的刪除，乃判斷front是否和rear同在一起，若是，則印出環狀佇列是滿的訊息，否則，將front往前移，並加入元素，以下是其片段程式：

22 3.4 環狀佇列 其中 front = (front+1) % MAX ;
3.4 環狀佇列 其中 front = (front+1) % MAX ; 主要的用意，乃希望能將front移到0的位置。讀者是否發現到以上的片段程式有什麼怪異的地方嗎？有的，我們發現環狀佇列會浪費一個空間，如圖所示：

23 3.4 環狀佇列 當rear為MAX-2，front為MAX-1，此時若加入一元素，我們所設計的片段程式會發生“滿”的訊息，主要的用意在於能確保刪除時是正確的。 假若，您不理會也將它加入的話，此時刪除一元素時，則會發生佇列是空的，不合理吧！

24 front = rear = MAX-1 及 tag = 0
3.4 環狀佇列 有沒有方法可以充份的利用此一空間呢？有的，只是需要多加一判斷的變數如tag來輔助之。開始時 front = rear = MAX-1 及 tag = 0

25 3.4 環狀佇列 加入的片段程式

26 3.4 環狀佇列 比較encqueue和encqueue2函數，主要差異在於後者多了tag變數的判斷，因此會多花一些時間，但也可以省一個空間，這就是時間和空間的取捨囉！

27 3.4 環狀佇列 刪除的片段程式

28 3.4 環狀佇列 加入和刪除主要差異在於tag，當tag為1時，表示環狀佇列是滿的，反之tag為0，則表示環狀佇列是空的。

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

30 3.5 堆疊與佇列的應用 假如所要解決的問題是有先進先出的性質時，則宜用佇列來解決，例如作業系統的工作安排（job scheduling），若不考慮特權（priority）的話。

31 3.5 堆疊與佇列的應用 堆疊還有一些很好的用途，就是如何將算術運算式由中序表示式變為後序表示式。一般的算術運算式皆是以中序法來表示，亦即運算子（operator）置於運算元（operand）的中間。 而後序法表示運算子在其運算元後面，如：A * B / C，此乃中序表示式，而其後序表示式是AB * C /。

32 3.5 堆疊與佇列的應用 其實算術運算式由中序變為後序可依下列三步驟進行即可：
3.5 堆疊與佇列的應用 其實算術運算式由中序變為後序可依下列三步驟進行即可： 將式子中的運算單元適當的加以括號，此時須考慮運算子的運算優先順序。 將所有的運算子移到其對應的右括號。 將所有的括號去掉。

33 3.5 堆疊與佇列的應用 如將A*B/ C化為後序表示式，步驟如下： ((A* B)/ C) ((AB)* C)/ AB*C/

34 3.5 堆疊與佇列的應用 再舉一例將A-B/ C+D*E化成後序表示式，步驟如下： ((A-(B/C))+(D*E))
3.5 堆疊與佇列的應用 再舉一例將A-B/ C+D*E化成後序表示式，步驟如下： ((A-(B/C))+(D*E)) ((A(BC)/)-(DE)*)+ ABC/-DE*+

35 3.5 堆疊與佇列的應用

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

37 3.5 堆疊與佇列的應用

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

39 3.5 堆疊與佇列的應用 首先以A+B*C來說明，其情形如下：

40 3.5 堆疊與佇列的應用 再舉一例，如A*(B+C)*D

41 3.5 堆疊與佇列的應用

42 3.5 堆疊與佇列的應用 至於佇列的應用，舉凡銀行櫃台的服務、停車場的問題、大型計算機中心列印報表的情形，以及飛機起飛與降落等等的應用。

43 3.6 如何計算後序表示式 將中序表示式轉為後序表示式後，就可以很容易將此式子的值計算出來，其步驟如下： 將此後序表示式以一字串表示之。
3.6 如何計算後序表示式 將中序表示式轉為後序表示式後，就可以很容易將此式子的值計算出來，其步驟如下： 將此後序表示式以一字串表示之。 每次取一token，若此token為一運算元則將它push到堆疊，若此token為一運算子，則自堆疊pop出二個運算元並做適當的運算，若此token為‘\0’則goto步驟4。

44 3.6 如何計算後序表示式 將步驟2的結果再push到堆疊，goto步驟2。
3.6 如何計算後序表示式 將步驟2的結果再push到堆疊，goto步驟2。 彈出堆疊的資料，此資料即為此後序表示式計算的結果。我們以下例說明之，如有一中序表示式為10+8-6*5轉為後序表示式為 * -，今將利用上述的規則執行之，步驟如下： 因為10為一運算元，故將它push到堆疊，同理8也是，故堆疊有2個資料分別為10和8。

45 3.6 如何計算後序表示式 之後的token為+，故pop出堆疊的8和10做加法運算，結果為18，再次將18push到堆疊。
3.6 如何計算後序表示式 之後的token為+，故pop出堆疊的8和10做加法運算，結果為18，再次將18push到堆疊。 接下來將6和5 push到堆疊。

46 3.6 如何計算後序表示式 之後的token為*，故pop 5和6做乘法運算為30，並將它push到堆疊。
3.6 如何計算後序表示式 之後的token為*，故pop 5和6做乘法運算為30，並將它push到堆疊。 之後的token為-，故pop 30和18，此時要注意的是18減去30，答案為-12（是下面的資料減去上面的資料）