Implement Stack using Queues

How it works

This approach takes a different perspective by nesting structures. Instead of rearranging elements, we create a new queue (or node) for each push that contains the value and a reference to the previous structure. Each push wraps the current state inside a new container, with the new value at the front. This creates a chain where the most recent element is always immediately accessible. In practice, this behaves like building a linked list where each node holds a value and points to the rest of the stack.

Steps

1. Initialize q as null (empty stack).
2. push(x): Create a new queue/node containing x as the first element and the old q as the second element. Update q to point to this new structure.
3. pop(): Extract the first element (the value), update q to point to the second element (the rest of the stack), and return the value.
4. top(): Return the first element of q without modifying anything.
5. empty(): Return true if q is null.

Complexity

• Time complexity:
  • O(1) time for initialization.
  • O(1) time for each push() function call.
  • O(1) time for each pop() function call.
• Space complexity: O(n)

Things to watch for

Incorrect Rotation Count in Single Queue Approach

When using one queue, after pushing a new element, the queue must be rotated exactly size - 1 times to move the new element to the front. A common mistake is rotating size times, which brings the queue back to its original state and leaves the new element at the back. The loop should run for i in range(len(q) - 1), not for i in range(len(q)).

Forgetting to Swap Queues in Two Queue Approach

In the two-queue approach, after moving all elements from q1 to q2 behind the new element, the queues must be swapped so that q1 always contains the elements in stack order. Forgetting to swap means subsequent pop() and top() operations will access the wrong queue, returning incorrect results or causing errors on an empty queue.

from collections import deque

class MyStack:

    def __init__(self):
        self.q = None

    def push(self, x: int) -> None:
        self.q = deque([x, self.q])

    def pop(self) -> int:
        top = self.q.popleft()
        self.q = self.q.popleft()
        return top

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return not self.q

class MyStack {
private:
    struct Node {
        int val;
        shared_ptr<Node> next;
        Node(int v, shared_ptr<Node> n) : val(v), next(n) {}
    };
    shared_ptr<Node> q;

public:
    MyStack() : q(nullptr) {}

    void push(int x) {
        q = make_shared<Node>(x, q);
    }

    int pop() {
        if (!q) return -1;
        int top = q->val;
        q = q->next;
        return top;
    }

    int top() {
        if (!q) return -1;
        return q->val;
    }

    bool empty() {
        return q == nullptr;
    }
};