Microsoft PowerPoint - queue.ppt

Size: px

Start display at page:

Download "Microsoft PowerPoint - queue.ppt"

郊寿
6 years ago
Views:

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

2 佇列 (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

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

4 佇列的應用 Buffer: 寫入磁碟的資料先儲存在電腦的記憶體緩衝區中, 待緩衝區的資料到達一定的數量後, 再寫入磁碟中, 因為電腦的記憶體的速度比磁碟機快, 如此連續寫入資料比分段寫入資料更能節省時間 7 Communication: 數據機再傳輸時就是採取佇列的方式, 先到的資料先傳送, 來不及傳送的資料就先暫存在 Queue 中, 等到線路空出來時再繼續傳送. Printer Queue: 印表機連續列印不同資料時, 先到的先列印, 未列印的資料依序排在 Queue 中等待列印. 8 4

5 使用陣列建立佇列 #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

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

7 使用陣列建立佇列 - 取出元素 13 使用陣列建立佇列 - 佇列是否已空在取出資料 5 後, 指標 front(4) 與佇列 rear 指標 (5) 相差 1, 表示目前尚有 1 個元素,front 指標是指向目前佇列中第 1 個元素的前一個元素換句話說, 只需比較兩個 front 和 rear 指標是否相等, 就可以知道佇列是否已空如果 front 指標是指向佇列中的第 1 個元素, 當取出資料 6 後,front 指標就已經和指標 rear 相同, 都是索引值

8 使用陣列建立佇列 - 問題陣列實作的佇列有一個大問題, 因為 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

9 使用鏈結串列建立佇列 - 存入元素函數 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

10 使用鏈結串列建立佇列 - 取出元素函數 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

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

12 環狀佇列環狀佇列 (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

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

14 環型佇列的計算 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

15 環狀佇列 - 存入元素 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

16 環狀佇列 - 取出元素 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

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

18 環狀佇列 - 佇列是否己滿 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

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

20 輸入限制性雙佇列 #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

21 輸出限制性雙佇列 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

22 請寫出答案現有一個環狀佇列提供 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

23 請寫出答案現有一個環狀佇列大小為 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

Microsoft PowerPoint - Fig03_Stack.ppt [相容模式]

Microsoft PowerPoint - Fig03_Stack.ppt [相容模式] 四堆疊與佇列 (Stack & Queue) 4-. 串列及鏈結串列 4-. 用陣列結構實作堆疊 4-3. 用鏈結串列實作堆疊 4-4. 堆疊的應用 4-5. 佇列 4-6. 用陣列結構實作佇列 4-7 7. 用鏈結串列實作佇列堆疊的基本觀念. 定義 : 4- 堆疊當將東西疊成一堆, 而取用的時候由上方來取出. 特性 : 先進後出, 後進先出 ( 號球先放, 但 3 號球會先拿出 ) 3 3