Implementing a Queue Using Two Stacks

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

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

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 a Single Queue

A stack requires LIFO behavior. Using a single queue, this is achieved by rotating elements during push or pop so that the most recently added element is always at the front.

In this approach, after pushing a new element, all previous elements are cycled to the back, ensuring the new element stays on top.

class MyStack {
private:
    std::queue<int> q;

public:
    void push(int x) {
        q.push(x);
        // Rotate the queue to place x at the front
        for (int i = 0; i < static_cast<int>(q.size()) - 1; ++i) {
            q.push(q.front());
            q.pop();
        }
    }

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

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

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