Date: 2026-06-06
Time: 17:02
implement-queue-using-stacks/solution.pyThis file solves LeetCode 232: Implement Queue using Stacks. It implements a FIFO queue using only two LIFO stacks (Python lists), which is a classic data structures exercise demonstrating how to simulate one abstract data type with another.
MyQueue — The sole class. Exposes the standard queue interface required by LeetCode:
| Method | Contract |
|--------|----------|
| push(x) | Appends x to the back of the queue. O(1). |
| pop() | Removes and returns the front element. Amortized O(1). Undefined on empty queue. |
| peek() | Returns the front element without removal. Amortized O(1). Undefined on empty queue. |
| empty() | Returns whether the queue has zero elements. O(1). |
| transfer() | Internal helper. Moves all elements from instack to outstack (reversing order) only when out_stack is empty. |
Two-stack amortized queue — This is the textbook approach. The key insight: pushing onto a stack reverses order, so pushing twice (in → out) restores FIFO order. By lazily deferring the transfer until outstack is exhausted, each element moves between stacks exactly once across its lifetime, giving amortized O(1) per operation even though a single pop/peek can take O(n) in the worst case.
The transfer method is guarded by if not self.out_stack — this is the lazy transfer invariant. It ensures elements are only moved when necessary, preserving the amortized cost guarantee.
Imports: None. Uses only built-in list as the stack primitive (append for push, pop for pop, [-1] for peek).
Imported by: The "Imported By" list in the prompt is misleading — it lists hundreds of unrelated test files. The actual consumer is implement-queue-using-stacks/test_solution.py, which imports MyQueue and exercises the interface.
A typical lifecycle:
1. push(1), push(2), push(3) → instack = [1, 2, 3], outstack = []
2. peek() → transfer() fires because outstack is empty → pops 3, 2, 1 from instack and appends to outstack → outstack = [3, 2, 1] → returns 1 (top of out_stack)
3. pop() → outstack is non-empty, no transfer → pops and returns 1 → outstack = [3, 2]
4. push(4) → goes to instack = [4]. The two stacks now coexist: outstack holds older elements in correct order, instack accumulates new arrivals.
5. Two more pop() calls drain outstack, then the next pop() triggers another transfer of instack.
instack (newest-on-top) and outstack (oldest-on-top) always represents the queue in correct order. The logical queue front is outstack[-1] when non-empty, otherwise instack[0].transfer only executes the while-loop when out_stack is empty, so elements never get re-reversed.None. Calling pop() or peek() on an empty queue will raise IndexError from the underlying list — the LeetCode contract guarantees valid calls, so no defensive checks are needed.