Implement Deque (Double-Ended Queue) ใน C++

Deque (Double-Ended Queue) เป็นคิวที่เพิ่ม/ลบได้ทั้งสองข้าง รวมความสามารถของ Stack และ Queue

Operations

Implementation: Circular Buffer (Array-based)

#include <iostream>
#include <stdexcept>
#include <algorithm>

using namespace std;

template <typename T>
class Deque {
    T* data;
    int capacity;
    int frontIdx;  // index of front element
    int count;     // number of elements
    
public:
    explicit Deque(int cap = 10) : capacity(cap), frontIdx(0), count(0) {
        data = new T[capacity];
    }
    
    ~Deque() { delete[] data; }
    
    Deque(const Deque&) = delete;
    Deque& operator=(const Deque&) = delete;
    
    // Move semantics
    Deque(Deque&& other) noexcept 
        : data(other.data), capacity(other.capacity), 
          frontIdx(other.frontIdx), count(other.count) {
        other.data = nullptr;
        other.capacity = other.frontIdx = other.count = 0;
    }
    
    void push_front(const T& value) {
        if (count == capacity) throw overflow_error("Deque full");
        frontIdx = (frontIdx - 1 + capacity) % capacity;
        data[frontIdx] = value;
        ++count;
    }
    
    void push_back(const T& value) {
        if (count == capacity) throw overflow_error("Deque full");
        int rearIdx = (frontIdx + count) % capacity;
        data[rearIdx] = value;
        ++count;
    }
    
    T pop_front() {
        if (empty()) throw underflow_error("Deque empty");
        T value = data[frontIdx];
        frontIdx = (frontIdx + 1) % capacity;
        --count;
        return value;
    }
    
    T pop_back() {
        if (empty()) throw underflow_error("Deque empty");
        int rearIdx = (frontIdx + count - 1) % capacity;
        T value = data[rearIdx];
        --count;
        return value;
    }
    
    T& front() {
        if (empty()) throw underflow_error("Deque empty");
        return data[frontIdx];
    }
    
    T& back() {
        if (empty()) throw underflow_error("Deque empty");
        int rearIdx = (frontIdx + count - 1) % capacity;
        return data[rearIdx];
    }
    
    bool empty() const { return count == 0; }
    int size() const { return count; }
    int getCapacity() const { return capacity; }
    
    void display() const {
        if (empty()) {
            cout << "Deque: [empty]\n";
            return;
        }
        cout << "Deque: ";
        for (int i = 0; i < count; ++i) {
            int idx = (frontIdx + i) % capacity;
            cout << data[idx] << (i == count-1 ? "" : " <-> ");
        }
        cout << endl;
    }
};

int main() {
    Deque<int> dq(5);
    
    cout << "Push back: 10, 20, 30\n";
    dq.push_back(10);
    dq.push_back(20);
    dq.push_back(30);
    dq.display();  // 10 <-> 20 <-> 30
    
    cout << "Push front: 5, 1\n";
    dq.push_front(5);
    dq.push_front(1);
    dq.display();  // 1 <-> 5 <-> 10 <-> 20 <-> 30
    
    cout << "Pop back: " << dq.pop_back() << endl;  // 30
    cout << "Pop front: " << dq.pop_front() << endl; // 1
    dq.display();  // 5 <-> 10 <-> 20
    
    cout << "Front: " << dq.front() << ", Back: " << dq.back() << endl;
    
    return 0;
}

ผลลัพธ์

Push back: 10, 20, 30
Deque: 10 <-> 20 <-> 30
Push front: 5, 1
Deque: 1 <-> 5 <-> 10 <-> 20 <-> 30
Pop back: 30
Pop front: 1
Deque: 5 <-> 10 <-> 20
Front: 5, Back: 20

ใช้งานกับ STL std::deque

#include <deque>
#include <iostream>

using namespace std;

int main() {
    deque<int> dq;
    
    dq.push_back(10);
    dq.push_back(20);
    dq.push_front(5);
    dq.push_front(1);
    
    cout << "Deque: ";
    for (int x : dq) cout << x << " ";
    cout << endl;  // 1 5 10 20
    
    cout << "Front: " << dq.front() << endl;  // 1
    cout << "Back: " << dq.back() << endl;    // 20
    
    dq.pop_front();  // remove 1
    dq.pop_back();   // remove 20
    
    // Random access (O(1)) - deque supports []
    cout << "dq[1] = " << dq[1] << endl;  // 10
    
    return 0;
}

Deque vs Vector vs List

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

• Sliding Window Maximum/Minimum (monotonic queue)
• Palindrome Checker (compare front/back)
• Browser History (back/forward)
• Undo/Redo (two deques)
• BFS 0-1 (push_front weight 0, push_back weight 1)