Circular Queue Data Structure ใน C++

ภาพรวม Circular Queue

Circular Queue (คิววงกลม) เป็นการปรับปรุงจาก Linear Queue ที่ใช้ Array โดยการเชื่อมปลายท้ายกับหัวเข้าด้วยกัน แก้ปัญหา "False Overflow" ที่พื้นที่ว่างอยู่แต่แทรกไม่ได้ เพราะ Front/Rear อยู่ปลาย Array

แนวคิดหลัก

• Array ขนาดคงที่ (Fixed Size)
• Front - จุด Dequeue (นำออก)
• Rear - จุด Enqueue (ใส่เข้า)
• ใช้ Modulo Arithmetic สำหรับการวนรอบ: (index + 1) % SIZE

เงื่อนไขสำคัญ

การทำงานแบบทีละขั้นตอน

Enqueue (Insert)

1. ถ้า Full → Overflow
2. ถ้า Empty → front = rear = 0
3. มิฉะนั้น → rear = (rear + 1) % SIZE
4. queue[rear] = value

Dequeue (Delete)

1. ถ้า Empty → Underflow
2. value = queue[front]
3. ถ้า front == rear (เหลือ 1 ตัว) → front = rear = -1
4. มิฉะนั้น → front = (front + 1) % SIZE
5. Return value

ตัวอย่างโค้ด C++ แบบ Interactive Menu

#include <iostream>
using namespace std;

class CircularQueue {
    static const int SIZE = 5;
    int queue[SIZE];
    int front, rear;
    
public:
    CircularQueue() : front(-1), rear(-1) {}
    
    bool isFull() {
        return (front == 0 && rear == SIZE - 1) || (front == rear + 1);
    }
    
    bool isEmpty() {
        return front == -1;
    }
    
    void enqueue(int val) {
        if (isFull()) {
            cout << "Queue Overflow!\n";
            return;
        }
        if (isEmpty()) {
            front = rear = 0;
        } else {
            rear = (rear + 1) % SIZE;
        }
        queue[rear] = val;
        cout << "Inserted: " << val << endl;
    }
    
    void dequeue() {
        if (isEmpty()) {
            cout << "Queue Underflow!\n";
            return;
        }
        cout << "Deleted: " << queue[front] << endl;
        if (front == rear) {
            front = rear = -1;
        } else {
            front = (front + 1) % SIZE;
        }
    }
    
    void display() {
        if (isEmpty()) {
            cout << "Queue is empty\n";
            return;
        }
        cout << "Queue: ";
        int i = front;
        while (true) {
            cout << queue[i] << " ";
            if (i == rear) break;
            i = (i + 1) % SIZE;
        }
        cout << "(front=" << front << ", rear=" << rear << ")\n";
    }
};

int main() {
    CircularQueue cq;
    int choice, val;
    
    do {
        cout << "\n=== Circular Queue Menu ===\n";
        cout << "1. Insert\n2. Delete\n3. Display\n4. Exit\n";
        cout << "Choice: ";
        cin >> choice;
        
        switch (choice) {
            case 1:
                cout << "Value: ";
                cin >> val;
                cq.enqueue(val);
                break;
            case 2:
                cq.dequeue();
                break;
            case 3:
                cq.display();
                break;
            case 4:
                cout << "Exiting...\n";
                break;
            default:
                cout << "Invalid choice!\n";
        }
    } while (choice != 4);
    
    return 0;
}

ตัวอย่างการทำงาน (Simulation)

=== Circular Queue Menu ===
1. Insert
2. Delete
3. Display
4. Exit
Choice: 1
Value: 10
Inserted: 10
Choice: 1
Value: 20
Inserted: 20
Choice: 1
Value: 30
Inserted: 30
Choice: 1
Value: 40
Inserted: 40
Choice: 1
Value: 50
Inserted: 50
Choice: 3
Queue: 10 20 30 40 50 (front=0, rear=4)
Choice: 1
Value: 60
Queue Overflow!
Choice: 2
Deleted: 10
Choice: 2
Deleted: 20
Choice: 3
Queue: 30 40 50 (front=2, rear=4)
Choice: 1
Value: 60
Inserted: 60
Choice: 1
Value: 70
Inserted: 70
Choice: 3
Queue: 30 40 50 60 70 (front=2, rear=1)  // Rear วนรอบ!
Choice: 4
Exiting...

การจัดวางในหน่วยความจำ (Visualization)

หลังจาก Insert 30,40,50,60,70 (front=2, rear=1):

Array Index:  0    1    2    3    4
Value:       [60] [70] [30] [40] [50]
                    ↑         ↑
                  front      rear

Logical Order: 30 → 40 → 50 → 60 → 70
Physical:      index 2 → 3 → 4 → 0 → 1

ความซับซ้อนของอัลกอริทึม

C++ STL Alternative

#include <queue>
#include <deque>

// ใช้ deque เป็น circular buffer
deque cq;
cq.push_back(10);
cq.push_back(20);
// deque จัดการการเติบโตอัตโนมัติ ไม่ต้องกังวล Overflow

// หรือใช้ queue ที่มี underlying container เป็น deque
queue> q;

ประยุกต์ใช้งานจริง

• CPU Scheduling - Round Robin Algorithm
• Interrupt Handling - OS Kernel
• Network Buffers - Packet Queues
• Audio/Video Streaming - Ring Buffer
• Printer Spooler - Print Job Queue
• Traffic Light Control - State Machine

ข้อดีและข้อเสีย

การแก้ปัญหา Wasted Slot

ใช้ตัวนับจำนวน (count variable) แทนการทิ้ง 1 ช่อง:

class CircularQueue {
    int* arr;
    int capacity;
    int front;
    int count;  // จำนวนข้อมูลจริง
    
    bool isFull() { return count == capacity; }
    bool isEmpty() { return count == 0; }
    
    void enqueue(int val) {
        if (isFull()) return;
        int rear = (front + count) % capacity;
        arr[rear] = val;
        count++;
    }
    // ... ไม่ต้องทิ้งช่องว่าง
};

Dequeue และ Priority Queue ใน C++ STL

โปรแกรมหาผลรวมโหนดใน Circular Linked List ด้วย C++