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

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

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

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

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

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

14 /* 程式範例: Ch6-2-1.c */ #include <stdio.h> #include <stdlib.h> #include "Ch6-2-1.h" /* 函數: 檢查佇列是否是空的 */ int isQueueEmpty() { if ( front == rear ) return 1; else return 0; } /* 函數: 將資料存入佇列 */ int enqueue(int d) { if ( rear >= MAXQUEUE -1) { /* 是否超過佇列容量 */ printf("佇列內容全滿\n"); return 0; else { queue[++rear] = d; /* 存入佇列 */ return 1; /* 函數: 從佇列取出資料 */ int dequeue() { if ( isQueueEmpty() ) /* 佇列是否是空的 */ return -1; else return queue[++front]; /* 取出資料 */

15 /* 主程式 */ int main() { /* 宣告變數 */ int data[6] = {1, 2, 3, 4, 5, 6}; int i; printf("存入佇列資料的順序: "); /* 使用迴圈將資料存入佇列 */ for ( i = 0; i < 6; i++) { enqueue(data[i]); printf("[%d]", data[i]); } printf("\n取出佇列資料的順序: "); while ( !isQueueEmpty() ) /* 取出佇列資料 */ printf("[%d]", dequeue()); printf("\n"); system("PAUSE"); return 0;

16 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();

17 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;

18 6-2-2 使用鏈結串列建立佇列-存入元素(圖例)
例如：依序存入值1~3到佇列，可以看到rear指標一直都是指向串列的最後1個節點，如下圖所示：

19 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);

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

21 /* 程式範例: Ch6-2-2.c */ #include <stdio.h> #include <stdlib.h> #include "Ch6-2-2.h" /* 函數: 檢查佇列是否是空的 */ int isQueueEmpty() { if ( front == rear ) return 1; else return 0; } void enqueue(int d) {/* 函數: 將資料存入佇列 */ LQueue new_node; /* 新節點指標 */ /* 配置節點記憶體 */ new_node = (LQueue)malloc(sizeof(QNode)); new_node->data = d; /* 建立節點內容 */ new_node->next = NULL; if(rear==NULL) front = new_node; else { rear->next = new_node; } /* 新節點指向原開始 */ rear = new_node; /* 新節點成為佇列開始 */ /* 函數: 從佇列取出資料 */ int dequeue() { LQueue ptr; /* 指向佇列頂端 */ int temp; if ( front == Null && rear==Null ) rear = NULL; if ( !isQueueEmpty() ) { /* 佇列是否是空的 */ ptr = front; /* 指向佇列頂端 */ front = front->next; /* 佇列指標指向下節點 */ temp = ptr->data; /* 取出資料 */ free(ptr); /* 釋回節點記憶體 */ return temp; /* 佇列取出 */ } else return -1;

