Implement Stack ด้วย Two Queues ใน C++

ใช้ Queue 2 ตัว (FIFO) จำลอง Stack (LIFO) โดยรักษา invariant ว่าองค์ประกอบล่าสุดอยู่ที่ front ของ queue หลัก

วิธีการ: Active/Standby Queues

• q1 = active queue (เก็บข้อมูลเรียง LIFO)
• q2 = standby queue (ช่วยย้ายข้อมูล)

Operations

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

#include <iostream>
#include <queue>
#include <stdexcept>

using namespace std;

template <typename T>
class StackWithTwoQueues {
    queue<T> q1, q2;  // q1 = active, q2 = helper
    
public:
    void push(const T& value) {
        q1.push(value);
    }
    
    void pop() {
        if (empty()) throw underflow_error("Stack empty");
        
        // Move all except last from q1 to q2
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        
        // Last element is the top
        q1.pop();
        
        // Swap names
        swap(q1, q2);
    }
    
    T& top() {
        if (empty()) throw underflow_error("Stack empty");
        
        // Move all except last
        while (q1.size() > 1) {
            q2.push(q1.front());
            q1.pop();
        }
        
        T& topVal = q1.front();
        
        // Move last to q2
        q2.push(q1.front());
        q1.pop();
        
        swap(q1, q2);
        return topVal;
    }
    
    const T& top() const {
        return const_cast<StackWithTwoQueues*>(this)->top();
    }
    
    bool empty() const { return q1.empty(); }
    size_t size() const { return q1.size(); }
    
    void display() const {
        // Note: queues don't support iteration directly
        // This is for debugging only - would need to copy
        queue<T> temp = q1;
        cout << "Stack (top to bottom): ";
        while (!temp.empty()) {
            cout << temp.front() << " ";
            temp.pop();
        }
        cout << endl;
    }
};

int main() {
    StackWithTwoQueues<int> st;
    
    cout << "Push: 1, 2, 3, 4, 5\n";
    for (int i = 1; i <= 5; ++i) st.push(i);
    
    cout << "Top: " << st.top() << endl;  // 5
    cout << "Size: " << st.size() << endl; // 5
    
    cout << "\nPop all:\n";
    while (!st.empty()) {
        cout << "Pop: " << st.top() << endl;
        st.pop();
    }
    
    return 0;
}

ผลลัพธ์

Push: 1, 2, 3, 4, 5
Top: 5
Size: 5

Pop all:
Pop: 5
Pop: 4
Pop: 3
Pop: 2
Pop: 1

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

// Alternative: Make push O(n), pop/top O(1)
template <typename T>
class StackWithTwoQueuesFastPop {
    queue<T> q1, q2;
    
public:
    void push(const T& value) {
        // Push to q2 first
        q2.push(value);
        // Move all from q1 to q2
        while (!q1.empty()) {
            q2.push(q1.front());
            q1.pop();
        }
        // Swap
        swap(q1, q2);
    }
    
    void pop() {
        if (empty()) throw underflow_error("Stack empty");
        q1.pop();
    }
    
    T& top() {
        if (empty()) throw underflow_error("Stack empty");
        return q1.front();
    }
    
    bool empty() const { return q1.empty(); }
    size_t size() const { return q1.size(); }
};

การเลือกวิธี

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

นี่เป็น **การฝึกสมอง (educational)** ในการทำงานจริง:

• ใช้ std::vector (amortized O(1) push/pop_back)
• ใช้ std::deque (O(1) ทุก operation)
• ใช้ std::stack (adapter บน deque/vector)

ข้อสังเกต

Queue ที่ใช้ต้องเป็น FIFO จริง (std::queue ใช้ deque เป็น default container) หากใช้ array-based queue ต้องจัดการ circular buffer เอง