第五章　堆疊 5-1 認識佇列 5-2 佇列的應用.

Presentation on theme: "第五章　堆疊 5-1 認識佇列 5-2 佇列的應用."— Presentation transcript:

1 第五章　堆疊 5-1 認識佇列 5-2 佇列的應用

2 認識佇列 可以使用陣列或串列來建立一個佇列。不過堆疊只需一個top，指標指向堆疊頂，而佇列則必須使用front和rear兩個指標分別指向前端和尾端，如下圖所示：

3 佇列的工作運算 佇列是一種抽象型資料結構(Abstract Data Type, ADT)，它有下列特性： 佇列五種工作定義：
具有先進先出(FIFO)的特性。 擁有兩種基本動作加入與刪除，而且使用front與rear兩個指標來分別指向佇列的前端與尾端。 CREATE 建立空佇列。 ADD 將新資料加入佇列的尾端，傳回新佇列。 DELETE 刪除佇列前端的資料，傳回新佇列。 FRONT 傳回佇列前端的值。 EMPTY 若佇列為空集合，傳回真，否則傳回偽。

4 佇列的陣列實作 佇列宣告為queue[20]，且一開始front和rear均預設為-1(因為C語言陣列的索引從0開始)，表示空佇列。
加入資料時請輸入"1"，要取出資料時可輸入"2"，將會直接印出佇列前端的值，要結束請按"3"。

5 範例程式：ch05_01.java

6 事件說明表 事件說明 front rear Q(1) Q(2) Q(3) Q(4) 空佇列Q data1進入 1 data1 data2進入
data1進入 1 data1 data2進入 2 data2 data3進入 3 data3 data1離開 data4進入 4 data4 data2離開 data5進入 data5無法進入

7 從上圖中可以發現明明在佇列中還Q(1)與Q(2)兩個空間，但新的資料data5，因為rear=n(n=4)，所以會認為佇列已滿(Queue-Full)，不能再加入。
這時候，您可以將佇列中資料往前挪移，移出空間讓新資料加入。

8 範例 5.1.1 (1).下列何者不是佇列(Queue)觀念的應用？ (2).下列哪一種資料結構是線性串列？
(A)作業系統的工作排程(B)輸出入的工作緩衝(C)河內塔的解決方法(D)中山高速公路的收費站收費 (2).下列哪一種資料結構是線性串列？ (A)堆疊(B)佇列(C)雙向佇列(D)陣列(E)樹

9 範例 5.1.2 設一佇列(Queue)存於全長為N之密集串列(Dense List)Q內，HEAD、TAIL分別為其開始及結尾指標，均以nil表其為空。現欲加入一新資料(New Entry)，其處理可為以下步驟，請依序回答空格部分。 1.依序按條件做下列選擇： 若(1) ，則表Q已存滿，無法做插入動作。 若HEAD為nil，則表Q內為空，可取HEAD=1，TAIL=(2) 。 若TAIL=N，則表(3) 須將Q內由HEAD到TAIL位置之資料，移至由1到(4) 之位置，並取TAIL=(5) ，HEAD=1。 2.TAIL=TAIL+1。 3.new entry移入Q內之TAIL處。 4.結束插入動作。

10 以鏈結串列實作佇列 佇列除了能以陣列的方式來實作外，我們也可以鏈結串列實作佇列。
在宣告佇列類別中，除了和佇列類別中相關的方法外，還必須有指向佇列前端及佇列尾端的指標，即front及rear。

11 範例程式： ch05_02.java

12 佇列的應用 佇列在電腦領域的應用也相當廣泛，例如： 如在圖形的走訪的先廣後深搜尋法(BFS)，就是利用佇列。
可用於計算機的模擬(simulation)；在模擬過程中，由於各種事件(event)的輸入時間不一定，可以利用佇列來反應真實狀況。 可作為CPU的工作排程(Job Scheduling)。利用佇列來處理，可達到先到先做的要求。 例如「線上同時週邊作業系統」的應用，也就是讓輸出入的資料先在高速磁碟機中完成，接下來將磁碟資料輸出到列表機是由系統軟體主動負責，這也是應用了佇列的工作原理。

13 環狀佇列 一種環形結構的佇列，它是以一種Q(0:n-1)的一維陣列，同時Q(0)為Q(n-1)的下一個元素。
指標front永遠以逆時鐘方向指向佇列中第一個元素的前一個位置，rear則指向佇列目前的最後位置。 一開始front和rear均預設為-1，表示為空佇列，也就是說如果front=rear則為空佇列。另外有： rear(rear+1) mod n front(front+1) mod n

14 上述之所以將front指向佇列中第一個元素前一個位置。
原因是環狀佇列為空佇列和滿佇列時，front和rear都會指向同一個地方，如此一來我們便無法利用front是否等於rear這個判斷式來決定到底目前是空佇列或滿佇列。

15 範例程式：ch05_03.java 底下我們以java語言來實作一個環狀佇列的工作運算。當要取出資料時可輸入“0”，要結束時可輸入“-1”。
執行結果：

16 優先佇列 為一種不必遵守佇列特性－FIFO(先進先出)的有序串列。
其中的每一個元素都賦予一個優先權(Priority)，加入元素時可任意加入，但有最高優先權者(Highest Priority Out First, HPOF)則最先輸出。 在電腦中CPU的工作排程，優先權排程(Priority Scheduling, PS) 就是一種來挑選行程的「排程演算法」 (Scheduling Algotithm)，也會使用到優先佇列，好比層級高的使用者，就比一般使用者擁有較高的權利。

17 甘特圖 設定每個P1、P2、P3、P4的優先次序值分別為2,8,6,4(此處假設數值越小其優先權越低；數值越大其優先權越高)，以下就是以甘特圖(Gantt Chart)繪出優先權排程(Priority Scheduling, PS)的排班情況： 當各元素以輸入先後次序為優先權時，就是一般的佇列，假如是以輸入先後次序做為最不優先權時，此優先佇列即為一堆疊。

18 雙向佇列 雙向佇列(Deques)是英文名稱(Double-ends Queues)的縮寫，雙向佇列(Deque)就是一種前後兩端都可輸入或取出資料的有序串列。如下圖所示：

19 範例程式：ch05_04.java