# The Queue Disguise

> A queue in sheep's clothing.

Canonical URL: <https://datadriven.io/problems/the_queue_disguise>

Domain: Python · Difficulty: medium · Seniority: L4

## Problem

Implement a FIFO queue class using two stacks. Support push(x), pop() (return popped value), peek() (return front), empty() (return bool). Test harness passes ops and returns their outputs parallel: None for push, the value for pop/peek, True/False for empty.

## Worked solution and explanation

### Why this problem exists in real interviews

This is a classic data-structure design question. Interviewers want to see whether you can build FIFO behavior out of LIFO primitives, whether you can reason about amortized cost, and whether you avoid the naive O(n)-per-op solution.

---

### Break down the requirements

#### Step 1: Use two stacks with clear roles

One stack (`_in`) accepts new pushes. The other (`_out`) serves pops and peeks. Never mix the two responsibilities or you lose the amortized guarantee.

#### Step 2: Only refill `_out` when it is empty

When a `pop` or `peek` arrives and `_out` is empty, drain everything from `_in` into `_out`. The reversal turns the most recently pushed element into the top of `_out`, which is the front of the queue.

#### Step 3: Implement `empty()` against both stacks

The queue is empty only when both stacks are empty. Checking just one is the most common bug because elements may sit in `_in` waiting to be shifted.

---

### The solution

**Two stacks with lazy shift on read**

```python
class MyQueueFromStacks:
    def __init__(self):
        self._in = []
        self._out = []

    def push(self, x):
        self._in.append(x)

    def _shift(self):
        if not self._out:
            while self._in:
                self._out.append(self._in.pop())

    def pop(self):
        self._shift()
        return self._out.pop()

    def peek(self):
        self._shift()
        return self._out[-1]

    def empty(self):
        return not self._in and not self._out
```

> **Cost Analysis**
>
> Time: `push` is O(1). `pop` and `peek` are O(1) amortized; each element is moved from `_in` to `_out` exactly once over its lifetime, so N operations cost O(N) total. Space: O(N) for N elements currently in the queue, split across the two stacks.

> **Interviewers Watch For**
>
> Whether you can articulate the amortized argument (every element is shifted at most once), whether you avoid shifting on every pop (which would be O(n) per call), and whether `empty()` checks both stacks. Bonus points for naming the invariant: `_out` always holds the oldest elements with the front on top.

> **Common Pitfall**
>
> Shifting back from `_out` to `_in` after each pop. That destroys the amortized bound and makes every `pop` O(n). The correct rule is: only ever shift one direction, and only when `_out` is empty.

---

## Common follow-up questions

- What is the worst-case time of a single `pop` call, and why is the amortized bound still O(1)? _(Tests amortized analysis. Worst case is O(n) when `_out` is empty and `_in` has n items, but each item only pays for that move once across its lifetime.)_
- How would you implement a queue from a single stack plus recursion? _(Tests creativity and understanding of the call stack as an implicit second stack. Useful to surface whether the candidate sees recursion as a stack.)_
- If the queue must be thread-safe, what changes? _(Tests concurrency awareness. A single mutex around all four ops works but kills throughput; finer-grained locking on `_in` and `_out` separately is harder because of the shift step.)_

## Related

- [All practice problems](https://datadriven.io/problems)
- [Mock interview mode](https://datadriven.io/interview/the_queue_disguise)
- [Python Interview Questions](https://datadriven.io/python-interview-questions)
- [Data Engineering Interview Prep Guide](https://datadriven.io/data-engineer-interview-prep)
- [Daily Challenge](https://datadriven.io/daily)

---

Source: DataDriven (https://datadriven.io). 100% free data engineering interview prep. Live code execution against Postgres 16, Python 3.11, and Spark sandboxes. No paywall, no premium tier, no signup gate.