Queue using Stacks

Concept

Problem: Implement a First-In-First-Out (FIFO) Queue using only two Last-In-First-Out (LIFO) Stacks.

This is LeetCode 232. It is a classic computer science riddle designed to test your understanding of how Stacks manipulate the ordering of data.

If you push [1, 2, 3] into Stack A, and then pop them out, they come out in reverse order: 3, 2, 1.
If you immediately push that reversed data into Stack B (3, 2, 1), and then pop them out of Stack B… they come out as 1, 2, 3!

The Trick: Pouring data from one stack into another stack perfectly reverses the order. Reversing the order twice brings the data back to its original FIFO order!

Implementation

We will use two stacks:

1. pushStack: Used strictly for Enqueueing data.
2. popStack: Used strictly for Dequeueing data.

When someone calls enqueue(), we just blindly push it onto pushStack. ($O(1)$).
When someone calls dequeue(), we look at popStack. If it has data, we pop it!
If popStack is empty, we must trigger the “Pouring” phase. We pop every single item out of pushStack and push them into popStack. The oldest item is now perfectly sitting at the top of popStack, ready to be dequeued!

class MyQueue {
    private pushStack: number[] = [];
    private popStack: number[] = [];

    // O(1) Push
    push(x: number): void {
        this.pushStack.push(x);
    }

    // Amortized O(1) Pop
    pop(): number {
        this.shiftStacks();
        return this.popStack.pop()!;
    }

    // Amortized O(1) Peek
    peek(): number {
        this.shiftStacks();
        return this.popStack[this.popStack.length - 1];
    }

    empty(): boolean {
        return this.pushStack.length === 0 && this.popStack.length === 0;
    }

    // The Magic Helper Function
    private shiftStacks(): void {
        // ONLY pour if the popStack is completely empty!
        if (this.popStack.length === 0) {
            while (this.pushStack.length > 0) {
                // Pouring perfectly reverses the LIFO into FIFO
                this.popStack.push(this.pushStack.pop()!);
            }
        }
    }
}

Why is Dequeue Amortized O(1)?

When popStack is empty, calling dequeue() triggers a massive while loop that takes $O(N)$ time to pour the data. So how can we claim it is $O(1)$?

Because of Amortized Analysis.
Imagine you enqueue 100 items. pushStack has 100 items.
You call dequeue(). The pour takes $O(N)$ time (100 operations).
But now, popStack has 99 items sitting in perfect order. The next 99 times you call dequeue(), it takes exactly 1 operation ($O(1)$).
If you average out that single 100-operation spike across the 99 instant operations that follow, the mathematical average converges to exactly $O(1)$ per operation.

Interview Questions

Q: A candidate implements the push(x) method by immediately pouring all data from popStack back to pushStack, inserting the new item at the bottom, and pouring everything back. What is the time complexity of their solution?
A: This is a valid, but suboptimal solution. Their solution makes enqueue() an absolute worst-case $O(N)$ operation every single time, because it forces a double-pour on every push. The optimal solution keeps enqueue() at $O(1)$, and makes dequeue() Amortized $O(1)$, which is vastly more efficient for real-world high-throughput systems.

Q: Can you implement a Stack using Queues?
A: Yes! (LeetCode 225). You actually only need one Queue.
To enforce LIFO behavior in a FIFO Queue, whenever you enqueue a new item, you calculate the current size of the queue. Then, you run a loop size times, where you dequeue the front item and instantly enqueue it back to the rear. This mathematically rotates the entire line so the newly added item ends up sitting perfectly at the front of the queue, ready to be popped!