資料結構 第5章 佇列
5-1 認識佇列 佇列 (queue) 是一個線性串列，兩端分別稱為前端 (front) 與後端 (rear)，當要新增資料時，必須放入佇列的後端，當要刪除資料時，必須從佇列的前端開始。
5-2 佇列的實作 5-2-1 使用陣列實作佇列 #define MAX_SIZE 6 typedef struct que{ 5-2 佇列的實作 5-2-1 使用陣列實作佇列 #define MAX_SIZE 6 typedef struct que{ char data[MAX_SIZE]; int front; int rear; }queue; queue Q; Q.front = -1; Q.rear = -1;
佇列應該要提供下列運算： 判斷佇列已滿 (isFull) 判斷佇列已空 (isEmpty) enqueue或新增 (add) enqueue(queue *Q, char value) { if (Q->rear == (MAX_SIZE - 1)) printf("佇列已滿！"); else Q->data[++Q->rear] = value; } dequeue或刪除 (delete) dequeue(queue *Q) if (Q->front == Q->rear) printf("佇列已空！"); */ else printf("%c ", Q->data[++Q->front]);
假設佇列的最大長度為6，依序新增A、B、C、D等四個資料，然後刪除兩個資料，再新增E、F、G等三個資料，則變數front、rear的值與佇列的內容如下：
enqueue() 函數必須改寫成如下，以適用於環狀佇列： queue Q; Q.front = 0; Q.rear = 0; enqueue(queue *Q, char value) { if ((Q->rear + 1) % MAX_SIZE == Q->front) printf("佇列已滿！"); else{ Q->rear = (Q->rear + 1) % MAX_SIZE; Q->data[Q->rear] = value; }
dequeue() 函數必須改寫成如下，以適用於環狀佇列 ： dequeue(queue *Q) { if (Q->front == Q->rear) printf("佇列已空！"); else{ Q->front = (Q->front + 1) % MAX_SIZE; printf("%c ", Q->data[Q->front]); }
前面的例子改成環狀佇列後，佇列的內容如下：
5-2-2 使用鏈結串列實作佇列 typedef struct node{ int data; struct node *next; 5-2-2 使用鏈結串列實作佇列 typedef struct node{ int data; struct node *next; }list_node; typedef list_node *list_pointer; list_pointer front, rear;
若要新增資料，必須將資料放入佇列的後端，如下圖所示：
若要刪除資料，必須從佇列的前端開始，如下圖所示：
範例5.1：[enqueue] 根據本節宣告的單向鏈結串列，撰寫一個函數實作佇列的新增資料運算。 enqueue(int value) { list_pointer ptr; ptr = (list_pointer)malloc(sizeof(list_node)); ptr->data = value; ptr->next = NULL; if (rear == NULL) front = ptr; else rear->next = ptr; rear = ptr; }
範例5.2：[dequeue] 根據本節宣告的單向鏈結串列，撰寫一個函數實作佇列的刪除資料運算。 { list_pointer ptr; if (front == NULL) printf("佇列已空！"); else{ printf("%d ", front->data); ptr = front; front = front->next; free(ptr); }
5-3 雙向佇列 #define MAX_SIZE 100 typedef struct deq{ char data[MAX_SIZE]; 5-3 雙向佇列 #define MAX_SIZE 100 typedef struct deq{ char data[MAX_SIZE]; int frontL; int rearL; int frontR; int rearR; }deque; queue Q; Q.frontL = -1; Q.rearL = -1; Q.frontR = MAX_SIZE; Q.rearR = MAX_SIZE;
雙向佇列應該要提供下列運算： 判斷雙向佇列已滿 (isFull) 判斷雙向佇列已空 (isEmpty) enqueueL enqueueR dequeueL dequeueR
在雙向佇列內新增資料或刪除資料：