Back to Study Material Data Structures and Algorithms

Queue using Stacks

Implementing a queue using only two stacks is a classic interview problem that tests understanding of both data structures. The challenge is to support enq...

Queue using Stacks

Simulating a Queue with Two Stacks

Implementing a queue using only two stacks is a classic interview problem that tests understanding of both data structures. The challenge is to support enqueue and dequeue operations that together maintain first-in, first-out order even though stacks by themselves enforce last-in, first-out order.

The key insight is that two reversals produce the original order. A stack reverses the order of its elements. Reversing once gives LIFO. Reversing twice (by pouring from one stack into another) gives back the original insertion order, which is FIFO.

The solution uses two stacks called inbox and outbox (or push-stack and pop-stack). Enqueue always pushes to inbox. Dequeue checks whether outbox is empty. If outbox is non-empty, pop and return from outbox. If outbox is empty, pop every element from inbox and push each onto outbox, then pop and return from outbox. This transfer reverses the order of inbox elements, placing the oldest element (the one inserted first) at the top of outbox.

Time complexity: enqueue is O(1) always. Dequeue is O(1) amortized. Each element is pushed to inbox once, transferred to outbox at most once, and popped from outbox once. Over any sequence of n operations, the total work is O(n), giving O(1) amortized per operation. However, a single dequeue that triggers a full transfer from inbox to outbox takes O(m) worst-case time where m is the number of elements in inbox at that moment.

Space complexity is O(n) for the two stacks combined. At any given moment, each element exists in exactly one of the two stacks.

Worked example: enqueue 1, enqueue 2, enqueue 3. Inbox: [1, 2, 3] (3 on top), outbox: empty. Dequeue: outbox is empty, transfer all from inbox to outbox. Inbox becomes empty, outbox: [3, 2, 1] (1 on top). Pop outbox: returns 1. Dequeue again: outbox top is 2, return 2. Enqueue 4: inbox: [4]. Dequeue: outbox has 3 on top, return 3. Outbox now empty; next dequeue transfers 4 from inbox.

Interview tip: anticipate the follow-up question about whether the amortized O(1) guarantee holds under adversarial interleaving of enqueue and dequeue. It does, because the transfer cost is always proportional to the number of elements transferred and each element is transferred at most once in its lifetime.

The Lazy Transfer Strategy and Its Guarantees

The two-stack queue implementation above uses a lazy transfer strategy: the inbox is not drained into the outbox until the outbox is completely empty. Understanding why laziness is correct and why it gives amortized O(1) dequeue requires an amortized analysis argument called the banker's method or the potential function method.

Assign each element a charge of two units of computational work when it is enqueued. One unit pays for the push onto inbox. The second unit is saved as a credit. When the element is later transferred from inbox to outbox, it uses its saved credit to pay for that transfer operation. When it is finally popped from outbox, the pop itself costs one unit, but this is already paid for by the transfer unit we just discussed. Wait, let us recount: the credit of two pays for push-to-inbox and the eventual transfer-to-outbox. The pop-from-outbox costs one additional unit, so the total work per element is three units: push, transfer, pop. Assigning three units of charge per enqueue gives a true O(1) amortized cost for all operations.

An eager transfer strategy would move elements from inbox to outbox on every dequeue, maintaining the invariant that outbox is always up to date. This gives O(1) worst-case dequeue but O(n) worst-case enqueue whenever the outbox must be reversed back into inbox and the new element inserted at the correct position. Lazy transfer avoids this by batching the reversal work.

A variant of the two-stack queue allows peek to return the front element without popping. Peek must trigger the same lazy transfer if outbox is empty, then read the top of outbox without popping. The transfer logic is shared between dequeue and peek, so it is best extracted into a helper method called transfer_if_needed that both dequeue and peek call before accessing outbox.

Worked example of amortized analysis: perform 4 enqueues followed by 4 dequeues. Enqueues cost 4 push operations. The first dequeue triggers a transfer of 4 elements (cost 4) plus a pop (cost 1). Dequeues 2, 3, and 4 each cost only one pop from outbox. Total cost: 4 + 4 + 1 + 1 + 1 + 1 = 12 operations for 8 total enqueue and dequeue calls, giving 1.5 operations per call, confirming amortized O(1).

Interview tip: if asked about worst-case time per operation, be honest that a single dequeue is O(n) worst case. Then immediately offer the amortized argument showing the average is O(1). The ability to discuss both perspectives shows mathematical sophistication.

Comparing Queue Implementations: Which to Use and When

Several valid implementations exist for a queue: a linked list with head and tail pointers, a circular array buffer, and a pair of stacks. Each has different trade-offs in worst-case time, amortized time, space overhead, and suitability for concurrent access.

A linked list queue gives O(1) worst-case time for both enqueue and dequeue because each operation touches only the head or tail node and does not involve any batch processing or copying. Space overhead is O(n) plus one pointer per node, which is slightly higher than an array due to pointer storage. Cache locality is poor because nodes may be scattered across the heap.

A circular array queue also gives O(1) worst-case time for both operations (no resizing required for fixed-capacity queues). With dynamic resizing, enqueue is O(1) amortized and O(n) worst case. Space overhead is O(n) with a low constant and excellent cache locality due to contiguous memory.

A two-stack queue gives O(1) worst-case for enqueue and O(1) amortized but O(n) worst case for dequeue. The advantage is that it builds a queue from a data structure that may already be available in the environment, which is useful in functional programming languages where stacks are primitive and queues must be derived. Persistent (immutable) functional queues are typically implemented with two persistent stacks.

For single-threaded use with bounded capacity: circular array is the best choice. For unbounded single-threaded use: linked list or dynamic circular array. For concurrent use: choose a concurrent queue based on your threading model; lock-free linked list queues using compare-and-swap are common in high-throughput systems. For functional or persistent programming: the two-stack approach extends naturally to immutable data structures using persistent lists.

Worked example: a real-time game engine processes player input events with strict latency requirements. A fixed-size circular array queue is ideal because enqueue and dequeue have guaranteed O(1) worst-case time, the memory layout is cache-friendly, and no dynamic allocation occurs during gameplay which could cause garbage-collection pauses.

Interview tip: when asked to choose a queue implementation for a system design problem, always ask about expected throughput, latency requirements, concurrency model, and whether bounded or unbounded capacity is acceptable. These constraints determine the best implementation, not a one-size-fits-all answer.