Queue Using Stacks LeetCode 232 Deep Dive

LeetCode 232 — Implement Queue Using Stacks — requires you to build a FIFO queue using only two LIFO stacks as the underlying data structures. You must support four operations: push(x) to enqueue an element, pop() to dequeue the front element, peek() to return the front element without removing it, and empty() to check whether the queue is empty.

The challenge is that stacks operate last-in-first-out while queues operate first-in-first-out. Pushing to a stack puts elements on top; popping removes from the top. A queue must return the oldest element first — the opposite of a stack. The insight is that reversing a stack twice restores the original order, enabling FIFO behavior from two LIFO structures.

The problem is rated Easy but tests a deeper understanding of data structure properties. The naive approach — transferring all elements on every push — gives O(n) push. The optimized approach with lazy transfer achieves amortized O(1) for all operations. Understanding why the amortized analysis works is the real learning objective of LeetCode 232.

The fundamental insight is that a stack reverses insertion order: the last element pushed is the first popped. If you reverse a reversed sequence, you get the original order back. Two stacks applied in sequence perform exactly this double reversal — push to inbox reverses once, transfer to outbox reverses again, so elements emerge from outbox in FIFO order.

The inbox stack serves as a buffer for new pushes. All push(x) calls go directly to inbox. The outbox stack serves pop and peek requests. When outbox is empty and a pop or peek is needed, every element from inbox is popped and pushed onto outbox. This single transfer operation reverses the inbox order, converting the most recently inserted elements into the deepest elements of outbox — precisely the FIFO ordering a queue needs.

The key design decision is to keep the two stacks separate and never mix their roles. Inbox only receives pushes. Outbox only serves pops and peeks. Elements flow one-way from inbox to outbox, never back. This strict separation is what makes the lazy transfer strategy correct and efficient.

The push operation is the simplest of the four: always push the new element onto the inbox stack. There is no need to check outbox, no need to transfer anything, and no need to maintain any sorted or ordered invariant. Inbox accumulates all newly pushed elements in LIFO order — the most recently pushed element sits on top.

This unconditional push to inbox is what makes push O(1) per call. The cost of ordering elements into FIFO sequence is deferred to the first pop or peek that finds outbox empty. This deferral is the essence of the lazy transfer strategy — work is not done until it is needed, and when it is done, it covers all the work that was deferred at once.

An important correctness property: elements that are already in outbox and elements still in inbox can coexist safely. The outbox elements were added before the inbox elements (earlier pushes), so they are correctly the front of the queue. Inbox elements are more recent and will only be served after outbox is exhausted.

Pop and peek both need the front element — the oldest element in the queue. The oldest element is at the bottom of inbox if outbox is empty. To access it, every element in inbox must be popped from inbox and pushed onto outbox, which reverses their order. The bottom of inbox (oldest element) becomes the top of outbox, ready to be popped or peeked in O(1).

The critical rule is: only transfer when outbox is completely empty. If outbox still has elements, those elements are older than anything in inbox, so outbox already has the correct front element on top. Transferring inbox to outbox while outbox is non-empty would mix old and new elements and break FIFO ordering.

After the transfer, pop removes the top of outbox and peek returns it without removing. Both operations are O(1) after the transfer. Future pop and peek calls on a non-empty outbox are also O(1) — no transfer needed until outbox drains again.

Amortized analysis asks: what is the average cost per operation over a sequence of n operations, even if individual operations vary? For the two-stack queue, each element undergoes exactly four stack operations across its lifetime: one push onto inbox, one pop off inbox during transfer, one push onto outbox during transfer, and one pop off outbox during the final pop call.

Summing over n push-pop pairs: each of the n elements performs 4 operations = 4n total stack operations for 2n queue operations. The average cost per queue operation is 4n/2n = 2 = O(1). No element is ever transferred more than once — the invariant is that transfer only happens when outbox is empty, so once an element reaches outbox it stays there until popped.

The worst case for a single pop call is O(n) when outbox is empty and inbox has n elements — the transfer loop runs n times. But this worst-case pop is paid for by the n O(1) pushes that filled inbox. Amortized analysis spreads the O(n) transfer cost evenly across the n pushes that caused it, yielding O(1) per push.

Python: class MyQueue: def __init__(self): self.inbox = []; self.outbox = []. push appends to inbox. _transfer checks if outbox is empty and moves all inbox elements to outbox using a while loop: while self.inbox: self.outbox.append(self.inbox.pop()). pop calls _transfer then returns self.outbox.pop(). peek calls _transfer then returns self.outbox[-1]. empty returns not self.inbox and not self.outbox.

Java: class MyQueue with Deque<Integer> inbox = new ArrayDeque<>() and Deque<Integer> outbox = new ArrayDeque<>(). push calls inbox.push(x). A private transfer() checks if outbox is empty: while (!inbox.isEmpty()) outbox.push(inbox.pop()). pop calls transfer() then outbox.pop(). peek calls transfer() then outbox.peek(). empty returns inbox.isEmpty() && outbox.isEmpty().

Both implementations share the same structure: two lists or stacks, push to inbox unconditionally, a transfer helper that fires only when outbox is empty, and pop/peek delegating to the transfer helper before accessing outbox. Time complexity is O(1) amortized for all four operations. Space complexity is O(n) where n is the number of elements currently in the queue.

Implement Stack Using Queues (LeetCode 225) is the inverse problem: build a LIFO stack from two FIFO queues. The common approach rotates elements in one queue to put the most recently pushed element at the front. This is O(n) push but O(1) pop — the opposite performance profile compared to the two-stack queue here.

Min Stack (LeetCode 155) adds a getMin() operation to a standard stack in O(1) time. The trick is maintaining a parallel min-stack that records the minimum value at each stack depth. Design Circular Queue (LeetCode 622) implements a FIFO queue with fixed capacity using an array and two pointers, demonstrating that queues can be built without any stacks at all.

The stack-queue family — Implement Queue Using Stacks (232), Implement Stack Using Queues (225), Min Stack (155), Design Circular Queue (622), and Design Circular Deque (641) — covers the foundational data structure design interview questions. Mastering the inbox/outbox lazy transfer pattern for LeetCode 232 is the entry point to understanding amortized analysis, which applies throughout algorithm design.