Circular Queue การแทรกและลบข้อมูลใน C++

ภาพรวม Circular Queue

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

หลักการทำงาน

• Front - จุดนำข้อมูลออก (Dequeue)
• Rear - จุดใส่ข้อมูลเข้า (Enqueue)
• เมื่อ Rear ถึงปลาย Array จะวนกลับมาที่ Index 0 (ถ้ามีพื้นที่ว่าง)
• ใช้ Modulo Arithmetic: index = (index + 1) % capacity

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

อัลกอริทึม Enqueue (Insert)

INSERT(queue, value):
    IF queue is FULL: return OVERFLOW
    IF queue is EMPTY:
        front = rear = 0
    ELSE:
        rear = (rear + 1) % capacity
    queue[rear] = value

อัลกอริทึม Dequeue (Delete)

DELETE(queue):
    IF queue is EMPTY: return UNDERFLOW
    value = queue[front]
    IF front == rear:  // เหลือแค่ 1 ตัว
        front = rear = -1
    ELSE:
        front = (front + 1) % capacity
    RETURN value

ตัวอย่างโค้ด C++ สมบูรณ์

#include <iostream>
using namespace std;

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

int main() {
    CircularQueue cq;
    
    cout << "=== Circular Queue Demo ===\n\n";
    
    // Insert 5 elements (เต็มคิว)
    cq.enqueue(10);
    cq.enqueue(20);
    cq.enqueue(30);
    cq.enqueue(40);
    cq.enqueue(50);
    cq.display();
    
    // ลอง Insert เพิ่ม (ควร Overflow)
    cout << "\nTrying to insert 60 (should overflow):\n";
    cq.enqueue(60);
    
    // Delete 2 elements
    cout << "\nDeleting 2 elements:\n";
    cq.dequeue();
    cq.dequeue();
    cq.display();
    
    // Insert ใหม่หลังจาก Delete (ทดสอบ Circular)
    cout << "\nInserting 60, 70 after deletion:\n";
    cq.enqueue(60);
    cq.enqueue(70);
    cq.display();
    
    cout << "\nFront: " << cq.getFront() << ", Rear: " << cq.getRear() << endl;
    
    return 0;
}

ผลลัพธ์ตัวอย่าง

=== Circular Queue Demo ===

Inserted: 10 (front=0, rear=0)
Inserted: 20 (front=0, rear=1)
Inserted: 30 (front=0, rear=2)
Inserted: 40 (front=0, rear=3)
Inserted: 50 (front=0, rear=4)
Queue elements: 10 20 30 40 50

Trying to insert 60 (should overflow):
Queue Overflow! Cannot insert 60

Deleting 2 elements:
Deleted: 10 (front=1, rear=4)
Deleted: 20 (front=2, rear=4)
Queue elements: 30 40 50

Inserting 60, 70 after deletion:
Inserted: 60 (front=2, rear=0)
Inserted: 70 (front=2, rear=1)
Queue elements: 30 40 50 60 70

Front: 30, Rear: 70

การแสดงผลภายในหน่วยความจำ (หลัง Insert 60, 70)

Index:  0   1   2   3   4
Array: [60] [70] [30] [40] [50]
              ↑           ↑
            front        rear
            
Logical Order: 30 (front) → 40 → 50 → 60 → 70 (rear)

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

• Enqueue: O(1)
• Dequeue: O(1)
• Front/Rear: O(1)
• Display: O(n)
• พื้นที่: O(capacity)

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

• CPU Scheduling (Round Robin)
• Memory Management (Buffer)
• Traffic Light System
• Printer Spooler
• Streaming Data Buffer

C++ STL Alternative

ใน C++ สามารถใช้ std::queue พร้อม std::deque เป็น underlying container ซึ่งรองรับ Circular behavior อัตโนมัติ:

#include <queue>
#include <deque>

queue> q;  // ใช้ deque เป็น backend
q.push(10);
q.push(20);
cout << q.front();  // 10
q.pop();

multimap::find() ใน C++ STL

Priority Queue ใน C++ STL