第6章 佇列（Queues） 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列.

Presentation on theme: "第6章 佇列（Queues） 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列."— Presentation transcript:

1 第6章 佇列（Queues） 6-1 佇列的基礎 6-2 佇列的表示法 6-3 環狀佇列 6-4 雙佇列

2 6-1 佇列的基礎-說明 「佇列」（Queues）是一種和堆疊十分相似的資料結構，在日常生活中隨處可見的排隊人潮，例如：在郵局排隊寄信、銀行排隊存錢或電影院前排隊買票的隊伍，其組成的線性串列就是一種佇列，如下圖所示：

3 6-1 佇列的基礎-操作 排隊的隊伍是在尾端（Rear）加入隊伍，如同佇列在尾端存入資料，當前端（Front）寄完信、存完錢或買完票後，人就離開隊伍，如同佇列從前端取出資料，所以佇列的基本操作，如下所示： dequeue()：從佇列取出資料，每執行一次，就從前端取出一個資料。 enqueue()：在尾端將資料存入佇列。 isQueueEmpty()：檢查佇列是否是空的，以便判斷是否還有資料可以取出。

4 6-1 佇列的基礎-特性 佇列的資料因為是從尾端一一存入，佇列的內容是依序執行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）特性。總之，佇列擁有的特性，如下： 從佇列的尾端存入資料，從前端讀取資料。 資料存取的順序是先進先出（First In, First Out），也就是先存入佇列的資料，先行取出。

5 6-1 佇列的基礎-應用 以計算機科學來說，佇列的主要用途是作為資料緩衝區，例如：因為電腦周邊設備的處理速度遠不如CPU，所以印表機列印報表時，需要使用佇列作為資料暫存的緩衝區，如下圖所示：

6 6-2 佇列的表示法 6-2-1 使用陣列建立佇列 6-2-2 使用鏈結串列建立佇列

7 6-2-1 使用陣列建立佇列-標頭檔 01: /* 程式範例: Ch6-2-1.h */
02: #define MAXQUEUE /* 佇列的最大容量 */ 03: int queue[MAXQUEUE]; /* 佇列的陣列宣告 */ 04: int front = -1; /* 佇列的前端 */ 05: int rear = -1; /* 佇列的尾端 */ 06: /* 抽象資料型態的操作函數宣告 */ 07: extern int isQueueEmpty(); 08: extern int enqueue(int d); 09: extern int dequeue();

8 6-2-1 使用陣列建立佇列 佇列是分別從兩端存入和取出資料。
以陣列建立佇列，指標front(前端)及rear(後端)變數是用來儲存陣列的索引值。 front(前端) 變數的索引值是指向目前佇列中第1個元素的前一個索引值。rear(後端)變數是指向剛存入元素的索引值(最後ㄧ個)

9 6-2-1 使用陣列建立佇列-存入元素(步驟) 函數enqueue()是將資料存入佇列的rear尾端，其步驟如下所示：
Step 1： 檢查佇列是否已滿，如果沒有： Step 2：將尾端指標rear往前移動，也就是將指標rear加1。 Step 3：將值存入尾端指標rear所指的陣列元素。 queue[++rear] = d;

10 6-2-1 使用陣列建立佇列-存入元素(圖例)

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

12 6-2-1 使用陣列建立佇列-取出元素(圖例)

13 6-2-1 使用陣列建立佇列-佇列是否已空 在取出資料5後，指標front是指向佇列指標rear的前1個陣列索引值4，目前尚有1個元素，請注意！front指標是指向目前佇列中第1個元素的前一個元素。 換句話說，只需比較兩個front和rear指標是否相等，就可以知道佇列是否已空。 如果front指標是指向佇列中的第1個元素，當取出資料5後，front指標就已經和指標rear相同，都是索引值5，如此就無法判斷佇列到底是空了或還剩下1個元素。

