Microsoft PowerPoint - queue.ppt

資料結構的佇列 (Queues) 資訊科技系林偉川 佇列的基礎 佇列 (Queues) 是一種和堆疊十分相似的資料結構, 在日常生活中隨處可見的排隊人潮, 例如 : 在郵局排隊寄信 銀行排隊存錢或電影院前排隊買票的隊伍, 其組成的線性串列就是一種佇列, 如下圖所示 : 2 1

佇列 (Queue) 佇列的定義 佇列的動作 FIFO (First In First Out) Front Rear 3 佇列的基礎 排隊的隊伍是在尾端 (Rear) 加入隊伍, 如同佇列在尾端存入資料, 當前端 (Front) 寄完信 存完錢或買完票後, 人就離開隊伍, 如同佇列從前端取出資料, 所以佇列的基本操作, 如下所示 : dequeue(): 從佇列取出資料, 每執行一次, 就從前端取出一個資料 enqueue(): 在尾端將資料存入佇列 isqueueempty(): 檢查佇列是否是空的, 以便判斷是否還有資料可以取出 isqueuefull(): 檢查佇列是否是滿了, 以便判斷 是否還可以存入資料 4 2

佇列的基礎 - 特性 佇列的資料因為是從尾端一一存入, 佇列的內容是依序執行 enqueue(1) enqueue(2) enqueue(3) enqueue(4) 和 enqueue(5) 的結果, 接著從佇列依序執行 dequeue() 取出佇列資料, 如下所示 : dequeue():1 dequeue():2 dequeue():3 dequeue():4 dequeue():5 上述取出的順序是 1 2 3 4 5, 和存入時完全相同, 稱為 先進先出 (First In, First Out) 特性 總之, 佇列擁有的特性, 如下 : 從佇列的尾端存入資料, 從前端讀取資料 資料存取的順序是先進先出, 也就是先存入佇列的資料, 先行取出 5 佇列的應用 以計算機科學來說, 佇列的主要用途是作為資料緩衝區, 例如 : 因為電腦周邊設備的處理速度遠不如 CPU, 所以印表機列印報表時, 需要使用佇列作為資料暫存的緩衝區, 如下圖所示 : 6 3

佇列的應用 Buffer: 寫入磁碟的資料先儲存在電腦的記憶體緩衝區中, 待緩衝區的資料到達一定的數量後, 再寫入磁碟中, 因為電腦的記憶體的速度比磁碟機快, 如此連續寫入資料比分段寫入資料更能節省時間 7 Communication: 數據機再傳輸時就是採取佇列的方式, 先到的資料先傳送, 來不及傳送的資料就先暫存在 Queue 中, 等到線路空出來時再繼續傳送. Printer Queue: 印表機連續列印不同資料時, 先到的先列印, 未列印的資料依序排在 Queue 中等待列印. 8 4

使用陣列建立佇列 #define MAXQUEUE 10 /* 佇列的最大容量 */ int queue[maxqueue]; /* 佇列的陣列宣告 */ int front = -1; /* 佇列的前端 */ int rear = -1; /* 佇列的尾端 */ extern int isqueueempty(); extern int enqueue(int d); extern int dequeue(); 9 使用陣列建立佇列 - 存入元素 函數 enqueue() 是將資料存入佇列的 rear 尾端, 其步驟如下所示 : Step 1: 將尾端指標 rear 往前移動, 也就是將指標 rear 加 1 Step 2: 將值存入尾端指標 rear 所指的陣列元素 queue[++rear] = d; 10 5

使用陣列建立佇列 - 存入元素 11 使用陣列建立佇列 - 取出元素 函數 dequeue() 是從佇列的 front 前端取出資料, 其步驟如下所示 : Step 1: 檢查佇列是否已空, 如果沒有 : Step 2: 將前端指標 front 往前移, 即把其值加 1 Step 3: 取出前端指標 front 所指的陣列元素 return queue[++front]; 12 6

使用陣列建立佇列 - 取出元素 13 使用陣列建立佇列 - 佇列是否已空 在取出資料 5 後, 指標 front(4) 與佇列 rear 指標 (5) 相差 1, 表示目前尚有 1 個元素,front 指標是指向目前佇列中第 1 個元素的前一個元素 換句話說, 只需比較兩個 front 和 rear 指標是否相等, 就可以知道佇列是否已空 如果 front 指標是指向佇列中的第 1 個元素, 當取出資料 6 後,front 指標就已經和指標 rear 相同, 都是索引值 5 14 7

