# 演算法與資料結構 隊列(Queue)與循環對列(Circular Queue)
###### tags: `Algorithm and Data structure`
## 隊列(queue)介紹
隊列就如同堆疊一般，是一種線性表，與堆疊不同的地方在於，堆疊的push和pop操作都是在棧頂(Top)的地方進行操作，而隊列則是插入元素在一端進行，而刪除則是在另外一端執行。
隊列的基本操作為Enqueue(入隊)，他是在表的末端(稱為隊尾(rear))插入元素。另一個操作為Dequeue(出隊)，作用為刪除(或是回傳)表頭(又稱為(front))的元素。
而元素推入Queue，是遵循著==先進先出的原則(First In First Out)==。假設我們依序將2和3進行Enqueue，看起來會像是以下
1. 將2進行Enqueue
2. 將3進行Enqueue(在隊尾(rear)插入元素)
3. 進行Dequeue(刪除頭(front)元素)
4. 進行Dequeue
我們可以觀察到，2為最先進入Queue的元素(Enqueue)，也是最先出隊(Enqueue)的元素，也就是所謂First In First Out的特性。
## 隊列的概念與操作
我們實作隊列無論使用串列還是陣列的方式，對其進行的任何操作皆為$O(1)$，以下為如何使用陣列實作出隊列。
首先，我們需要陣列Queue，以及位置front和rear，他們代表著Queue這個陣列的頭端和末端，除此之外，我們還需要紀錄陣列的大小，也就是陣列中元素的多寡size。所有這一些資訊作為結構(struct)的成員(member)並包裝起來
首先，先針對入隊(Enqueue)進行分析
### 入隊(Enqueue)
其實我們所進行的事情，就只是改變隊尾(rear = rear + 1)，並將元素放入隊尾(Queue[rear] = X)，沒有涉及到需要移動到整個陣列的操作，因此，時間複雜度為$O(1)$。就像是排隊一樣，來的人只要接在原來排隊人群的後面就可以了。
### 出隊(Dequeue)
接著，針對出隊(Dequeue)進行分析，出隊為將頭(front)元素移除的操作，就像是排隊一樣，排頭的人走了，那其餘的人就必須往前進一格，也因此出隊會涉及到整個陣列的移動，時間複雜度為O(N)。
原本排隊情形
排頭的人取得商品後走掉了
後面的人需要跟著往前進一格
以Queue陣列的結構圖演示就如同以下
但出隊需要的時間複雜度為O(N)，有沒有辦法將它簡化到O(1)，其實是有辦法的，只要我們不要限制隊頭(front)一定要在0號的位置，也就是排頭的位置，就可以不用涉及陣列所有元素移動的操作了，如同下圖所示
為了避免當只有一個元素時，隊頭(front)和隊尾(rear)重合的問題，我們使用兩個指標進行處理，front指標指向Queue陣列的隊頭，==rear指向Queue陣列的隊尾元素的下一個位置==，如下圖所示
執行Dequeue
執行Dequeue
執行Dequeue
我們可以發現，當front和rear重合時，就表示Queue為空的
## 空間不足的問題，與假溢出(False overflow)問題
下圖為長度為5的陣列，經過入隊(Enqueue)a1,a2,a3,a4的操作後的情況
然後我們將a1,a2出隊(Dequeue)
在將a5入隊(Enqueue)
我們會發現，當我們執行入隊(Enqueue)時，需要將rear + 1，他會跑到陣列界線以外的地方，造成錯誤，而且我們還發現到，當我們要將元素入隊時，如將a6入隊，Queue明明還有0號和1號的位置，卻無法將元素加入，因為會有rear越界的問題，而這個問題，我們稱之為假溢出問題(False overflow)。
## 解決假溢出問題，使用循環陣列(circular array)
要解決假溢出的問題，其實我們只要將rear跑到陣列界線時，再往下走一格會回到陣列的頭就可以解決了，也就是使陣列的頭尾相接，這種陣列我們稱之為循環陣列(circular array)。
而回到剛剛將a6入隊(Enqueue)的問題，我們使用循環陣列就能夠順利地解決了，原本將a5入隊會發生的狀況使用循環陣列後如下圖所示
然後我們將a6入隊
接著將a7入隊
此時我們又發現新的問題了，前面說過，當front和rear相等時，表示Queue為空的，在單向時行得通，但在循環陣列時就發生問題了，這裡我們的front和rear發生了重合，但是Queue卻不為空，我們要如何解決這個問題?
## 常見判斷Queue是為滿(Full)還是空(NULL)的方法，front和rear的特殊對應關係
下面我們會介紹常見判斷Queue是空還是滿的方法，歸納上面的演示，由於rear有可能大於front，也有可能小於front，當rear和front只相差一個位置時，有可能是Queue滿(Full)的狀況，但也有可能相差了整整一圈。
我們歸納出了一下結論，如果Queue的最大長度為QueueSize，==則Queue為滿(Full)的條件為$(rear + 1) \mod QueueSize == front$==，我們已下舉幾個例子來說明 :
Example 1.
> 如果QueueSize = 5
> 
> 目前的front = 0，raer = 4
> 而我們帶入$(rear + 1) \mod QueueSize == front$
> (4 + 1) % 5 = 0，而front恰好為零，符合$(rear + 1) \mod QueueSize == front$
> 因此判斷此Queue為滿(Full)。P.S:對於Full的Queue，我們保留一個空的格子
Example 2.
> 如果QueueSize = 5
> 
> 目前front = 2，rear = 1
> 而我們帶入$(rear + 1) \mod QueueSize == front$
> (1 + 1) % 5 = 2，而front恰好為2，符合$(rear + 1) \mod QueueSize == front$
> 因此判斷此Queue為滿(Full)。P.S:對於Full的Queue，我們保留一個空的格子
Example 3.
> 如果QueueSize = 5
> 
> 目前front = 2, rear = 0
> 而我們帶入$(rear + 1) \mod QueueSize == front$
> (0 + 1) % 5 = 1，符合$(rear + 1) \mod QueueSize == front$ (1 != 2)
> 因此判斷Queue未滿。
---
### Queue的長度問題(Queue中元素個數)
我們可以將Queue求長度的問題分為兩個部分進行討論
1. 當rear > front時，如下圖
此時Queue長度為rear - front，4 - 2 = 2
2. 當rear < front時，如下圖
長度的問題就必須分段討論，一個為QueueSize - front，也就是5 - 2，另一段為0 + rear，也就是0 + 1，在將兩者相加，得到Queue的長度。
我們綜合了一下上方兩種情況，得到了一個通用==計算Queue長度的公式
$(rear - front + MaxQueueSize)\ \% \ MaxQueueSize$==
### 取得Queue最後一個元素
取得最後一個元素，我們在實作Queue時，會空出一個格子，而rear指標會指向這一個空格，真正有元素的位置是在rear的前一格(請見上圖)，所以我們可能會以為最後一個元素即為Queue\[rear - 1]，但事實上這是錯的，如果遇到rear在0號位置，那rear - 1即會超出Queue的邊界，造成違法存取的錯誤，因此，我們歸納出了一個公式，用來取得Queue的最後一個元素
==Queue最後一個元素: $Q$->$array$ $[rear - 1 + MaxQueueSize]$ $\%$ $MaxQueueSize$==
有了這一些結論後，我們就可以開始實作Queue了
## 單向隊列的實作ADT
下面為使用陣列實作隊列的ADT
```c=
#ifndef _Queue_h
Queue* InitQueue(Queue* Q);
void DestroyQueue(Queue* Q);
void ClearQueue(Queue* Q);
int IsEmpty(Queue* Q);
int GetHead(Queue* Q);
int Gettail(Queue* Q);
void EnQueue(Queue* Q, ElementType X);
void DeQueue(Queue* Q);
int QueueLengh(Queue* Q);
void PrintQueue(Queue* Q);
#endif /* _Queue_h */
/* Place in implementation file */
/* Queue implementation is a dynamically allocated array */
#define MaxQueueSize (number)
typedef struct Queue{
int Front;
int Rear;
ElementType *Array;
}Queue;
```
### IsEmpty實作
```c=
int IsEmpty(Queue Q)
{
return QueueLenght(Q) == 0;
}
```
說明:如果長度為零，表示Queue為空。
### IsFull實作
```c=
int IsFull(Queue Q)
{
return QueueLenght(Q) == MaxQueueSize - 1;
}
```
說明:長度等於MaxQueueSize - 1，原因為Queue狀態為滿時，我們會空出一格。
### InitQueue實作
```c=
Queue* InitQueue()
{
Queue* Q = malloc(sizeof(Q));
Q->array = malloc(sizeof(int) * MaxQueueSize);
Q->front = 0;
Q->rear = 0;
return Q;
}
```
### QueueLengh實作
```c=
int QueueLengh(Queue *Q)
{
return (Q->rear - Q->front + MaxQueueSize) % MaxQueueSize;
}
```
說明:請參照上方說明。
### EnQueue實作
```c=
int EnQueue(Queue *Q, int X)
{
if((Q->rear + 1) % MaxQueueSize == Q->front)
{
return -1;
}
Q->array[Q->rear] = X;
Q->rear = (Q->rear + 1) % MaxQueueSize;
return 0;
}
```
說明:
(Q->rear + 1) % MaxQueueSize == Q->front表示判斷Queue是否為滿，如果發現Queue已滿，則無法再將元素入隊(Enqueue)，回傳錯誤碼-1。
如果Queue不為滿，則將元素入隊(Enqueue)，也就是將元素加在Queue的尾巴(rear)，並改變rear的位置。
### DeQueue實作
```c=
int DeQueue(Queue* Q)
{
int front_value;
if(Q->front == Q->rear)
{
return -1;
}
front_value = Q->array[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
return front;
}
```
說明:
當front和rear相等時，即表示Queue為空(注意: 這是單向Queue，非循環Queue)。
如果Queue不為空，則先將Queue隊頭(front)的元素存入front_value中，並改變front的索引號
之後回傳原先Queue頭元素，也就是front_value。
### printQueue實作
```c=
void printQueue(Queue *Q)
{
for(int i = 0; i < QueueLength(Q); i++)
{
if(i >= 1)
{
printf("%s", "->");
}
printf("%d", Q->array[i]);
}
}
```
### DestroyQueue實作
```c=
void DestroyQueue(Queue* Q)
{
free(Q->array);
free(Q);
}
```
### GetTail實作
```c=
int GetTail(Queue* Q)
{
return Q->value[Q->rear - 1 + MaxQueueSize] % MaxQueueSize;
}
```
### Queue實作範例程式碼
```c=
#include <stdio.h>
#include <stdlib.h>
#define MaxQueueSize 10
typedef struct Queue{
int front;
int rear;
int *array;
}Queue;
Queue* InitQueue(void);
void DestroyQueue(Queue* Q);
void ClearQueue(Queue* Q);
int IsEmpty(Queue* Q);
int IsFull(Queue* Q);
int GetHead(Queue* Q);
int GetTail(Queue* Q);
int EnQueue(Queue* Q, int X);
int DeQueue(Queue* Q);
int QueueLength(Queue* Q);
void printQueue(Queue* Q);
int main(void)
{
Queue *Q = InitQueue();
EnQueue(Q, 1);
EnQueue(Q, 2);
EnQueue(Q, 3);
EnQueue(Q, 4);
EnQueue(Q, 5);
DeQueue(Q);
DeQueue(Q);
DeQueue(Q);
printQueue(Q);
printf("\nThe QueueLength is %d", QueueLength(Q));
printf("\nThe front of Queue is %d", GetHead(Q));
DestroyQueue(Q);
}
Queue* InitQueue()
{
Queue* Q = malloc(sizeof(Q));
Q->array = malloc(sizeof(int) * MaxQueueSize);
Q->front = 0;
Q->rear = 0;
return Q;
}
void DestroyQueue(Queue* Q)
{
free(Q->array);
free(Q);
}
int QueueLength(Queue *Q)
{
return (Q->rear - Q->front + MaxQueueSize) % MaxQueueSize;
}
int EnQueue(Queue *Q, int X)
{
if((Q->rear + 1) % MaxQueueSize == Q->front)
{
return -1;
}
Q->array[Q->rear] = X;
Q->rear = (Q->rear + 1) % MaxQueueSize;
return 0;
}
int DeQueue(Queue* Q)
{
int front;
if(Q->front == Q->rear)
{
return -1;
}
front = Q->array[Q->front];
Q->front = (Q->front + 1) % MaxQueueSize;
return front;
}
void printQueue(Queue *Q)
{
for(int i = Q->front; i < Q->rear; i++)
{
if(i > Q->front)
{
printf("%s", "->");
}
printf("%d", Q->array[i]);
}
}
int IsEmpty(Queue *Q)
{
return QueueLength(Q) == 0;
}
int IsFull(Queue *Q)
{
return QueueLength(Q) == MaxQueueSize - 1;
}
int GetHead(Queue *Q)
{
return Q->array[Q->front];
}
int GetTail(Queue* Q)
{
return Q->value[(Q->rear - 1 + MaxQueueSize) % MaxQueueSize];
}
```
參考資料: 大話數據結構，C语言程序设计现代方法第2版，圖片源於網路(flaticon)
Sign in with Wallet
Connect another wallet