Implement Queue using Stacks
Understanding the Problem
We need to build a queue (FIFO: first in, first out) using only stacks (LIFO: last in, first out). These two data structures have opposite ordering. When you push elements 1, 2, 3 onto a stack, popping gives you 3, 2, 1. A queue should give you 1, 2, 3 in the same order they went in.
The question is how to reverse the order of elements using stacks. Pushing elements onto one stack and then popping them all into a second stack reverses the order. The element that was at the bottom of the first stack ends up on top of the second stack, which is the element that should come out first in a queue.
What separates the approaches is efficiency, specifically which operation pays the cost of moving elements between stacks. There are two main strategies, and they make opposite choices.
Key Constraints:
1 <= x <= 9→ Values stay small, so there are no overflow concerns and a plainintis enough in every language.- At most
100calls → The volume is low enough that any correct approach passes. The follow-up asking for amortized O(1) is the real design goal. - All
popandpeekcalls are valid → We never have to handle an empty queue for these operations, so the code can skip those guards.
Approach 1: Push-Heavy (Eager Transfer)
Intuition
This approach keeps one stack in queue order at all times so that pop and peek read the oldest element directly off the top. The cost of maintaining that order is paid during push.
We designate one stack as main, where elements are stored in queue order with the oldest on top. When a new element arrives, we move everything from main to a temporary helper stack, push the new element onto the now-empty main, and move everything back. The new element ends up at the bottom of main, and the oldest element returns to the top.
Algorithm
- Maintain two stacks:
main(stores elements in queue order, oldest on top) andhelper(temporary storage during push). - push(x): Move all elements from
maintohelper. Push x ontomain. Move all elements back fromhelpertomain. - pop(): Pop from
main(the top is the oldest element). - peek(): Peek at
main(the top is the oldest element). - empty(): Check if
mainis empty.
Example Walkthrough
Code
- Time Complexity: push is O(n) where n is the number of elements in the queue. We move every element twice. pop, peek, and empty are all O(1).
- Space Complexity: O(n) for storing the elements across the two stacks.
Every push rearranges the entire queue, so a sequence of pushes does repeated O(n) work. The next approach defers the rearranging until a dequeue needs it.
Approach 2: Pop-Heavy (Lazy Transfer) - Amortized O(1)
Intuition
Instead of doing the reordering work during every push, this approach defers it until a dequeue needs it. It uses two stacks with distinct roles: an input stack for pushing and an output stack for popping.
A push appends the element to the input stack and does nothing else, so it is O(1).
A pop or peek reads from the output stack. If the output stack has elements, its top is the oldest element, so we pop or peek directly. If the output stack is empty, we move every element from the input stack into the output stack first. Popping from input and pushing onto output reverses the order, which puts the oldest element on top of output.
Each element is moved at most twice over its lifetime: once onto the input stack, and once during the transfer to the output stack. Across n operations the total movement is O(n), so each operation is amortized O(1).
The transfer is the only step that touches FIFO order, so it has to be safe to defer. It is, because the transfer only runs when output is empty. While output is non-empty, its elements are already in FIFO order from a previous transfer, and any pushes since then sit in input behind them in arrival order. Those newer elements cannot become the front of the queue until every element currently in output has been served, so leaving them untransferred never reorders the queue. Once output drains, the next transfer reverses input in one pass and the elements that have waited longest end up on top.
Algorithm
- Maintain two stacks:
input(receives pushed elements) andoutput(serves pop/peek requests). - push(x): Push x onto the input stack.
- pop(): If the output stack is empty, transfer all elements from input to output (this reverses their order). Pop from the output stack.
- peek(): If the output stack is empty, transfer all elements from input to output. Return the top of the output stack without removing it.
- empty(): Return true only if both stacks are empty.
Example Walkthrough
Code
- Time Complexity: push is O(1). pop and peek are amortized O(1). Worst case for pop/peek is O(n) when a transfer is needed, but each element is transferred at most once, so n operations cost O(n) total. empty is O(1).
- Space Complexity: O(n) where n is the total number of elements in the queue, distributed across the two stacks.