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 堆疊與佇列的應用 3.7 如何計算後序表示式

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 堆疊的加入與刪除 在堆疊的運作上，堆疊的加入必須注意加入的元素是否會超出堆疊的最大容量，因此設定一變數查看它是否超出，每次push 一個元素則top 加1；反之，pop 一個元素則top 減1。我們可以利用一陣列來表示堆疊，如：stack[MAX]，其中MAX 表示堆疊的最大容量。 初始的top 設為–1。

8 3.2 堆疊的加入與刪除 3.2.1堆疊的加入 堆疊的加入應注意堆疊是否為滿的情況，若沒滿，則將輸入的資料放在堆疊的上方。

9 3.2 堆疊的加入與刪除 3.2.1堆疊的刪除 堆疊的刪除應注意堆疊是否為空的，若不是空的，則將資料刪除之。

10 3.3 佇列的加入與刪除 佇列的運作，分別利用rear 變數作用在加入的動作；front 變數作用在刪除的動作，佇列的加入要注意它是否超出最大的容量，rear 變數的初值為–1。注意！先將rear 加1 之後，再加入資料喔!而front 變數之初值為0，刪除的動作是先刪除資料後再將front 加1。

11 3.3 佇列的加入與刪除 3.3.1佇列的加入 佇列的加入是作用在rear 端

12 3.3 佇列的加入與刪除 3.3.2佇列的刪除 佇列的刪除是作用在front 端

13 3.3 佇列的加入與刪除 當佇列的表示方式是Q(1：n)時，常常會發生佇列前端還有空位，但要加入元素時卻發現此佇列已滿的情形，如下圖所示：

14 3.3 佇列的加入與刪除 為了解決此一問題，佇列常常以環狀佇列(circle queue)來表示之，CQ(0: n-1)，如圖所示：

15 3.3 佇列的加入與刪除 3.3.3 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述
3.3 佇列的加入與刪除 環狀佇列的加入 環狀佇列的初始值為front=rear=MAX-1，當有元素欲加入時，利用下一敘述 rear=(rear+1) % MAX;

16 3.3 佇列的加入與刪除 環狀佇列開始的時候，將front 與rear 之初值均設為MAX–1。

17 3.3 佇列的加入與刪除 環狀佇列的刪除 環狀佇列之刪除與之前的線性佇列有所不同

18 3.3 佇列的加入與刪除 是環狀佇列的加入是先找一位置，然後做判斷；但其刪除則是先做判斷，然後再找位置。還有一點要留意的是在環狀佇列永遠會空一個位置，乃是為了辨別是否已額滿或空的。如下圖：假設此環狀佇列cq[]中有10 個元素。

19 3.3 佇列的加入與刪除 1. front 在cq[9]，經過多次的加入後rear 在cq[8]。
3.3 佇列的加入與刪除 1. front 在cq[9]，經過多次的加入後rear 在cq[8]。 2. 加一元素此時(8+1) % 10 = 9，因此rear 指向cq[9]的地方。 3. 此時rear == front，因此輸出Queue is full!，但是從圖得知front 指的位置是空的。假設要繼續使用此空間的話，則下次在刪除環狀佇列的元素時會產生佇列是空的訊息(根據上述的片段程式，當front == rear 時，會顯示Queue is empty!)，這與有許多的元素在環狀佇列中有所不符了。所以環狀佇列會浪費一個空間。 假使一定非用此空間不可，有一種補救的方法，那就是加一tag 變數，並設定front = rear= MAX–1，tag = 0。

20 3.3 佇列的加入與刪除

21 3.3 佇列的加入與刪除

22 3.4 其他型式的佇列 另外二種佇列，一為雙向佇列（deque），二為優先權佇列（priority queue）。Deque 乃是double-ended queue 的縮寫，表示佇列的兩端皆可做為加入和刪除，不同於前述的佇列。

23 3.5 多個堆疊 和單一堆疊的觀念大致上是相同的，例如多個堆疊的加入和刪除也是在同一端。而這種方式在日常生活中也是常常看到的，例如：公司可能會將硬碟容量分割成很多個部份來分給每個員工一些硬碟容量來收發電子郵件。

24 3.5 多個堆疊 3.5.1多個堆疊的加入

25 3.5 多個堆疊

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

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

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

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

30 3.5 堆疊與佇列的應用 如將A*B/ C化為後序表示式，步驟如下： 1. ( ( A * B ) + C )
3.5 堆疊與佇列的應用 如將A*B/ C化為後序表示式，步驟如下： 1. ( ( A * B ) + C ) 2. ( ( A * B ) + C ) => ( ( AB )*C ) + 3. AB *C +

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

32 3.5 堆疊與佇列的應用

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

34 3.5 堆疊與佇列的應用

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

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

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

38 3.5 堆疊與佇列的應用

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

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

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

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

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