Hàng đợi vòng (Circular Queue) - Thêm và xóa trong C++

Hàng đợi (queue) là cấu trúc dữ liệu trừu tượng theo cơ chế FIFO (First In First Out). Triển khai bằng mảng có vấn đề: sau nhiều thao tác thêm/xóa, front và rear dịch chuyển, gây lãng phí ô nhớ trống. Hàng đợi vòng giải quyết bằng cách nối cuối với đầu thành vòng tròn.

Thuật toán

Thêm (insert)

insert(queue, key):
    if (front == 0 && rear == n-1) || (front == rear+1) → queue đầy, trả về
    if front == -1 → front = rear = 0
    else if rear == n-1 → rear = 0
    else rear++
    queue[rear] = key

Xóa (delete)

delete(queue):
    if front == -1 → queue rỗng, trả về
    item = queue[front]
    if front == rear → front = rear = -1
    else if front == n-1 → front = 0
    else front++
    return item

Ví dụ mã nguồn hoàn chỉnh

#include <iostream>
using namespace std;

int cqueue[5];
int front = -1, rear = -1, n = 5;

void themCQ(int val) {
    if ((front == 0 && rear == n-1) || (front == rear+1)) {
        cout << "Queue Overflow\n"; return;
    }
    if (front == -1) { front = 0; rear = 0; }
    else {
        if (rear == n-1) rear = 0;
        else rear++;
    }
    cqueue[rear] = val;
}

void xoaCQ() {
    if (front == -1) {
        cout << "Queue Underflow\n"; return;
    }
    cout << "Phần tử xóa: " << cqueue[front] << endl;
    if (front == rear) { front = -1; rear = -1; }
    else {
        if (front == n-1) front = 0;
        else front++;
    }
}

void hienThiCQ() {
    if (front == -1) { cout << "Queue rỗng\n"; return; }
    cout << "Các phần tử: ";
    if (front <= rear) {
        for (int i = front; i <= rear; i++) cout << cqueue[i] << " ";
    } else {
        for (int i = front; i < n; i++) cout << cqueue[i] << " ";
        for (int i = 0; i <= rear; i++) cout << cqueue[i] << " ";
    }
    cout << endl;
}

int main() {
    int ch, val;
    do {
        cout << "\n1)Thêm\n2)Xóa\n3)Hiển thị\n4)Thoát\nChọn: ";
        cin >> ch;
        switch(ch) {
            case 1: cout << "Giá trị: "; cin >> val; themCQ(val); break;
            case 2: xoaCQ(); break;
            case 3: hienThiCQ(); break;
            case 4: cout << "Thoát\n"; break;
            default: cout << "Sai!\n";
        }
    } while(ch != 4);
    return 0;
}

Kết quả chạy mẫu

1)Thêm 2)Xóa 3)Hiển thị 4)Thoát
Chọn: 1 Giá trị: 10
Chọn: 1 Giá trị: 20
Chọn: 1 Giá trị: 30
Chọn: 1 Giá trị: 40
Chọn: 1 Giá trị: 50
Chọn: 3
Các phần tử: 10 20 30 40 50
Chọn: 2
Phần tử xóa: 10
Chọn: 2
Phần tử xóa: 20
Chọn: 3
Các phần tử: 30 40 50
Chọn: 4
Thoát