昨天我們講到佇列的基本概念和實作，今天我們要來介紹環狀佇列 !

什麼是環狀佇列?

簡單來說環狀佇列就是圓形的佇列，這樣講很難懂對吧!
它本質上是一個長度為n的一維陣列 (索引從 0 ~ n-1 )
頭尾接在一起 : 當陣列走到 Q[n-1]時，他下一個位置會繞回開頭 Q[0]

優點 : 可以解決一般佇列在刪除資料後沒辦法判斷是否 overflow 的問題

舉例來說 :
今天有一組大小為 5 的陣列

此時 Queue 已滿

如果我們執行兩次 dequeue()：
取出 10， 20

此時如果繼續執行：enqueue(60)
rear 無法再往後移動，導致 Queue 被誤判為已滿
前面明明還有空間，卻無法被利用，所以環狀佇列正好可以解決這點

下圖為空佇列

指標

和佇列一樣用

front
rear

來追蹤資料的位置

如何判斷佇列狀態

初始狀態 : 沒資料時，front=-1，rear=-1
空佇列條件 : front==rear

因為是環狀結構，所以指標移動不能只用 +1，要用 ％
Enqueue : rear = (rear + 1) % n，將資料放進 Q[rear]
Dequeue : front = (front + 1) % n，取出 Q[front]的資料

程式碼實作

class CircularQueue {
private:
    char* arr;
    int capacity;
    int front;
    int rear;

public:
    CircularQueue(int size) {
        capacity = size;
        arr = new char[capacity];
        front = -1;
        rear = -1;
    }

    bool isEmpty() {
        return front == -1;
    }

    bool isFull() {
        return (rear + 1) % capacity == front;
    }

    void enqueue(char val) {
        if (isFull()) {
            cout << "Queue is full" << endl;
            return;
        }
        if (isEmpty()) {
            front = 0;          // 第一筆資料進來,front 也要初始化
        }
        rear = (rear + 1) % capacity;
        arr[rear] = val;
    }

    char dequeue() {
        if (isEmpty()) {
            cout << "Queue is empty" << endl;
            return '\0';
        }
        char val = arr[front];
        if (front == rear) {
            // 只剩最後一筆資料被取走,佇列變空,front、rear 都重置
            front = -1;
            rear = -1;
        } else {
            front = (front + 1) % capacity;
        }
        return val;
    }
};
int main() {
    CircularQueue q(6);
    q.enqueue('H');
    q.enqueue('e');
    q.enqueue('l');
    q.enqueue('l');
    q.enqueue('o');
    q.enqueue('!');

    cout << q.dequeue() << endl;  // 輸出 H
    cout << q.dequeue() << endl;  // 輸出 e
    
    q.enqueue('j');
    q.enqueue('e');
    return 0;
}

實際跑一次

enqueue

enqueue('H'): 原本是空的,先把 front 設成 0,再執行 rear = (rear+1)%6 = 0
H 放進索引 0

enqueue('e'): rear = (0+1)%6 = 1,e 放進索引 1
rear=1, front=0

enqueue('l'): rear = (1+1)%6 = 2
rear=2, front=0

enqueue('l'): rear = (2+1)%6 = 3
rear=3, front=0

enqueue('o'): rear = (3+1)%6 = 4
rear=4, front=0

enqueue('!'): rear = (4+1)%6 = 5
rear=5, front=0

dequeue

1. front = (0+1)%6 = 1
2. front = (1+1)%6 = 2

enqueue

現在狀態 : front=2, rear=5
enqueue('j')

isFull()?  (0+1)%6 = 1
           1 == front ?  false

繼續執行

rear = (rear + 1) % capacity;  // rear = (5+1)%6 = 0
arr[rear] = val;               // arr[0] = 'j'

現在狀態 : front=2, rear=0

enqueue('e'):

isFull()?  (0+1)%6 = 1
           1 == front  false

繼續執行:

rear = (0+1) % 6 = 1;
arr[1] = 'e';

複雜度

跟一般佇列（用普通陣列，front 只往前移不回收空間）相比，環狀佇列讓已釋放的空間可以被重複利用。

參考資料和書籍

1. https://youtu.be/Tvinx8ioi2s
2. https://hackmd.io/@Tz1_ncbGQtquQhfkU3XfuQ/Sy1Hnp1mI
3. https://liuxiaozhu.github.io/algorithm-test/AlgorithmGossip/QueueByArray.htm