22 /* 主程式 */ int main() { int input[100], output[100]; /* 儲存輸入和取出元素 */ int select = 1; /* 選項 */ int numOfInput = 0; /* 陣列的元素數 */ int numOfOutput = 0; int i , temp; printf("鏈結串列的佇列處理......\n"); while ( select != 3 ) { /* 主迴圈 */ printf("[1]存入 [2]取出 [3]顯示全部內容 ==> "); scanf("%d", &select); /* 取得選項 */ switch ( select ) { case 1: /* 將輸入值存入佇列*/ printf("請輸入存入值(%d) ==> ", numOfInput); scanf("%d", &temp); /* 取得存入值 */ enqueue(temp); input[numOfInput++] = temp; break; case 2: /* 取出佇列的內容 */ if ( !isQueueEmpty() ) { temp = dequeue(); printf("取出佇列元素: %d\n", temp); output[numOfOutput++] = temp; }

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

24 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();

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

26 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;

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

28 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;

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

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

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

32 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;

33

34 /* 程式範例: Ch6-2-1.c */ #include <stdio.h> #include <stdlib.h> #include “Ch6-3.h” /* 函數: 檢查佇列是否是空的 */ int isQueueEmpty() { if ( front == rear ) return 1; else return 0; } int isQueueFull(){ int pos; pos = (rear+1) % MAXQUEUE; if ( front == pos ) return 1; /* 函數: 將資料存入佇列 */ int enqueue(int d) { rear++; if ( rear == MAXQUEUE ) { rear = 0; queue[rear] = d; else { return 1; /* 函數: 從佇列取出資料 */ int dequeue() { front++; if ( front == MAXQUEUE ) { front = 0; return queue[front]; } else /* 主程式 */ int main() { /* 宣告變數 */ int data[6] = {1, 2, 3, 4, 5, 6}; int i; printf("存入佇列資料的順序: "); /* 使用迴圈將資料存入佇列 */ for ( i = 0; i < 6; i++) { enqueue(data[i]); printf("[%d]", data[i]); printf("\n取出佇列資料的順序: "); while ( !isQueueEmpty() ) /* 取出佇列資料 */ printf("[%d]", dequeue()); printf("\n"); system("PAUSE"); return 0;

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

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

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

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

39 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();

40 #include <stdio.h>
#include <stdlib.h> #include "ex9.h" /* 函數: 檢查佇列是否是空的*/ int isDequeEmpty() { if ( front == NULL ) return 1; else return 0; } /* 函數: 將資料存入佇列*/ void endeque(int d) { LDeque new_node; /* 配置節點記憶體*/ new_node = (LDeque)malloc(sizeof(QNode)); new_node->data = d; /* 存入佇列節點*/ new_node->next = NULL; /* 設定初值*/ if ( rear == NULL ) /* 是否是第一次存入*/ front = new_node; /* front指向new_node */ else rear->next = new_node;/* 插入rear之後*/ rear = new_node; /* rear指向new_node */ int dedeque_front() { LDeque ptr; int temp; if ( !isDequeEmpty() ) { /* 佇列是否是空的*/ if ( front == rear ) /* 如果是最後一個節點*/ rear = NULL; ptr = front; /* ptr指向front */ front = front->next; /* 刪除第個節點*/ temp = ptr->data; /* 取得資料*/ free(ptr); /* 釋回記憶體*/ return temp; /* 傳回取出的資料*/ } else return -1; /* 佇列是空的*/

41 if ( !isDequeEmpty() ) { /* 佇列是否是空的*/
int dedeque_rear() { LDeque ptr; int temp; if ( !isDequeEmpty() ) { /* 佇列是否是空的*/ if ( front == rear ) { /* 如果是最後一個節點*/ rear = NULL; ptr = front; front = NULL; temp = ptr->data; free(ptr); return temp; } else { ptr = rear; rear = front; /* ptr指向front */ while ( rear->next != ptr ) /* 找到rear的前一個節點*/ rear = rear->next; rear->next = NULL; /* 刪除最後一個節點*/ temp = ptr->data; /* 取得資料*/ free(ptr); /* 釋回記憶體*/ return temp; /* 傳回取出的資料*/ else return -1; /* 佇列是空的*/ int main() { int input[6] = { 1, 2, 3, 4, 5, 6 }; /* 輸入元素*/ int output[6]; /* 取出元素*/ int select; /* 選擇項*/ int i, temp, pos = 0; for ( i = 0; i < 6; i++ ) /* 將陣列元素存入佇列*/ endeque(input[i]); printf("輸入限制性雙佇列的處理......\n"); while ( !isDequeEmpty() ) { /* 主迴圈*/ printf("[1]從後取出[2]從前取出==> "); scanf("%d", &select); /* 取得選項*/ switch ( select ) { case 1: /* 從尾端取出佇列內容*/ temp = dedeque_rear(); output[pos++] = temp; break; case 2: /* 從前端取出佇列內容*/ temp = dedeque_front(); } printf("存入佇列的順序: "); /* 顯示輸入陣列內容*/ for ( i = 0; i < 6; i++ ) printf("[%d]", input[i]); printf("\n佇列取出的順序: "); /* 顯示取出陣列內容*/ printf("[%d]", output[i]); printf("\n"); system("PAUSE"); return 0;

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

43 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();

44 #include <stdio.h>
#include <stdlib.h> #include "ex10.h" /* 函數: 檢查佇列是否是空的*/ int isDequeEmpty() { if ( front == rear ) return 1; else return 0; } /* 函數: 檢查佇列是否已滿*/ int isDequeFull() { int pos; pos = (rear+1) % MAXQUEUE; if ( front == pos ) return 1; else return 0; /* 函數: 將資料存入佇列*/ int endeque_rear(int d) { if ( isDequeFull() ) /* 檢查是否已滿*/ return 0; /* 已滿, 無法存入*/ else { rear = (rear+1) % MAXQUEUE;/* 是否超過,重新定位*/ deque[rear] = d; return 1; /* 函數: 將資料存入佇列*/ int endeque_front(int d) { if ( isDequeFull() ) /* 檢查是否已滿*/ return 0; /* 已滿, 無法存入*/ else { deque[front] = d; front = front - 1; if (front == 0) front = MAXQUEUE-1;/* 是否超過,重新定位*/ } return 1; /* 函數: 從佇列取出資料*/ int dedeque() { if ( isDequeEmpty() ) /* 檢查佇列是否是空*/ return -1; /* 無法取出*/ front = (front+1) % MAXQUEUE; /* 是否超過,重新定位*/ return deque[front]; /* 傳回佇列取出元素*/

45 int main() { int input[6] = { 1, 2, 3, 4, 5, 6 }; /* 輸入元素*/ int i, select; /* 選擇項*/ for ( i = 0; i < 6; i++ ) { /* 存入佇列*/ printf("[1]從後存入[2]從前存入==> "); scanf("%d", &select); /* 讀入選項*/ switch ( select ) { case 1: /* 從尾端存入佇列內容*/ endeque_rear(input[i]); break; case 2: /* 從前端存入佇列內容*/ endeque_front(input[i]); } printf("存入的元素順序: "); /* 顯示輸入陣列內容*/ for ( i = 0; i < 6; i++ ) printf("[%d]", input[i]); printf("\n佇列取出的順序: "); while ( !isDequeEmpty() ) /* 取出剩下的佇列元素*/ printf("[%d]", dedeque()); printf("\n"); system("PAUSE"); return 0;