14 6-2-1 使用陣列建立佇列-問題 陣列實作的佇列有一個大問題，因為front和rear變數的指標都是往同一個方向遞增，如果rear指標到達一維陣列的邊界MAXQUEUE-1，需要位移佇列元素才有空間存入其它佇列元素，就算佇列的一維陣列尚有一些空間，如下圖所示：

15 6-2-2 使用鏈結串列建立佇列-標頭檔 01: /* 程式範例: Ch6-2-2.h */
02: struct Node { /* 佇列結構的宣告 */ 03: int data; /* 資料 */ 04: struct Node *next; /* 結構指標 */ 05: }; 06: typedef struct Node QNode; /* 佇列節點的新型態 */ 07: typedef QNode *LQueue; /* 串列佇列的新型態 */ 08: LQueue front = NULL; /* 佇列的前端 */ 09: LQueue rear = NULL; /* 佇列的尾端 */ 10: /* 抽象資料型態的操作函數宣告 */ 11: extern int isQueueEmpty(); 12: extern void enqueue(int d); 13: extern int dequeue();

16 6-2-2 使用鏈結串列建立佇列-存入元素(步驟)
函數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 6-2-2 使用鏈結串列建立佇列-存入元素(圖例)
例如：依序存入值1~3到佇列，可以看到rear指標一直都是指向串列的最後1個節點，如下圖所示：

18 6-2-2 使用鏈結串列建立佇列-取出元素(步驟)
函數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 6-2-2 使用鏈結串列建立佇列-取出元素(圖例)
例如：在依序存入值1~3到佇列後，呼叫二次dequeue()函數取出佇列值，如下圖所示：

20 6-3 環狀佇列-說明 「環狀佇列」（Circular Queue）也是使用一維陣列實作的有限元素數佇列，其差異只在使用特殊技巧來處理陣列索引值，將陣列視為一個環狀結構，佇列的索引指標周而復始的在陣列中環狀的移動，如下圖所示：

21 6-3 環狀佇列-標頭檔 01: /* 程式範例: Ch6-3.h */
02: #define MAXQUEUE /* 佇列的最大容量 */ 03: int queue[MAXQUEUE]; /* 佇列的陣列宣告 */ 04: int front = -1; /* 佇列的前端 */ 05: int rear = -1; /* 佇列的尾端 */ 06: /* 抽象資料型態的操作函數宣告 */ 07: extern int isQueueEmpty(); 08: extern int isQueueFull(); 09: extern int enqueue(int d); 10: extern int dequeue();

22 6-3 環狀佇列-存入元素1 函數enqueue()是在rear尾端將資料存入佇列，因為是環狀結構的陣列，所以當rear到達陣列邊界時，需要特別處理，如下圖所示：

23 6-3 環狀佇列-存入元素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;

24 6-3 環狀佇列-取出元素1 函數dequeue()是在front前端從佇列取出資料，因為是環狀結構的陣列，所以當front到達陣列邊界時，需要特別處理，如下圖所示：

25 6-3 環狀佇列-取出元素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;

26 6-3 環狀佇列-佇列是否是空的1 函數isQueueEmpty()可以判斷環狀佇列是否已經空了。現在環狀佇列尚餘1個元素，如下圖所示：

27 6-3 環狀佇列-佇列是否是空的2 再執行一次dequeue()取出最後1個元素4，可以發現front和rear指標相等，換句話說，只需判斷兩個指標是否相等，就可以判斷環狀佇列是否已經空了，如下所示： if ( front == rear ) return 1; else return 0;

28 6-3 環狀佇列-佇列是否己滿1 函數isQueueFull()可以判斷環狀佇列是否已滿。現在環狀佇列尚有1個空間沒有存入元素，如下圖所示：

29 6-3 環狀佇列-佇列是否己滿2 再執行enqueue(6)新增元素6，可以發現front和rear指標相等，沒有辦法判斷環狀佇列是已空和全滿，因為兩個指標都是指向相同索引值1。 所以，環狀佇列全滿就是指標rear和front相隔一個空間，換句話說，為了分辨環狀佇列是已空和全滿，其實際的儲存空間是陣列尺寸減1，如下所示： int pos; pos = (rear+1) % MAXQUEUE; if ( front == pos ) return 1; else return 0;

