Implement Queue ด้วย Two Stacks ใน C++

ใช้ Stack 2 ตัว (LIFO) จำลอง Queue (FIFO) โดยรักษา invariant ว่า stack หนึ่งเก็บข้อมูลเรียง FIFO

วิธีการ: Input/Output Stacks

• inStack: รับข้อมูลใหม่ (push)
• outStack: ให้ข้อมูลออก (pop/front)
• เมื่อ outStack ว่าง → ย้ายทั้งหมดจาก inStack → outStack (กลับลำดับ)

Operations

* Amortized O(1): แต่ละ element ถูกย้ายสูงสุด 1 ครั้ง

ตัวอย่างโค้ด (ใช้ STL stack)

#include <iostream>
#include <stack>
#include <stdexcept>

using namespace std;

template <typename T>
class QueueWithTwoStacks {
    stack<T> inStack;   // For enqueue
    stack<T> outStack;  // For dequeue/front
    
    // Move elements from inStack to outStack (reverses order)
    void transferIfNeeded() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
    }
    
public:
    void enqueue(const T& value) {
        inStack.push(value);
    }
    
    void dequeue() {
        if (empty()) throw underflow_error("Queue empty");
        transferIfNeeded();
        outStack.pop();
    }
    
    T& front() {
        if (empty()) throw underflow_error("Queue empty");
        transferIfNeeded();
        return outStack.top();
    }
    
    const T& front() const {
        return const_cast<QueueWithTwoStacks*>(this)->front();
    }
    
    bool empty() const { return inStack.empty() && outStack.empty(); }
    size_t size() const { return inStack.size() + outStack.size(); }
    
    void display() const {
        // For debugging: show logical order
        stack<T> tempOut = outStack;
        stack<T> tempIn = inStack;
        vector<T> elements;
        
        // outStack has front elements (top = front)
        while (!tempOut.empty()) {
            elements.push_back(tempOut.top());
            tempOut.pop();
        }
        // inStack has back elements (bottom = back) - need to reverse
        vector<T> inElements;
        while (!tempIn.empty()) {
            inElements.push_back(tempIn.top());
            tempIn.pop();
        }
        reverse(inElements.begin(), inElements.end());
        elements.insert(elements.end(), inElements.begin(), inElements.end());
        
        cout << "Queue: ";
        for (const auto& e : elements) cout << e << " ";
        cout << endl;
    }
};

int main() {
    QueueWithTwoStacks<int> q;
    
    cout << "Enqueue: 7, 6, 2, 3\n";
    q.enqueue(7);
    q.enqueue(6);
    q.enqueue(2);
    q.enqueue(3);
    q.display();  // 7 6 2 3
    
    cout << "Dequeue: " << q.front() << endl;  // 7
    q.dequeue();
    q.display();  // 6 2 3
    
    cout << "Dequeue: " << q.front() << endl;  // 6
    q.dequeue();
    q.display();  // 2 3
    
    cout << "Enqueue: 10, 20\n";
    q.enqueue(10);
    q.enqueue(20);
    q.display();  // 2 3 10 20
    
    cout << "Dequeue all:\n";
    while (!q.empty()) {
        cout << q.front() << " ";
        q.dequeue();
    }
    cout << endl;
    
    return 0;
}

ผลลัพธ์

Enqueue: 7, 6, 2, 3
Queue: 7 6 2 3
Dequeue: 7
Queue: 6 2 3
Dequeue: 6
Queue: 2 3
Enqueue: 10, 20
Queue: 2 3 10 20
Dequeue all:
2 3 10 20

วิธีการแบบกลับกัน (ทำ enqueue ช้า dequeue เร็ว)

// Alternative: enqueue O(n), dequeue O(1)
template <typename T>
class QueueWithTwoStacksFastDequeue {
    stack<T> mainStack;  // Always in FIFO order (bottom = front)
    stack<T> tempStack;
    
public:
    void enqueue(const T& value) {
        // Move all to temp
        while (!mainStack.empty()) {
            tempStack.push(mainStack.top());
            mainStack.pop();
        }
        // Push new value (will be at bottom)
        mainStack.push(value);
        // Move back
        while (!tempStack.empty()) {
            mainStack.push(tempStack.top());
            tempStack.pop();
        }
    }
    
    void dequeue() {
        if (empty()) throw underflow_error("Queue empty");
        mainStack.pop();
    }
    
    T& front() {
        if (empty()) throw underflow_error("Queue empty");
        return mainStack.top();
    }
    
    bool empty() const { return mainStack.empty(); }
    size_t size() const { return mainStack.size(); }
};

การเลือกใช้

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

• **Interview question** คלאסิก
• **Persistent Queue** (functional programming)
• **Lock-free queue** implementations
• เข้าใจหลักการ **amortized analysis**

ใน Production Code

ใช้ std::queue (backed by std::deque) หรือ std::deque โดยตรง ซึ่งให้ O(1) ทุก operation และ thread-safe options