Implement Stack using Queues

Implement Stack using Queues

What is this problem about?

The Implement Stack using Queues coding problem asks you to simulate a Last-In-First-Out (LIFO) stack using only one or two standard First-In-First-Out (FIFO) queues. You must implement push, pop, top, and empty using only the standard queue operations (push, peek, pop, size).

Why is this asked in interviews?

Similar to its counterpart (Queue using Stacks), this problem is a classic at companies like Amazon and Adobe to evaluate a candidate's flexible thinking regarding data flow. It tests your ability to manipulate a data structure to behave in a way that is inherently contrary to its design. It also tests your ability to analyze the time complexity of operations when one data structure must "emulate" another.

Algorithmic pattern used

There are two common strategies:

1. Two Queues (Push is $O(N)$): When pushing an element $x$ into Queue 1, first add it to Queue 2, then move all elements from Queue 1 to Queue 2, and finally swap the names of the two queues. This ensures the newest element is always at the front of Queue 1.
2. One Queue (Push is $O(N)$): When pushing $x$, add it to the queue. Then, for size - 1 times, remove the front element and re-add it to the back. This "rotates" the queue until the newest element is at the front.

Example explanation

Using the One Queue approach:

1. push(1): Queue = [1].
2. push(2):
   • Add 2: [1, 2].
   • Rotate (size-1 = 1 time): Pop 1, push 1 $o$ [2, 1].
3. push(3):
   • Add 3: [2, 1, 3].
   • Rotate (2 times):
     • Pop 2, push 2 $o$ [1, 3, 2].
     • Pop 1, push 1 $o$ [3, 2, 1]. Now pop() or top() will correctly return 3, the last element pushed.

Common mistakes candidates make

• Inefficient Pop: Trying to make pop $O(N)$ instead of push. While both are valid, the interviewer often asks for one specifically. Making pop $O(N)$ requires transferring all but one element between queues for every call.
• Wrong Queue Ops: Using non-standard operations like "remove from back" which would turn the queue into a Deque, defeating the purpose of the challenge.

Interview preparation tip

Be ready to discuss the Time vs. Space trade-off. Using one queue saves space but requires more careful "rotation" logic. Using two queues is often more intuitive but doubles the memory footprint.