使用陣列建立佇列 - 問題 陣列實作的佇列有一個大問題, 因為 front 和 rear 變數的指標都是往同一個方向遞增, 如果 rear 指標到達一維陣列的邊界 MAXQUEUE-1, 就算佇列尚有一些空間, 也需要位移佇列元素, 才有空間存入其它佇列元素, 如下圖所示 : 15 使用鏈結串列建立佇列 struct Node { /* 佇列結構的宣告 */ int data; /* 資料 */ struct Node *next; /* 結構指標 */ }; typedef struct Node QNode; /* 佇列節點的新型態 */ typedef QNode *LQueue; /* 串列佇列的新型態 */ LQueue front = NULL; /* 佇列的前端 */ LQueue rear = NULL; /* 佇列的尾端 */ extern int isqueueempty(); extern void enqueue(int d); extern int dequeue(); 16 8

使用鏈結串列建立佇列 - 存入元素 函數 enqueue() 將資料存入佇列, 插入成為串列的最後 1 個節點, 其步驟如下所示 : Step 1: 建立一個新節點存入佇列資料 new_node = (LQueue)malloc(sizeof(QNode)); new_node->data = d; new_node->next = NULL; Step 2: 檢查 rear 指標是否是 NULL, 如果是, 表示第一次存入資料, 則 : (1) 如果是, 將開頭指標 front 指向新節點 front = new_node; (2) 如果不是, 將 rear 指標所指節點的 next 指標指向新節點 rear->next = new_node; Step 3: 將後 rear 指標指向新節點 rear = new_node; 17 使用鏈結串列建立佇列 - 存入元素 依序存入值 1~3 到佇列, 可以看到 rear 指標一直都是指向串列的最後 1 個節點, 如下圖所示 : 18 9

使用鏈結串列建立佇列 - 取出元素 函數 dequeue() 是從佇列取出資料, 也就是刪除串列第 1 個節點, 其步驟如下所示 : Step 1: 若 front 等於 rear 指標, 表示只剩一個節點, 將 rear 設為 NULL if ( front == rear ) rear = NULL; Step 2: 將佇列的前端指標 front 指向下一個節點 ptr = front; front = front->next; Step 3: 取出第 1 個節點內容 temp = ptr->data; Step 4: 釋回第 1 個節點的節點記憶體 free(ptr); 19 使用鏈結串列建立佇列 - 取出元素 例如 : 在依序存入值 1~3 到佇列後, 呼叫二次 dequeue() 函數取出佇列值, 如下圖所示 : 20 10

環型佇列 解決一般佇列問題的方法 : 環型佇列 將一般佇列 ( 陣列 ) 邏輯上的頭尾相接, 實體上仍然是一個一維陣列. 21 環型佇列的動作 一維陣列共 N 個元素, 製作 Q(0:n-1) 的環型陣列. Q(n-1) 下一個元素是 0. Front N-1 0 Rear 1 N-2 2 3 4 22 11

環狀佇列 環狀佇列 (Circular Queue) 也是使用一維陣列實作的有限元素數佇列, 其差異只在使用特殊技巧來處理陣列索引值, 將陣列視為一個環狀結構, 佇列的索引指標周而復始的在陣列中環狀的移動, 如下圖所示 : 23 環狀佇列 #define MAXQUEUE 4 /* 佇列的最大容量 */ int queue[maxqueue]; /* 佇列的陣列宣告 */ int front = -1; /* 佇列的前端 */ int rear = -1; /* 佇列的尾端 */ extern int isqueueempty(); extern int isqueuefull(); extern int enqueue(int d); extern int dequeue(); 24 12

環型佇列操作範例 ( 一 ) 1.ADD(Q,A) 11 9 10 Front 0 Rear 1 A 2 2. ADD(Q,B) 11 9 10 Front 0 1 A B 2 Rear 8 3 8 3 7 6 3. Delete(Q) 11 10 9 5 0 4 7 6 Front 4. ADD(Q,C) 11 1 10 Rear B 2 9 5 0 4 Front 1 B 2 8 3 8 C 3 Rear 7 6 5 4 7 6 5 4 25 Condition 1. Rear 已到最後 環型佇列操作範例 ( 二 ) Rear Rear 11 0 ADD(Q,V) 11 0 10 1 T U 10 T U V 9 X 2 9 X R R 8 3 8 Front 7 4 Front 7 4 6 5 6 Condition 2. 5 Front front 已到最後 11 0 Delete(Q) 11 0 Front 10 V 1 10 1 W W 9 X 2 9 X 2 8 Y 3 8 Y 3 1 2 3 N=12 0 N=12 0 7 6 5 4 Rear 7 6 5 4 Rear 26 13

