Implement Queue using Stacks

Implement Queue using Stacks

What is this problem about?

The Implement Queue using Stacks interview question is a classic data structure adaptation task. You need to implement a First-In-First-Out (FIFO) queue using only two standard Last-In-First-Out (LIFO) stacks. You must support push, pop, peek, and empty operations using only the standard stack operations (push, pop, peek, size).

Why is this asked in interviews?

This is a fundamental problem used by Amazon, Microsoft, and Apple to test a candidate's understanding of how data structures manage elements. It evaluations whether you can think creatively about "reversing" data flow—since two stacks (two LIFO layers) effectively create a FIFO flow. It also tests your ability to analyze amortized time complexity.

Algorithmic pattern used

The problem uses the Two Stacks (In and Out) pattern.

1. Stack 1 (input): All new elements are pushed here.
2. Stack 2 (output): Elements are popped from here.
3. Logic:
   • push(x): Always push to Stack 1. ($O(1)$)
   • pop(): If Stack 2 is empty, transfer all elements from Stack 1 to Stack 2. This reverses their order, making the oldest element the top of Stack 2. Then pop from Stack 2.
   • peek(): Same logic as pop, but return the top instead of removing it.

Example explanation

1. push(1), push(2): Stack 1: [1, 2]. Stack 2: [].
2. pop(): Stack 2 is empty. Transfer! Stack 1: []. Stack 2: [2, 1].
   • Pop from Stack 2 returns 1.
3. push(3): Stack 1: [3]. Stack 2: [2].
4. pop(): Pop from Stack 2 returns 2. Resulting order: 1, then 2. Correct FIFO behavior.

Common mistakes candidates make

• Transfer on every Push: Moving elements back and forth between stacks for every single operation, resulting in $O(N)$ for every step. The optimized "Lazy Transfer" approach is $O(1)$ amortized.
• Empty Checks: Failing to check if both stacks are empty before returning from empty().
• Peek Duplication: Writing separate transfer logic for peek and pop instead of a reusable transferIfEmpty() helper.

Interview preparation tip

Explain Amortized Analysis. While a single pop might take $O(N)$ if a transfer happens, most pop operations will take $O(1)$. Over $N$ operations, the total time is $O(N)$, meaning the average time per operation is $O(1)$. This distinction is what interviewers are looking for.