untitled

Size: px

Start display at page:

Download "untitled"

淯百虞
7 years ago
Views:

1 佇列 (Queue) 本章學習目標 1. 讓讀者了解日常生活有許多例子都是佇列的應用 2. 說明佇列的運作原理本章內容 5-1 佇列 5-2 以陣列來製作佇列 5-3 環形佇列 (circular queue) 5-4 進階佇列本章重點整理課後評量

2 5-1 佇列佇列 (Queue) 是一種先進先出 (First In First Out, FIFO) 的有序串列, 它與堆疊處理資料方式是不大一樣的, 亦即資料處理是在不同邊進行, 也就是資料由一端加入, 由另一端刪除因此, 日常生活中, 也有一些佇列的例子, 如排隊上公車排隊買電影票或是超市排隊付帳等, 皆是先到達的先處理後到的後處理如圖 5-1 所示完成租片程序的人 ( 已取出的資料 ) 前端 (rear) 尾端 (rear) 加入圖 5-1 佇列的例子 1. 一群相同性質元素的組合, 即有序串列 (Ordered List) 2. 具有 FIFO(First In First Out) 先進先出的性質 3. 加入元素的動作發生在 Rear( 後 ) 端 4. 刪除元素的動作發生在 Front( 前 ) 端 5. Add/Delete 的動作皆發生在不同兩端如圖 5-2 所示 5-2 圖 5-2 佇列的基本運作

3 佇列 (Queue) 1. Add( 或 Enqueue): 由佇列的後端 (Rear ) 加入一個新項目 2. Delete( 或 Dequeue): 從佇列的前端 (Front ) 刪除一個項目 3. IsFull: 判斷佇列是否已滿, 若已滿為真 ( True), 否則為假 ( False) 4. IsEmpty: 判斷佇列是否為空, 若空為真 ( True), 否則為假 ( False) 插入元素 Add 刪除元素 Delete 01 Procedure Add(item,Queue) 01 Procedure Delete(item, Queue) begin begin if (Rear=N-1) Queue Is Full; //Queue 已滿 if (Front=Rear) Queue Is Empty; //Queue 為空 05 else 05 else 06 { 06 { 07 Rear=Rear+1; 07 Front=Front+1; 08 Queue[Rear]=item; 08 item=queue[front]; 09 } 09 } 10 end 10 End 運作過程 : 運作過程 : 5-3

4 假設有一個空的 Queue, 實施下列的動作 : Add A Add B Add C Delete Delete Add D 請呈現以上佇列運作的過程空的 Queue Front= N-1 Rear=-1 Add Add Add A 到 Queue B 到 Queue C 到 Queue Rear 後端 A B C N-1 Front=-1 Rear=2 Delete 從 Queue Front 頭端 Rear 尾端 A B C N-1 Front=0 Rear=2 5-4

5 佇列 (Queue) Delete 從 Queue Front 頭端 Rear 後端 B C N-1 Front=1 Rear=2 Add D 到 Queue Front 頭端 Rear 後端 C D N-1 Front=1 Rear=3 檔案在附書光碟中 ADD A,B,C ADD E 刪除二項佇列經常應用在電腦中, 一般作業系統內均有一個工作佇列 (job queue), 若系統不考慮工作的優先權時, 則工作將依進入系統的先後順序來處理, 亦即先到的工作先處理例如 : 我們使用的印表機印表的工作也是採用佇列的特性來處理, 其作法就是先送來的資料先印列, 如果有兩個或兩個以上的資料, 則將它們先放到工作排程佇列中等待列印 5-5

6 1. 作業系統的工作排程 2. 計算機的模擬程式 3. 磁碟管理的輸出入 (input/output) 排序 4.I/O 的緩衝區 (Buffer) 上 5.Priority Queue 6. 圖形的 BFS 廣度追蹤例如 : 作業系統的工作排程如圖 5-3 所示圖 5-3 作業系統的工作排程 5-2 以陣列來製作佇列製作佇列最常用的方法就是利用一維陣列來完成其製作的過程如下 : 1. 產生佇列結構 : 宣告一個陣列結構方法 :Create(Queue) // 指建立一個空的 Queue 製作 : 利用 VB 語言 01 Dim N As Integer = 10 Dim Queue(N) As String Dim Rear As Integer = -1 Dim Front As Integer = -1 ' 定義佇列大小 ' 宣告及建立佇列 ' 宣告佇列的尾端 ' 宣告佇列的前端陣列的記憶體配置 ( 空的 Queue) Front= N-1 Rear=-1 5-6

