การนำคิว (Queue) ไปใช้งานด้วยอาร์เรย์ใน C++

Queue และ Array Implementation

Queue เป็นโครงสร้างข้อมูลแบบ FIFO (First In First Out) การนำไปใช้กับอาร์เรย์ต้องจัดการสองขอบ:

• Front (top): จุดนำออก (Dequeue)
• Rear (end): จุดใส่เข้า (Enqueue)

การทำงาน

• เริ่มต้น: front = 0, rear = 0 (คิวว่าง)
• Enqueue: ใส่ที่ rear, เพิ่ม rear++
• Dequeue: ดึงจาก front, เลื่อนข้อมูลซ้าย (shift left), ลด rear--
• Overflow: rear == capacity
• Underflow: front == rear

หมายเหตุ: การ shift left ทำให้ Dequeue เป็น O(n) สามารถปรับปรุงได้ด้วย Circular Queue

ตัวอย่างโค้ด C++

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

struct Queue {
    int front, rear, capacity;
    int* arr;
    
    Queue(int c) : front(0), rear(0), capacity(c) {
        arr = new int[capacity];
    }
    
    ~Queue() { delete[] arr; }
    
    void enqueue(int data) {
        if (rear == capacity) {
            cout << "Queue Overflow\n";
            return;
        }
        arr[rear++] = data;
    }
    
    void dequeue() {
        if (front == rear) {
            cout << "Queue Underflow\n";
            return;
        }
        // Shift left (O(n))
        for (int i = 0; i < rear - 1; i++)
            arr[i] = arr[i + 1];
        rear--;
    }
    
    void display() {
        if (front == rear) {
            cout << "Queue is Empty\n";
            return;
        }
        for (int i = front; i < rear; i++)
            cout << arr[i] << " <-- ";
        cout << endl;
    }
    
    void frontElement() {
        if (front == rear) {
            cout << "Queue is Empty\n";
            return;
        }
        cout << "Front: " << arr[front] << endl;
    }
};

int main() {
    Queue q(4);
    q.display();
    
    q.enqueue(12); q.enqueue(89); q.enqueue(65); q.enqueue(34);
    q.display();        // 12 <-- 89 <-- 65 <-- 34 <--
    
    q.enqueue(92);      // Overflow
    q.display();
    
    q.dequeue(); q.dequeue();
    q.display();        // 65 <-- 34 <--
    
    q.frontElement();   // Front: 65
    return 0;
}

ผลลัพธ์

Queue is Empty
12 <-- 89 <-- 65 <-- 34 <--
Queue Overflow
12 <-- 89 <-- 65 <-- 34 <--
65 <-- 34 <--
Front: 65

การปรับปรุง: Circular Queue

เพื่อให้ Dequeue เป็น O(1) ให้ใช้ Circular Array:

void enqueue(int data) {
    if ((rear + 1) % capacity == front) { /* full */ }
    arr[rear] = data;
    rear = (rear + 1) % capacity;
}

void dequeue() {
    if (front == rear) { /* empty */ }
    front = (front + 1) % capacity;
}