Implementing a Queue Using Two Stacks

A queue follows FIFO (First-In-First-Out) semantics, while a stack follows LIFO (Last-In-First-Out). To simulate queue behavior using only stacks, two stacks are employed: one for input (inStack) and another for output (outStack).

• Push: Elements are always pushed onto inStack.
• Pop / Peek: If outStack is empty, all elements from inStack are transferred to outStack, reversing thier order. The top of outStack then represents the front of the queue.

#include <stack>

class MyQueue {
private:
    std::stack<int> inStack;
    std::stack<int> outStack;

    void transfer() {
        if (outStack.empty()) {
            while (!inStack.empty()) {
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
    }

public:
    void push(int x) {
        inStack.push(x);
    }

    int pop() {
        transfer();
        int val = outStack.top();
        outStack.pop();
        return val;
    }

    int peek() {
        transfer();
        return outStack.top();
    }

    bool empty() {
        return inStack.empty() && outStack.empty();
    }
};

Implementing a Stack Using Two Queues

To mimic LIFO behavior using queues (which are FIFO), two queues (mainQ and helperQ) can be used. The key idea is to maintain the most recently added element at the front of the main queue during each push.

• Push: Add the new element to helperQ, then move all elements from mainQ to helperQ. Swap the queues so mainQ always holds elements in reverse insertion order.
• Pop / Top: Directly access the front of mainQ.

#include <queue>

class MyStack {
private:
    std::queue<int> mainQ;
    std::queue<int> helperQ;

public:
    void push(int x) {
        helperQ.push(x);
        while (!mainQ.empty()) {
            helperQ.push(mainQ.front());
            mainQ.pop();
        }
        std::swap(mainQ, helperQ);
    }

    int pop() {
        int val = mainQ.front();
        mainQ.pop();
        return val;
    }

    int top() {
        return mainQ.front();
    }

    bool empty() {
        return mainQ.empty();
    }
};