7 佇列 (Queue) 2. 將資料加入佇列 (Add 動作 ): 將資料 (item) 加入到 Queue 中 ; 成為 Rear 端元素如果佇列已滿, 則無法進行方法 :Add(item, Queue) Procedure Add(item, Queue) begin if (Rear=N-1) Queue Is Full; //Queue 已滿 else { Rear=Rear+1; Queue[Rear]=item; } end 假設有一個空的 Queue, 實施下列的動作 : Add Add Add A 到 Queue B 到 Queue C 到 Queue 請呈現以上佇列運作之後的 Front 與 Rear 之值 Rear 後端 A B C N-1 Front=-1 Rear=2 3. 刪除資料 (Delete 動作 ): 指刪除 Queue 的 Front 頭端元素, 如果 Queue 是空, 則無法進行方法 :Delete(item,Queue) 5-7

8 Procedure Delete(item, Queue) begin if (Front=Rear) Queue Is Empty; //Queue 為空 else { Front=Front+1; item=queue[front]; } end 假設有一個 Queue, 已經有 A,B,C 三個資料項, 如果再實施下列的動作 : Delete 從 Queue 請呈現以上佇列運作之後的 Front 與 Rear 之值 Front 頭端 Rear 尾端 A B C N-1 Front=0 Rear=2 4. 判斷佇列是否已滿 : 若使用陣列時, 判斷 Queue 是否已滿 ( 亦即 Rear 是否等於 N-1), 若是則傳回 True, 否則傳回 False 方法 :IsFull(Queue) 判斷佇列是否已滿 Procedure IsFull(Queue) begin if (Rear=N-1) return True; //Queue 已滿 else return False; //Queue 尚未滿 end 5-8

9 佇列 (Queue) 在佇列中, 當 Rear=N-1 時, 並不能保證 Queue 真的已滿 Front 頭端 Rear 尾端 C D E Z N-1 在上圖中, 判斷佇列是否為滿的副程式 IsFull(Queue), 必須要額外增加一個判斷條件為 :if (Front=-1), 否則像上圖中, 尚有 2 個空間, 而結果卻為滿判斷佇列是否為滿的副程式 Procedure IsFull(Queue) begin if (Rear=N-1) And (Front=-1) return True; //Queue 已滿 else return False; //Queue 尚未滿 end 5. 判斷佇列是否為空 : 若使用陣列時, 判斷 Queue 是否是空 ( 亦即 Front=Rear), 若是則傳回 True, 否則傳回 False 方法 :IsEmpty(Queue) 判斷佇列是否為空 Procedure IsEmpty (Queue) begin if (Front=Rear) return True; // Queue 為空 else return False; // Queue 不為空 end 5-9

10 請實作 Queue 佇列, 可以讓使用者加入或刪除資料加入動作刪除動作在附書光碟中 5-3 環形佇列 (circular queue) 由於佇列有一個問題, 就是前端 (Front) 尚有空位時, 卻再加入元素時, 發現此佇列已滿解決方法 : 使用環形佇列 (circular queue) 如圖 5-4 所示 1. 環狀佇列就是一種環形結構的佇列, 它是利用一種 Q[ 0: N-1] 的一維陣列, 同時 Q[0] 為 Q[N-1] 的下一個元素 2. 最多使用 (N-1) 個空間佇列滿了, 浪費一個空格沒有使用, 若再加入一個項目時, Rear 等於 0, 也就是 Front 等於 Rear, 如此無法分辨此時佇列是空的還是滿的因此, 環形佇列必須浪費一個空格當 Front 等於 Rear 時, 環形佇列為空的當 (Rear+1) Mod N 等於 Front 時, 環形佇列為已滿 5-10

