# The Impersonator > You only have stacks. Make a queue anyway. Canonical URL: Domain: Python · Difficulty: medium · Seniority: L5 ## Problem Implement a FIFO queue backed by two stacks. Support enqueue(x), dequeue() (return value), peek() (return front). Test harness passes operations; returns parallel results: None for enqueue, the value for dequeue/peek. ## Worked solution and explanation ### Why this problem exists in real interviews Implementing a queue from two stacks is a textbook way to test whether you understand amortized analysis and whether you can resist the obvious-but-wrong eager-transfer design. Interviewers also use it to see whether you handle the empty-dequeue case as an exception (which the harness expects to surface as the literal string 'IndexError') rather than silently returning None. --- ### Break down the requirements #### Step 1: Match the harness API: MyQueue with enqueue/dequeue/peek The class is `MyQueue` with methods `enqueue(value)`, `dequeue()`, and `peek()`. The harness driver `run_my_queue(operations)` reads `[method, *args]` rows, calls `getattr(obj, method)(*args)`, catches IndexError to record the string 'IndexError', and otherwise records the return value (None for enqueue). #### Step 2: Two stacks, one for arrivals and one for departures Keep two lists used as stacks: `in_stack` for new arrivals, `out_stack` for items ready to leave. Enqueue is always `in_stack.append(val)`. Dequeue and peek work off `out_stack.pop()` and `out_stack[-1]` respectively. #### Step 3: Lazy transfer, raise on empty Only refill `out_stack` from `in_stack` when `out_stack` is empty. Pop everything off `in_stack` and push onto `out_stack`, which reverses the order and turns the next pops into FIFO. If both stacks are empty when dequeue or peek is called, raise `IndexError('dequeue from empty queue')` so the harness records 'IndexError'. --- ### The solution **Two-stack MyQueue with lazy transfer and IndexError on empty** ```python class MyQueue: def __init__(self): self.in_stack = [] self.out_stack = [] def enqueue(self, val): self.in_stack.append(val) def dequeue(self): if not self.out_stack: if not self.in_stack: raise IndexError("dequeue from empty queue") while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack.pop() def peek(self): if not self.out_stack: if not self.in_stack: raise IndexError("peek from empty queue") while self.in_stack: self.out_stack.append(self.in_stack.pop()) return self.out_stack[-1] def run_my_queue(operations): obj = MyQueue() results = [] for op in operations: method = op[0] args = op[1:] try: result = getattr(obj, method)(*args) except IndexError: results.append("IndexError") continue results.append(result) return results ``` > **Cost Analysis** > > Enqueue is strictly O(1). Dequeue and peek are O(1) amortized: each element is pushed onto in_stack once, popped off in_stack once, pushed onto out_stack once, and popped off out_stack once, so over n operations the total work is O(n). The worst single dequeue is O(n) when it triggers a full transfer of n queued items, but that cost is paid back over the next n cheap dequeues. Space is O(n) split across the two stacks. > **Interviewers Watch For** > > Whether you explain the amortized argument out loud (n operations cost O(n) total, even though one dequeue can be O(n)), whether you raise IndexError on empty rather than returning None, and whether your peek reuses the same lazy-transfer logic instead of duplicating bookkeeping. Strong candidates also note that `pop(0)` on a Python list is O(n), which is exactly the cost the two-stack design is meant to avoid. > **Common Pitfall** > > Transferring from in_stack to out_stack on every dequeue instead of only when out_stack is empty. The visible test of three enqueues followed by three dequeues works either way, but eager transfer makes every dequeue O(n) and breaks the amortized guarantee. The other classic miss is returning None on empty: the harness checks for the literal string 'IndexError' in its results, so silent Nones make the tests fail without an obvious clue. --- ## Common follow-up questions - How would you implement a stack from two queues, and which operation do you make expensive? _(Tests the inverse construction. The cleanest version makes push the expensive operation: enqueue the new value, then rotate the queue by dequeuing everything else and re-enqueuing it behind the new item. Push becomes O(n), pop is O(1).)_ - What is the worst-case single-operation cost, and why does the amortized analysis still hold? _(Tests whether the candidate knows the amortized bound is for sequences, not single calls. A burst of dequeues on a freshly enqueued queue of size n will see one O(n) call followed by n minus 1 cheap ones.)_ - Where does the two-stack queue actually show up in real systems, as opposed to interview problems? _(Tests knowledge of where this pattern appears: functional or persistent queues built from immutable lists, undo/redo systems, and any environment where only stack-like primitives are exposed (some embedded VMs, certain blockchain VMs).)_ ## Related - [All practice problems](https://datadriven.io/problems) - [Mock interview mode](https://datadriven.io/interview/the_impersonator) - [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.