Implement Queue ใน C++ ด้วย Array และ Linked List

Queue เป็นโครงสร้างข้อมูลแบบ FIFO (First-In-First-Out) การเข้า (Enqueue) ที่ rear การออก (Dequeue) ที่ front

Interface มาตรฐาน

Implementation 1: Circular Array (Fixed Size)

#include <iostream>
#include <stdexcept>

using namespace std;

template <typename T>
class ArrayQueue {
    T* data;
    int capacity;
    int frontIdx;
    int rearIdx;
    int count;
    
public:
    explicit ArrayQueue(int cap = 10) 
        : capacity(cap), frontIdx(0), rearIdx(-1), count(0) {
        data = new T[capacity];
    }
    
    ~ArrayQueue() { delete[] data; }
    
    // Delete copy (rule of 5)
    ArrayQueue(const ArrayQueue&) = delete;
    ArrayQueue& operator=(const ArrayQueue&) = delete;
    
    void enqueue(const T& value) {
        if (count == capacity) {
            throw overflow_error("Queue is full");
        }
        rearIdx = (rearIdx + 1) % capacity;
        data[rearIdx] = value;
        ++count;
    }
    
    T dequeue() {
        if (count == 0) {
            throw underflow_error("Queue is empty");
        }
        T value = data[frontIdx];
        frontIdx = (frontIdx + 1) % capacity;
        --count;
        return value;
    }
    
    T& front() {
        if (count == 0) throw underflow_error("Queue is empty");
        return data[frontIdx];
    }
    
    const T& front() const {
        if (count == 0) throw underflow_error("Queue is empty");
        return data[frontIdx];
    }
    
    bool empty() const { return count == 0; }
    int size() const { return count; }
    int getCapacity() const { return capacity; }
    
    void display() const {
        if (empty()) {
            cout << "Queue is empty\n";
            return;
        }
        cout << "Queue: ";
        for (int i = 0; i < count; ++i) {
            int idx = (frontIdx + i) % capacity;
            cout << data[idx] << " ";
        }
        cout << endl;
    }
};

int main() {
    ArrayQueue<int> q(5);
    
    cout << "Enqueue 10, 20, 30, 40, 50:" << endl;
    for (int i = 10; i <= 50; i += 10) q.enqueue(i);
    q.display();  // 10 20 30 40 50
    
    cout << "Dequeue: " << q.dequeue() << endl;  // 10
    cout << "Dequeue: " << q.dequeue() << endl;  // 20
    q.display();  // 30 40 50
    
    cout << "Enqueue 60, 70:" << endl;
    q.enqueue(60);
    q.enqueue(70);
    q.display();  // 30 40 50 60 70
    
    cout << "Front: " << q.front() << endl;  // 30
    cout << "Size: " << q.size() << endl;    // 5
    
    return 0;
}

Implementation 2: Linked List (Dynamic Size)

#include <iostream>
#include <memory>

using namespace std;

template <typename T>
class LinkedQueue {
private:
    struct Node {
        T data;
        unique_ptr<Node> next;
        Node(const T& val) : data(val), next(nullptr) {}
    };
    
    unique_ptr<Node> frontPtr;
    Node* rearPtr;  // raw pointer to last node
    int count;
    
public:
    LinkedQueue() : frontPtr(nullptr), rearPtr(nullptr), count(0) {}
    
    void enqueue(const T& value) {
        auto newNode = make_unique<Node>(value);
        if (empty()) {
            frontPtr = move(newNode);
            rearPtr = frontPtr.get();
        } else {
            rearPtr->next = move(newNode);
            rearPtr = rearPtr->next.get();
        }
        ++count;
    }
    
    T dequeue() {
        if (empty()) throw underflow_error("Queue is empty");
        
        T value = frontPtr->data;
        frontPtr = move(frontPtr->next);
        if (!frontPtr) rearPtr = nullptr;
        --count;
        return value;
    }
    
    T& front() {
        if (empty()) throw underflow_error("Queue is empty");
        return frontPtr->data;
    }
    
    bool empty() const { return count == 0; }
    int size() const { return count; }
    
    void display() const {
        if (empty()) {
            cout << "Queue is empty\n";
            return;
        }
        cout << "Queue: ";
        for (Node* cur = frontPtr.get(); cur; cur = cur->next.get()) {
            cout << cur->data << " ";
        }
        cout << endl;
    }
};

int main() {
    LinkedQueue<string> q;
    
    q.enqueue("Hello");
    q.enqueue("World");
    q.enqueue("C++");
    q.display();  // Hello World C++
    
    cout << "Dequeue: " << q.dequeue() << endl;  // Hello
    q.display();  // World C++
    
    return 0;
}

ใช้งานกับ STL Queue

#include <queue>
#include <iostream>

using namespace std;

int main() {
    queue<int> q;
    
    q.push(10);
    q.push(20);
    q.push(30);
    
    cout << "Front: " << q.front() << endl;  // 10
    cout << "Back: " << q.back() << endl;    // 30
    cout << "Size: " << q.size() << endl;    // 3
    
    while (!q.empty()) {
        cout << q.front() << " ";
        q.pop();
    }
    // Output: 10 20 30
    
    return 0;
}

การประยุกต์ใช้ Queue

• BFS (Breadth-First Search) ในกราฟ/ต้นไม้
• Task Scheduling ใน OS (process queue)
• Print Spooler จัดการคำสั่งพิมพ์
• Buffer/Stream Processing (producer-consumer)
• Level Order Traversal ของต้นไม้

สรุป

เลือก ArrayQueue เมื่อ: ขนาดสูงสุดรู้จัก ต้องการประสิทธิภาพสูงสุด (cache-friendly)
เลือก LinkedQueue เมื่อ: ขนาดไม่ทราบล่วงหน้า ต้องการ dynamic sizing
ในโปรดักชันจริง: ใช้ std::queue หรือ std::deque (STL optimized)