11 佇列 (Queue) 圖 5-4 環形佇列 (circular queue) 環形佇列的基本運作功能基本製作之方法 : 最多使用 (n-1) 個空間 1. 產生環形佇列結構 : 宣告一個陣列結構方法 :Create(CQueue) // 指建立一個空的 Circular Queue 製作 : 利用 VB 語言 Dim N As Integer = 10 Dim CQueue(N) As String Dim Rear As Integer = -1 Dim Front As Integer = -1 ' 定義環形佇列大小 ' 宣告及建立環形佇列 ' 宣告環形佇列的尾端 ' 宣告環形佇列的前端 5-11

12 陣列的記憶體配置 ( 空的 Circular Queue) Front=-1 Rear=-1 2. 將資料放入環形佇列 (Add 動作 ): 將資料 (item) 加入到 Circular Queue 中方法 :Add(item, CQueue) 製作 : 演算法 Procedure Add(item,CQueue) begin if((rear+1)mod N=Front) Circular Queue Is Full; //Circular Queue 已滿 else { CQueue[Rear]=item; } end 5-12

13 佇列 (Queue) 假設有一個空的環形佇列 CQueue, 實施下列的動作 : Add A Add B,C Delete Add D Delete Add E,F,G,H,I Add J Delete Delete Delete Delete Delete Delete Delete 請呈現以上佇列運作之後的 Front 與 Rear 之值空佇列 Front=-1 Rear=-1 加入 A Front=-1 Rear=0 加入 B,C Front=-1 Rear=2 刪除 Front=0 Rear=2 加入 D Front=0 Rear=3 刪除 Front=1 Rear=3 5-13

14 加入 E,F,G,H,I Front=1 Rear=0 佇列已滿加入 J Front=1 Rear=1 失敗刪除 7 次 Front=0 Rear=0 佇列為空 3. 刪除資料 (Delete 動作 ): 指刪除 Circular Queue 的元素方法 :Delete(item,CQueue) 演算法 Procedure Delete(item, CQueue) begin if (Front=Rear) Circular Queue Is Empty; //Queue 為空 else { Front=(Front+1) Mod N item=cqueue[front]; } end 分析 : a. 若硬要使用 N 個空間, 則 Rear=Front 條件式成立時, 則無法區分出 Queue 是否真的 Full 或 Empty 如下圖所示: 5-14

15 佇列 (Queue) b. 判斷 Queue 是否已滿或為空, 則使用相同的條件式 (Rear=Front) c. 加入或刪除動作的時間複雜度均為 O(1) 僅剩下一個空間 Front=1 Rear=0 再加入一項資料 J 時,Rear=1 使得 Front=Rear 環形佇列已滿僅剩下一筆資料 Front=1 Rear=0 再刪除一項資料 A 時,Front=0 使得 Front=Rear 環形佇列已空 5-15

16 表 5-7 一般佇列與環狀佇列之比較表一般佇列環狀佇列陣列宣告 q[n] q[n] 陣列元素 q[0],q[1],,q[n-1] q[0],q[1],,q[n-1] 加入資料的位置 rear=rear+1 rear = (rear+1) mod n 刪除資料的位置 front=front+1 front = (front+1) mod n 判斷是否為空佇列 front=rear front=rear 判斷佇列是否滿溢 rear=n-1 front=(rear+1) mod n 佇列可儲存之元素個數 n n-1 佇列中僅剩一個元素 rear=front+1 rear=(front+1) mod n 請撰寫一個環形佇列的程式 1. 加入 5 個資料項 2. 刪除 A 資料項加入 item 刪除 item 5-16 在附書光碟中

