Implement queue using stacks

Problem Link

232. Implement Queue using Stacks – LeetCode

Problem Statement

Implement a first in first out (FIFO) queue using only two stacks.

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

void push(int x) – Pushes element x to the back of the queue.
int pop() – Removes the element from the front of the queue and returns it.
int peek() – Returns the element at the front of the queue.
boolean empty() – Returns true if the queue is empty, false otherwise.

Examples

Example 1:

Input:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Output:
[null, null, null, 1, 1, false]

Constraints

1 <= x <= 9
At most 100 calls will be made to push, pop, peek, and empty.
All calls to pop and peek are valid.

Intuition

A stack is LIFO (Last-In-First-Out), while a queue is FIFO (First-In-First-Out). To simulate a queue using stacks, we need to reverse the order of elements when dequeuing.

By using two stacks, we can reorder elements in a way that simulates queue behavior:

One stack handles the pushing of elements.
The other stack handles the popping and peeking, maintaining correct order.

Approach: Two Stacks – Immediate Reversal During Push

Maintain two stacks:
- outStack: Holds elements in queue order (front at the top).
- tempStack: Temporary stack to help reverse order.
Push Operation:
- Reverse outStack into tempStack.
- Push new element onto outStack.
- Reverse tempStack back into outStack.
Pop / Peek Operation:
- Directly access top of outStack.
Empty Check:
- Return whether outStack is empty.

Java Code

class MyQueue {
    private Stack<Integer> outStack;
    private Stack<Integer> tempStack;

    public MyQueue() {
        this.outStack = new Stack<>();
        this.tempStack = new Stack<>();
    }

    public void push(int x) {
        if (outStack.isEmpty()) {
            outStack.push(x);
        } else {
            while (!outStack.isEmpty()) {
                tempStack.push(outStack.pop());
            }
            outStack.push(x);
            while (!tempStack.isEmpty()) {
                outStack.push(tempStack.pop());
            }
        }
    }

    public int pop() {
        return outStack.pop();
    }

    public int peek() {
        return outStack.peek();
    }

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

Time and Space Complexity

Operation	Time Complexity	Explanation
`push`	`O(n)`	Reorders entire stack every push
`pop`	`O(1)`	Top of `outStack`
`peek`	`O(1)`	Top of `outStack`
`empty`	`O(1)`	Check if `outStack` is empty
Space	`O(n)`	All elements stored in stacks

Dry Run

Input:

["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]

Steps:

Create a new MyQueue → outStack = []
Push 1 → outStack = [1]
Push 2:
- Reverse outStack → tempStack = [1]
- Push 2 → outStack = [2]
- Reverse back → outStack = [1, 2]
Peek → Top of outStack → 1
Pop → Remove and return top → 1, outStack = [2]
Empty → false

Follow-Up: Amortized O(1) Time

A better approach reverses elements only when needed, making each operation amortized O(1):

Use two stacks:
- inStack for push
- outStack for pop and peek
Only move elements from inStack to outStack when outStack is empty.

This reduces total time over n operations to O(n).

Conclusion

This problem demonstrates how to simulate queue behavior using stack constraints, reinforcing understanding of stack/queue principles.

While this solution is correct, it can be improved to amortized O(1) using lazy transfer from inStack to outStack.