Implement stack using queues

Problem Link

225. Implement Stack using Queues – LeetCode

Problem Statement

Implement a last in first out (LIFO) stack using only two queues.

The implemented stack should support all the functions of a normal stack:

• void push(int x) – Pushes element x onto the stack.

• int pop() – Removes the element on top of the stack and returns it.

• int top() – Returns the top element.

• boolean empty() – Returns true if the stack is empty, false otherwise.

Constraints:

• Only standard queue operations are allowed:

  • add(x) / offer(x) – Insert element at the back

  • poll() – Remove element from front

  • peek() – Get the front element

  • isEmpty()

Examples

Example 1:

Input:
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 2, 2, false]

Intuition

A queue is FIFO (First-In-First-Out), whereas a stack is LIFO (Last-In-First-Out).

To simulate a stack using queues, we need to reverse the order of elements after each push so that the most recent element is always at the front of the queue.

Approach: Two Queues – Reordering on Push

1. Maintain two queues:

   • inqueue: Temporary queue for pushing.

   • stack: Main queue that always keeps the top element at the front.

2. On push(x):

   • Add x to inqueue.

   • Transfer all elements from stack to inqueue.

   • Swap stack and inqueue.

3. On pop():

   • Return stack.poll() (removes front element).

4. On top():

   • Return stack.peek() (accesses front element).

5. On empty():

   • Return stack.isEmpty().

Java Code

class MyStack {
    Queue<Integer> inqueue;
    Queue<Integer> stack;

    public MyStack() {
        inqueue = new LinkedList<>();
        stack = new LinkedList<>();
    }

    public void push(int x) {
        inqueue.add(x);
        while (!stack.isEmpty()) {
            inqueue.add(stack.poll());
        }
        while (!inqueue.isEmpty()) {
            stack.add(inqueue.poll());
        }
    }

    public int pop() {
        return stack.poll();
    }

    public int top() {
        return stack.peek();
    }

    public boolean empty() {
        return stack.isEmpty();
    }
}

Time and Space Complexity

Dry Run

Input:

["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Steps:

• Create a new stack → stack = []

• Push 1 → stack = [1]

• Push 2:

  • inqueue = [2]

  • Move 1 to inqueue → [2, 1]

  • Transfer to stack → [2, 1]

• Top → stack.peek() = 2

• Pop → stack.poll() = 2 → stack = [1]

• Empty → false

Follow-Up: One Queue Optimization

You can optimize using a single queue by rotating it after each push:

public void push(int x) {
    queue.add(x);
    for (int i = 0; i < queue.size() - 1; i++) {
        queue.add(queue.poll());
    }
}

This keeps the newest element at the front, simulating LIFO with a single queue.

Conclusion

This problem reinforces how reordering operations and understanding data structure properties can help simulate one structure (stack) using another (queue).

While this solution uses two queues and incurs O(n) time for push, it keeps pop, top, and empty operations efficient.