17 佇列 (Queue) 環形佇列的改良改良版製作之方法 : 可以使用 N 個空間作法 : 另外再增加一個變數 (Tag) 來判斷, 每一次的動作, 例如 : 當每次加入資料時, 將 Tag 設為 1, 而刪除資料時設為 0 因此, 在檢查 Front 是否等於 Rear 時, 先再檢查 Tag 的狀態即可 1. 產生環形佇列結構 : 宣告一個陣列結構方法 :Create(Queue) // 指建立一個空的 Queue 製作 : 利用 VB 語言 Dim N As Integer = 10 ' 定義環形佇列大小 Dim CQueue(N) As String ' 宣告及建立環形佇列 Dim Rear As Integer = -1 ' 宣告環形佇列的尾端 Dim Front As Integer = -1 ' 宣告環形佇列的前端 Dim bool As Integer Tag=0 ' 當 CQueue 為 Full 時, 則 Tag=1, 否則 Tag=0 2. 將資料加入環形佇列 (Add 動作 ): 將資料 (item) 加入到 Circular Queue 中方法 :Add(item, CQueue) Procedure Add(item,CQueue) Begin Rear=(Rear+1) Mod n if (Rear=Front) And (Tag=1) CircularQueue Is Full; //Queue 已滿 else { CQueue[Rear]=item; if(rear=front) then Tag=1; } End 5-17

18 3. 刪除資料 (Delete 動作 ): 指刪除 Circular Queue 的元素方法 :Delete(item,CQueue) Procedure Delete(item, CQueue) begin if (Front=Rear) And (Tag=0) Circular Queue Is Empty; //Queue 為空 else { Front=(Front+1) Mod n item=cqueue[front]; if(rear=front) then Tag=0; } end 4. 分析 : 最多可以利用到 N 個空間 Add 與 Delete 動作均須額外多了一個條件判斷式 5-4 進階佇列除了前面所提到的一般佇列與環狀佇列之外, 在某些情況之下, 也會使用到比較特殊的佇列, 例如 : 優先佇列 (priority queue) 及雙向佇列 (double-ended queue: deque) 優先佇列 (priority queue) 在優先佇列中, 其元素的加入及刪除不須要遵守先進先出的特性這種情況在日常生活中, 時常遇到例如 : 醫院的急診室捷運座位提供老幼婦孺者之仁愛座等等 5-18

19 佇列 (Queue) 為一種不必遵守佇列特性 -FIFO( 先進先出 ) 的有序串列每一個佇列的元素, 都給予一個優先順序權, 其數字最大者代表有最高優先權優先佇列可以利用陣列結構及鏈結串列來解決在經常需要大量資料異動時, 無法預先知道需要保留多少尾部的空間給插入的工作使用 ( 採用陣列實施 ) 如圖 5-5 所示圖 5-5 優先佇列結構其中 : A1:front_a,A 級佇列的首端 A2:rear_a,A 級佇列的尾端 B1:front_b,B 級佇列的首端 B3:rear_b,B 級佇列的尾端 C1:front_c,C 等級佇列的首端 C4:rear_c,C 等級佇列的尾端雙向佇列 (double-ended queue:deque) 雙向佇列 (Deque) 是一種特殊的資料結構, 它的兩端都可做加入與取出資料的動作, 不像 Stack 的 LIFO 或 Queue 的 FIFO 亦即它是一種前後兩端都可輸入或取出資料的有序串列如圖 5-6 所示 5-19

20 圖 5-6 雙向佇列 (Deque) 假設我們循序輸入一串數字 :1,2,3,4,5,6,7, 請問是否可以輸出呢? 循序輸入一串數字 :1,2,3,4,5,6,7 順序如下 : 輸出 : 先輸出 5, 再輸出 1, 又輸出 7, 但是, 下一個輸出不是 2 就是 6, 無法輸出 4, 因此, 在循序輸入 1,2,3,4,5,6,7 的情況之下, 無法得到的輸出結果 5-20