30 6-4 雙佇列 6-4-1 輸入限制性雙佇列 6-4-2 輸出限制性雙佇列

31 6-4 雙佇列-說明 「雙佇列」（Deques）是英文名稱（Double-ends Queues）的縮寫，雙佇列的二端如同佇列的前尾端，都允許存入或取出資料，如下圖所示：

32 6-4 雙佇列-種類 雙佇列依其應用分為多種存取方式。常見的雙佇列，如下所示：
輸入限制性雙佇列（Input Restricted Deque）。 輸出限制性雙佇列（Output Restricted Deque）。 上述雙佇列是使用在電腦CPU的排程，排程在多人使用的電腦是重要觀念，因為同時有多人使用同一個CPU，而CPU在每一段時間內只能執行一個工作，所以將每個人的工作集中擺在一個等待佇列，等待CPU執行完一個工作後，再從佇列取出下一個工作來執行，排定工作誰先誰後的處理稱為「工作排程」（Jobs Scheduling）。

33 6-4-1 輸入限制性雙佇列-說明 輸入限制性雙佇列（Input Restricted Deque）是限制存入只能在其中一端，取出可以在兩端的任何一端，雙佇列只有一端存入，兩端都可以輸出，所以佇列輸出的結果擁有多種組合。

34 6-4-1 輸入限制性雙佇列-標頭檔 01: /* 程式範例: Ch6-4-1.h */
02: #define MAXQUEUE /* 佇列的最大容量 */ 03: int deque[MAXQUEUE]; /* 佇列的陣列宣告 */ 04: int front = -1; /* 佇列的前端 */ 05: int rear = -1; /* 佇列的尾端 */ 06: /* 抽象資料型態的操作函數宣告 */ 07: extern int isDequeEmpty(); 08: extern int isDequeFull(); 09: extern int endeque(int d); 10: extern int dedeque_rear(); 11: extern int dedeque_front();

35 6-4-2 輸出限制性雙佇列-說明 輸出限制性雙佇列（Output Restricted Deque）是限制取出只能在一端，卻可以從兩端的任何一端存入元素，如下圖所示：

36 6-4-2 輸出限制性雙佇列-標頭檔 01: /* 程式範例: Ch6-4-2.h */
02: struct Node { /* 佇列結構的宣告 */ 03: int data; /* 資料 */ 04: struct Node *next; /* 結構指標 */ 05: }; 06: typedef struct Node QNode;/* 雙佇列節點的新型態 */ 07: typedef QNode *LDeque; /* 串列雙佇列的新型態 */ 08: LDeque front = NULL; /* 雙佇列的前端 */ 09: LDeque rear = NULL; /* 雙佇列的尾端 */ 10: /* 抽象資料型態的操作函數宣告 */ 11: extern int isDequeEmpty(); 12: extern void endeque_rear(int d); 13: extern void endeque_front(int d); 14: extern int dedeque();

37 本章結束

38 複習(一) 1.舉例說明何謂「佇列」（Queues）? 2.佇列的特性為何? 3.舉例說明電腦如何使用「佇列」?
4. 資料結構裡First In , First Out 意義為何? 5.為何佇列的front指標不指向佇列中的第1個元素? 6. enqueue()是將資料存入佇列的rear尾端，其步驟為何? 7. dequeue()是從佇列的front前端取出資料，其步驟為何? 8. 何謂「環狀佇列」（Circular Queue）? 9.如何判斷環狀佇列是否已空? 10.為何環狀佇列實際的儲存空間是陣列尺寸減1?

39 複習(二) 11. 鏈結串列建立之佇列enqueue() 步驟為何? 12.鏈結串列建立之佇列dequeue() 步驟為何?
13.何為「雙佇列」（Deques）? 14.電腦如何使用資料結構做「工作排程」? 15.何謂輸入限制性雙佇列（Input Restricted Deque）? 16. 何謂輸出限制性雙佇列（Output Restricted