4.4 佇列 特徵： c b a c b d c b 新增 d 刪除 入口 入口 入口 尾端(rear) 尾端(rear) 尾端(rear)

Presentation on theme: "4.4 佇列 特徵： c b a c b d c b 新增 d 刪除 入口 入口 入口 尾端(rear) 尾端(rear) 尾端(rear)"— Presentation transcript:

1 4.4 佇列 特徵： c b a c b d c b 新增 d 刪除 入口 入口 入口 尾端(rear) 尾端(rear) 尾端(rear)
4.4 佇列 特徵： 入口 入口 入口 新增 d 刪除 c b a c b d c b 尾端(rear) 尾端(rear) 尾端(rear) 頭端(front) 頭端(front) 頭端(front) 出口 出口

2 4.4.1 以陣列實作佇列 2

3 4.4.1 以陣列實作佇列—移動門 (ch4_queue_1.java)
適用於限量服務，不適合不限量、但座位有限的服務 優點：簡單 缺點：還有空位卻認為已滿 解決方法：當有 remove 動作時，搬移資料，讓剩下的所有佇列資料都由陣列索引位置 0 開始 或參考 4.5.5 環狀 佇列

4 4.4.2以串列實作佇列(ch4_queue_2.java)
class Node { int data; Node link; } class Queue { Node front; Node rear;

5 4.4.2以串列實作佇列(ch4_queue_2.java)

6 4.4.2以串列實作佇列(ch4_queue_2.java)
基本動作如下： 建立一個 空佇列：生成 front 跟 rear 節點，而且兩者的 link 都是 null void add(int data): 生成新節點，將 data 值存在此節點，依 佇列是否為空，分別處理(第 4 頁投影片) int remove( ): 刪除並傳回佇列頭端資料 int getfront( ): 傳回頭端資料 int getrear( ): 傳回尾端資料 boolean empty( ): 傳回佇列是否為空之布林值 練習： int getlength()：傳回長度 如果想以串列實作，但又要限制佇列長度(最多為 n)，則可以檢查 getlength() 是否等於 n ，來判斷是否佇列已滿

7

8 4.5 變形堆疊和變形佇列 4.5.1, 4.5.2 多重堆疊，多重佇列 [課本這兩節跳過] 重新設計：
課本：將一陣列切成 3 段，每段實作一堆疊(佇列)，當某一堆 疊(佇列)滿了，其他堆疊(佇列)還有空間時，需重新分配，處 理起來太複雜。其實可以用之前設計之 Stack 或 Queue 來實作 。 重新設計： class ThreeStack { Stack s1; Stack s2; Stack s3; int s1_max_size; //optional int s2_max_size; //optional int s3_max_size; //optional void push(int i, int data) int pop(int i) boolean full(int i) boolean empty(int i) } class ThreeQueue { Queue q1; Queue q2; Queue q3; int q1_max_size; //optional int q2_max_size; //optional int q3_max_size; //optional void add(int i, int data) int remove(int i) boolan full(int i) boolean empty(int i) } 如果對堆疊容量有設限

9 4.5.1, 4.5.2 多重堆疊，多重佇列(重新設計，補充) 也可擴充為可變長度之多重堆疊 (ch4_MultiStack.java)
其方法 (以多重堆疊為例：ch4_threestack.java) 建構子: 初始化 3 個堆疊 void push(int i, int data)： 新增資料 data 到第 i 個堆疊 int pop(int i): 由第 i 個堆疊取出資料(要移除) boolean full(int i): 檢查第 i 個堆疊是否滿了 (對堆疊容量 有設限時才需要) boolean empty(int i)：檢查第 i 個堆疊是否為空 也可擴充為可變長度之多重堆疊 (ch4_MultiStack.java) 建構子：以整數陣列代表需要新增的堆疊的各個長度限 制

10 4.5.3 優先佇列 課本作法 1：將一陣列切成 3 段，每段實作一佇列， 由左到右分級 課本作法 2：以鍊結串列

11 4.5.3 優先佇列 (補充) 重新設計: 視為一個佇列，由 3 個佇列實作，新增時可 設定要加入第幾個佇列。移除時會由 q1, q2, q3 依續移 除 常用於服務有分等級時，例如 q1 為頭等艙旅客，q2 為商務艙旅客，q3 為經濟艙旅客。 add 表示旅客到達櫃台排隊。 remove 表示請排在最前面旅客到櫃台接受服務 (但需依照等級) class PriorityQueue { Queue q1; Queue q2; Queue q3; int q1_max_size; int q2_max_size; int q3_max_size; void add(int i, int data) int remove( ) boolan full( ) boolean empty( ) } 練習： 請畫出經過以下動作後，各佇列內容： add(1, 1)、add(2,2)、add(3,3)、add(2,4)、 remove()、remove()、remove()、add(1,5)、 remove()

12 4.5.4 雙向佇列 (DQueue) 課本：將一個陣列切成 2 半 重新設計 class DQueue { Queue q1;
int max_size; //兩個佇列長度和 void add(int i, int data) int remove(int i ) boolan full( ) boolean empty( ) { return q1.empty() && q2.empty(); }

13 4.5.5以陣列實作環狀佇列(ch4_cqueue.java)
4.4.1 以陣列實作佇列的缺點 改進的想法： 當有 remove 動作時，搬移資料，讓剩下的所有佇列資料 都由陣列索引位置 0 開始 (作業) 將陣列的頭尾相接，以利用空出來的位置

14 4.5.5 環狀佇列 (ch4_cqueue.java)

15 4.5.5 環狀佇列

16

17 作業 為了使用陣列來實作 “不限量、但座位有限” 的佇列 服務，請改進 ch4_queue_1.java 還有空位卻認為 已滿的缺點，當有 remove 動作時，搬移陣列資料 ，讓剩下的所有佇列資料都由陣列索引位置 0 開始 ( 由於以上這個特性，這樣的佇列不需要 front )。請 改寫 ch4_queue_1.java 所有方法，並加以測試。 請以堆疊陣列完成 可變長度之多重堆疊的相關方法 ，並加以測試 完成 優先佇列 的相關方法，並加以測試