21 佇列 (Queue) 本章重點整理佇列 (Queue): 是一種先進先出 (First In First Out, FIFO) 的有序串列例子 : 如排隊上公車排隊買電影票佇列(Queue) 的定義 1. 一群相同性質元素的組合, 即有序串列 (ordered List) 2. 具有 FIFO(First In First Out) 先進先出的性質 3. 加入元素的動作發生在 Rear( 尾 ) 端 4. 刪除元素的動作發生在 Front( 前 ) 端 5. Add/Delete 的動作皆發生在不同一端佇列的應用 1. 作業系統的工作排程 2. 計算機的模擬程式 3. 磁碟管理的輸出入 (input/output) 排序 4.I/O 的緩衝區 (Buffer) 上 5.Priority Queue 6. 圖形的 BFS 廣度追蹤環形佇列的定義 1. 環狀佇列就是一種環形結構的佇列, 它是以一種 Q( 0: N-1) 的一維陣列, 同時 Q(0) 為 Q(N-1) 的下一個元素 2. Front( 前端 ) 永遠是以逆時鐘方向指向佇列中第一個元素的前一個位置,Rear( 尾端 ) 則指向佇列目前的最後位置 3. 最多使用 (N-1) 個空間優先佇列 (priority queue): 在優先佇列中, 其元素的加入及刪除不需要遵守先進先出的特性例如 : 醫院的急診室 5-21

22 優先佇列的定義為一種不必遵守佇列特性-FIFO( 先進先出 ) 的有序串列 1. 插入任意鍵值的動作 2. 刪除最大或最小鍵值動作 3. 當各元素以輸入先後次序為優先權時, 就是一般的佇列 4. 如是以輸入先後次序做為最不優先權時, 此優先佇列即為一堆疊雙向佇列 (double-ended queue: dequeue): 它的兩端都可做置入與取出資料的動作, 不像 Stack 的 FILO 或 Queue 的 FIFO 亦即它是一種前後兩端都可輸入或取出資料的有序串列 5-22

23 佇列 (Queue) B 一基本題題庫來源 : 四技研究所及高普考 1. 請詳細寫出佇列的定義為何? 及其應用實例? 至少列出 5 項 2. 假設要實作佇列時須考慮哪些基本操作 (Operation)? 至少列出 5 項 3. 試比較堆疊和佇列在應用上之差異 4. 請寫出 Add 插入元素到佇列的演算法 5. 請寫出從佇列 Delete 刪除元素的演算法 6. 假設有一個空的 Queue, 實施下列的動作 : Add A 到 Queue Add B 到 Queue Add C 到 Queue Add D 到 Queue Delete 請呈現以上佇列運作之後的 Front 與 Rear 之值 7. 當一開始狀態為 front=rear=-1 的環狀佇列, 若加入 5( 分別為 A B C D E) 個資料, 刪除 3 個資料, 最後 front rear 分別為若干? 5-23

24 二進階題 1. 若以陣列來實作佇列, 如何判斷佇列滿溢及佇列空了? 2. 若以陣列來實作環狀佇列, 如何判斷佇列滿溢及佇列空了? 新增資料刪除資料之位置為何? 3. 試說明將 1,2,3,4 四個數字依此一次序分別經由堆疊 (stack) 與佇例 (queue) 做排列, 問各有多少種不同的排列方式? 請也分別寫出這些排列的結果 4. 如果 MAX_ITEM=10, 請畫出環狀佇列變化的情形, 每個變化都必須標出 front 和 rear 的值 Enqueue(A) Enqueue(B) Enqueue(C) Dequeue( ) Enqueue(D) Dequeue( ) Dequeue( ) Enqueue(E) 5. 利用雙向佇列 (deque) 循序輸入 , 試問是否能夠得到的輸出排列? 並說明其過程或理由 5-24

4-2 1. 使用一般佇列存放資料時, 當前端 (Front) 尚有空位時, 再加入元素, 卻發現此佇列已滿, 請問此時使用下列那一個方法較佳? (A) 優先佇列 (B) 環形佇列 (C) 雙向佇列

4-2 1. 使用一般佇列存放資料時, 當前端 (Front) 尚有空位時, 再加入元素, 卻發現此佇列已滿, 請問此時使用下列那一個方法較佳? (A) 優先佇列 (B) 環形佇列 (C) 雙向佇列 CHAPTER 4 隨書光碟 4-1 4-3 環形佇列由於佇列有一個問題, 就是前端 (Front) 尚有空位時, 再加入元素, 卻發現此佇列已滿此時的解決方法就是使用環形佇列 (Circular Queue) 定義是指一種環形結構的佇列作法將一維陣列的第 0 個