環型佇列的計算 Enqueue() Rear=(Rear+1) mod n If Rear = ((Front+1) mod n) then Queue_Full Dequeue() If Front=Rear then Queue_Empty Front=(Front+1) mod n 27 環狀佇列 - 存入元素 1 函數 enqueue() 是在 rear 尾端將資料存入佇列, 因為是環狀結構的陣列, 所以當 rear 到達陣列邊界時, 需要特別處理, 如下圖所示 : 28 14

環狀佇列 - 存入元素 2 MAXQUEUE 為 4 的環狀佇列, 當 rear = 3 時到達陣列邊界, 此時再新增佇列元素 5,rear++ 等於 4, 超過陣列尺寸, 所以需要將它歸 0, 如下所示 : rear++; if ( rear == MAXQUEUE ) rear = 0;?: 條件運算子, 如下所示 : rear = ( rear+1 == MAXQUEUE )? 0 : rear+1; 也可使用餘數運算, 如下所示 : rear = (rear+1) % MAXQUEUE; 29 環狀佇列 - 取出元素 1 函數 dequeue() 是在 front 前端從佇列取出資料, 因為是環狀結構的陣列, 所以當 front 到達陣列邊界時, 需要特別處理, 如下圖所示 : 30 15

環狀佇列 - 取出元素 2 MAXQUEUE 為 4 的環狀佇列, 當 front = 3 時到達陣列邊界, 此時再從佇列取出元素 3, front++ 等於 4, 超過陣列尺寸, 所以需要將它歸 0, 如下所示 : front++; if ( front == MAXQUEUE ) front = 0;?: 條件運算子, 如下所示 : front = ( front+1 == MAXQUEUE )? 0 : front+1; 也可使用餘數運算, 如下所示 : front = (front+1) % MAXQUEUE; 31 環狀佇列 - 佇列是否是空的 1 函數 isqueueempty() 可以判斷環狀佇列是否已經空了 現在環狀佇列尚餘 1 個元素, 如下圖所示 : 32 16

環狀佇列 - 佇列是否是空的 2 再執行一次 dequeue() 取出最後 1 個元素 4, 可以發現 front 和 rear 指標相等, 換句話說, 只需判斷兩個指標是否相等, 就可以判斷環狀佇列是否已經空了, 如下所示 : if ( front == rear ) return 1; else return 0; 33 環狀佇列 - 佇列是否己滿 1 函數 isqueuefull() 可以判斷環狀佇列是否已滿 現在環狀佇列尚有 1 個空間沒有存入元素, 如下圖所示 : 34 17

環狀佇列 - 佇列是否己滿 2 再執行 enqueue(6) 新增元素 6, 可以發現 front 和 rear 指標相等, 沒有辦法判斷環狀佇列是已空和全滿, 因為兩個指標都是指向相同索引值 1 所以, 環狀佇列全滿就是指標 rear 和 front 相隔一個空間, 換句話說, 為了分辨環狀佇列是已空和全滿, 其實際的儲存空間是陣列尺寸減 1, 如下所示 :( 犧牲 1 個位置 ) int pos; pos = (rear+1) % MAXQUEUE; if ( front == pos ) return 1; else return 0; 35 雙佇列 雙佇列 (Deques) 是英文名稱 (Double-ends Queues) 的縮寫, 雙佇列的二端如同佇列的前尾端, 都允許存入或取出資料, 如下圖所示 : 36 18

