資料結構 第5章　佇列.

Presentation on theme: "資料結構 第5章　佇列."— Presentation transcript:

1 資料結構 第5章　佇列

2 5-1　認識佇列 佇列 (queue) 是一個線性串列，兩端分別稱為前端 (front) 與後端 (rear)，當要新增資料時，必須放入佇列的後端，當要刪除資料時，必須從佇列的前端開始。

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

4 佇列應該要提供下列運算： 判斷佇列已滿 (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]);

5 假設佇列的最大長度為6，依序新增A、B、C、D等四個資料，然後刪除兩個資料，再新增E、F、G等三個資料，則變數front、rear的值與佇列的內容如下：

6

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

8 dequeue() 函數必須改寫成如下，以適用於環狀佇列 ：
dequeue(queue *Q) { if (Q->front == Q->rear) printf("佇列已空！"); else{ Q->front = (Q->front + 1) % MAX_SIZE; printf("%c ", Q->data[Q->front]); }

9 前面的例子改成環狀佇列後，佇列的內容如下：

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

11 若要新增資料，必須將資料放入佇列的後端，如下圖所示：

12 若要刪除資料，必須從佇列的前端開始，如下圖所示：

13 範例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; }

14 範例5.2：[dequeue] 根據本節宣告的單向鏈結串列，撰寫一個函數實作佇列的刪除資料運算。
{ list_pointer ptr; if (front == NULL) printf("佇列已空！"); else{ printf("%d ", front->data); ptr = front; front = front->next; free(ptr); }

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

16 雙向佇列應該要提供下列運算： 判斷雙向佇列已滿 (isFull) 判斷雙向佇列已空 (isEmpty) enqueueL enqueueR
dequeueL dequeueR

17 在雙向佇列內新增資料或刪除資料：