C++ Program: Implement Circular Queue

Circular Queue (Queue vòng) - Queue mảng cố định kích thước, rear nối với front tạo thành vòng tròn. Tận dụng tối đa bộ nhớ.

Đặc điểm

• Kích thước cố định (static array)
• Front, Rear quay vòng (modulo size)
• Tránh dịch chuyển phần tử như linear queue
• Điều kiện full: (rear + 1) % size == front
• Điều kiện empty: front == -1

Triển khai C++

#include <iostream>
using namespace std;

class CircularQueue {
    int* arr;
    int front, rear, capacity;
public:
    CircularQueue(int size) : capacity(size), front(-1), rear(-1) {
        arr = new int[capacity];
    }
    
    ~CircularQueue() { delete[] arr; }
    
    bool isFull() const {
        return (front == 0 && rear == capacity - 1) || 
               (front == rear + 1);
    }
    
    bool isEmpty() const {
        return front == -1;
    }
    
    void enqueue(int val) {
        if (isFull()) {
            cout << "Queue Overflow\n";
            return;
        }
        if (isEmpty()) front = rear = 0;
        else rear = (rear + 1) % capacity;
        arr[rear] = val;
    }
    
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow\n";
            return;
        }
        cout << "Deleted: " << arr[front] << '\n';
        if (front == rear) front = rear = -1; // Phần tử cuối
        else front = (front + 1) % capacity;
    }
    
    void display() const {
        if (isEmpty()) {
            cout << "Queue empty\n";
            return;
        }
        cout << "Queue: ";
        int i = front;
        while (true) {
            cout << arr[i] << ' ';
            if (i == rear) break;
            i = (i + 1) % capacity;
        }
        cout << '\n';
    }
};

int main() {
    CircularQueue cq(5);
    int choice, val;
    
    do {
        cout << "\n1.Enqueue 2.Dequeue 3.Display 4.Exit\nChoice: ";
        cin >> choice;
        switch (choice) {
            case 1: cout << "Value: "; cin >> val; cq.enqueue(val); break;
            case 2: cq.dequeue(); break;
            case 3: cq.display(); break;
        }
    } while (choice != 4);
}

Kết quả mẫu

1.Enqueue 2.Dequeue 3.Display 4.Exit
Choice: 1
Value: 10
Choice: 1
Value: 20
Choice: 1
Value: 30
Choice: 3
Queue: 10 20 30
Choice: 2
Deleted: 10
Choice: 3
Queue: 20 30
Choice: 1
Value: 40
Choice: 1
Value: 50
Choice: 1
Value: 60
Queue Overflow
Choice: 4

C++ STL: Không có circular_queue chuẩn

Dùng std::deque (double-ended queue) hoặc boost::circular_buffer.

#include <deque>
#include <iostream>

int main() {
    std::deque dq;
    dq.push_back(1); dq.push_back(2); dq.push_back(3);
    dq.push_front(0); // 0 1 2 3
    dq.pop_back();    // 0 1 2
    // Không tự động overwrite khi full - cần logic thủ công
}

Boost Circular Buffer (Nếu có Boost)

#include <boost/circular_buffer.hpp>
#include <iostream>

int main() {
    boost::circular_buffer cb(3);
    cb.push_back(1); cb.push_back(2); cb.push_back(3); // Full
    cb.push_back(4); // Overwrite oldest: 2, 3, 4
    for (int x : cb) cout << x << ' '; // 2 3 4
}

Ứng dụng

• Buffer streaming (audio, video, network)
• Producer-consumer pattern
• Embedded systems (bộ nhớ cố định)
• Sliding window algorithms
• History/undo buffer (fixed size)

So sánh Linear vs Circular Queue