雙佇列 - 種類 雙佇列依其應用分為多種存取方式 常見的雙佇列, 如下所示 : 輸入限制性雙佇列 (Input Restricted Deque) 輸出限制性雙佇列 (Output Restricted Deque) 上述雙佇列是使用在電腦 CPU 的排程, 排程在多人使用的電腦是重要觀念, 因為同時有多人使用同一個 CPU, 而 CPU 在每一段時間內只能執行一個工作, 所以將每個人的工作集中擺在一個等待佇列, 等待 CPU 執行完一個工作後, 再從佇列取出下一個工作來執行, 排定工作誰先誰後的處理稱為 工作排程 37 輸入限制性雙佇列 輸入限制性雙佇列 (Input Restricted Deque) 是限制存入只能在其中一端, 取出可以在兩端的任何一端, 雙佇列只有一端存入, 兩端都可以輸出, 所以佇列輸出的結果擁有多種組合 38 19

輸入限制性雙佇列 #define MAXQUEUE 10 /* 佇列的最大容量 */ int deque[maxqueue]; /* 佇列的陣列宣告 */ int front = -1; /* 佇列的前端 */ int rear = -1; /* 佇列的尾端 */ extern int isdequeempty(); extern int isdequefull(); extern int endeque(int d); extern int dedeque_rear(); extern int dedeque_front(); 39 輸出限制性雙佇列 輸出限制性雙佇列 (Output Restricted Deque) 是限制取出只能在一端, 卻可以從兩端的任何一端存入元素, 如下圖所示 : 40 20

輸出限制性雙佇列 struct Node { /* 佇列結構的宣告 */ int data; /* 資料 */ struct Node *next; /* 結構指標 */ }; typedef struct Node QNode;/* 雙佇列節點的新型態 */ typedef QNode *LDeque; /* 串列雙佇列的新型態 */ LDeque front = NULL; /* 雙佇列的前端 */ LDeque rear = NULL; /* 雙佇列的尾端 */ extern int isdequeempty(); extern void endeque_rear(int d); extern void endeque_front(int d); extern int dedeque(); 41 請寫出答案 1. 原佇列 =(a,b,c),enqueue(d); enqueue(e); dequeue(); 請列出佇列中處理資料的過程及最後佇列內容為何? 2. 原佇列 =(10,20,30) enqueue(dequeue()+40); printf( %d\n,dequeue()); printf( %d\n,dequeue()- dequeue()); enqueue(dequeue()+5); printf( %d\n,dequeue()); 列出佇列中處理資料的過程及最後佇列內容為何? 3. enqueue(3); enqueue(4); printf( %d\n,dequeue()+5); enqueue(5); enqueue(6); enqueue(7); enqueue(8); enqueue(dequque()+dequeue()); printf( %d\n,dequeue()*2); 列出佇列中處理資料的過程即最後佇列內容為何? 42 21

請寫出答案 現有一個環狀佇列提供 enqueue() 和 dequeue() 函數, 請寫出下列主程式 main() 的執行結果, 如下所示 : void main(){ enqueue(5); enqueue(3); enqueue(4); printf("[%d]", dequeue()); enqueue(dequeue()); enqueue(dequeue()+4); while (!isqueueempty() ) printf("[%d]", dequeue()); } 43 請寫出答案 現有一個環狀佇列大小為 0-6, 目前 front=2 rear=5, 佇列內容為 (a,b,c), 請寫出下列 front rear 的值, 並寫出其執行結果 1. dequeue(),front=? rear=? 取出值 =? 2. enqueue(d),front=? rear=? 3. enqueue(e),front=? rear=? 4. dequeue(),front=? rear=? 取出值 =? 44 22

請寫出答案 現有一個環狀佇列大小為 0-7, 目前 front=3 rear=6, 佇列內容為 (e,f,g), 請寫出下列 front rear 的值, 並寫出其執行結果 1. enqueue(a),front=? rear=? 2. enqueue(d),front=? rear=? 3. dequeue(),front=? rear=? 取出值 =? 4. enqueue(b),front=? rear=? 5. dequeue(),front=? rear=? 取出值 =? 6. enqueue(c),front=? rear=? 7. enqueue(h),front=? rear=? 8. dequeue(),front=? rear=? 取出值 =? 9. dequeue(),front=? rear=? 取出值 =? 10. dequeue(),front=? rear=? 取出值 =? 45 請寫出答案 現有一個環狀佇列大小為 0-5,, 請寫出下列 front rear 的值, 並畫出佇列內容 : void main(){ enqueue(10); enqueue(20); enqueue(30); enqueue(dequeue()+40); printf("[%d]", dequeue()); printf("[%d]", dequeue()-dequeue()); } 46 23