C++ 實現循環佇列：模板類完整實作與操作詳解

循環佇列 設計核心

• 固定大小陣列 Type* base，容量 capacity。
• 兩指標：front (隊頭索引)、back (隊尾下一插入索引)。
• 判空：front == back；判滿：(back+1)%capacity == front (犧牲一格區分滿/空)。

完整模板類實作

#include <iostream>
#include <cstddef>
using namespace std;

template <typename Type>
class CircleQueue {
    static const size_t INIT_SIZE = 8;
    Type* base;
    size_t capacity;
    size_t front, back;
public:
    explicit CircleQueue(size_t sz = INIT_SIZE)
        : capacity(sz > INIT_SIZE ? sz : INIT_SIZE), front(0), back(0) {
        base = new Type[capacity];
    }
    ~CircleQueue() { destroy(); }
    CircleQueue(const CircleQueue&) = delete;
    CircleQueue& operator=(const CircleQueue&) = delete;

    bool empty() const { return front == back; }
    bool full() const { return (back + 1) % capacity == front; }
    size_t size() const { return (back + capacity - front) % capacity; }

    // 入隊
    void push(const Type& x) {
        if (full()) {
            cerr << "Queue full\n"; return;
        }
        base[back] = x;
        back = (back + 1) % capacity;
    }
    // 出隊
    void pop() {
        if (empty()) { cerr << "Queue empty\n"; return; }
        front = (front + 1) % capacity;
    }
    // 取隊頭
    bool getFront(Type& x) const {
        if (empty()) return false;
        x = base[front];
        return true;
    }
    void clear() { front = back = 0; }
    void destroy() { delete[] base; base = nullptr; capacity = front = back = 0; }

    void show() const {
        if (empty()) { cout << "Queue empty\n"; return; }
        for (size_t i = front; i != back; i = (i + 1) % capacity)
            cout << base[i] << ' ';
        cout << '\n';
    }
};

// 測試
int main() {
    CircleQueue q;
    q.push(1); q.push(2); q.push(3);
    cout << "Size: " << q.size() << '\n'; // 3
    q.show(); // 1 2 3
    int f; q.getFront(f); cout << "Front: " << f << '\n'; // 1
    q.pop(); q.show(); // 2 3
    q.clear(); q.show(); // empty
    return 0;
}

關鍵操作複雜度

設計細節解析

1. 犧牲一格區分滿空：capacity 實際可存 capacity-1 個元素。若需滿用量，可額外加 bool fullFlag 或維護 count 變數。
2. 模運算：(idx+1)%cap 實現指標環繞，size() 用 (back-front+cap)%cap 避免負數。
3. 類別元素析構：pop 僅移動 front，舊元素析構延遲至覆寫或 destroy。嚴格 RAII 需在 pop 呼叫 base[front].~Type()。
4. 擴容：循環佇列擴容需重新線性化拷貝，較堆疊複雜。固定容量場景 (如緩衝區) 較常見。

標準庫替代

#include <queue>
queue q;        // 底層 deque，動態擴容
q.push(1); q.front(); q.pop();

std::queue 以 deque 為預設容器，支援動態增長、無容量上限、介面更豐富。手寫循環佇列適合嵌入式、共享記憶體、高效能固定緩衝區場景。