Queue via Two Stacks Explained: Tracing Enqueue 1,2,3 & Dequeue

Imagine you are building a data processor where items must be handled strictly in a First-In, First-Out (FIFO) order: the first item that arrives must be the first one processed. However, your programming environment or memory constraints only give you access to a standard Stack data structure. A stack is strictly Last-In, First-Out (LIFO), meaning elements can only be pushed and popped from the top.

Consider our locked working example: you need to enqueue 1, 2, 3; dequeue; enqueue 4; dequeue, dequeue, dequeue. If you try to store incoming elements directly in a single stack, pushing 1, 2, and then 3 leaves 3 sitting right at the top. The moment you call pop, you get 3 instead of the expected 1. That violates the core rule of our queue, which must yield 1 first.

Without a clever design, you would have to shift elements around in memory constantly or abandon the stack restriction entirely. We need a way to combine two separate stacks—let's call them in and out—to reverse that LIFO order into a reliable FIFO queue. We are given this exact sequence of operations, and our challenge is to design a system where these exact enqueues and dequeues execute in correct chronological sequence.

To bridge the gap between Last-In-First-Out (LIFO) stacks and a First-In-First-Out (FIFO) queue, we divide our data flow into two distinct buckets: an in stack and an out stack. When we perform an enqueue 1,2,3 operation, elements land in the in stack in arrival order, but sitting upside down relative to what a queue needs. To extract them in correct FIFO order, we cannot just pop from the in stack directly—that would yield 3 first, violating our queue contract.

Instead, we treat the in stack purely as a write-append zone and the out stack as a read-drain zone. When a dequeue arrives and the out stack is empty, we pour the entire contents of the in stack into the out stack in a single bulk transfer. This physical inversion flips the order: the bottom of the in stack (which holds our earliest arrival, 1) lands at the very top of the out stack, ready to pop instantly.

Following our locked example, after we enqueue $1,2,$ and 3, our in stack holds $[1,2,3]$ with 3 at the top. The first dequeue forces a pour into the out stack, reversing $[1,2,3]$ into $[3,2,1]$ from bottom to top, allowing us to cleanly pop 1 as our first output.

Try this: State the contents of both the in stack and the out stack immediately after the first dequeue operation in the sequence: enqueue 1,2,3; dequeue.

Let us trace our locked example end-to-end to watch how the input stack ($\text{in}$) and output stack ($\text{out}$) coordinate to preserve strict FIFO order.

Given / Setup:
We start with two empty stacks: $\text{in}=[]$ and $\text{out}=[]$. We will execute the exact sequence: $\text{enqueue}(1),\text{enqueue}(2),\text{enqueue}(3)$, followed by $\text{dequeue}()$, then $\text{enqueue}(4)$, and finally three consecutive $\text{dequeue}()$ operations.

Steps:
1. $\text{enqueue}(1),\text{enqueue}(2),\text{enqueue}(3)$:
- Push each item onto the $\text{in}$ stack as it arrives.
- State: $\text{in}=[1,2,3]$, $\text{out}=[]$.
2. $\text{dequeue}()$ (First Dequeue):
- Check the $\text{out}$ stack. It is empty.
- Transfer all elements from $\text{in}$ to $\text{out}$ by popping from $\text{in}$ and pushing to $\text{out}$.
- Popping 3, then 2, then 1 from $\text{in}$ and pushing them to $\text{out}$ results in $\text{out}=[3,2,1]$ (with 1 at the top).
- Pop the top of $\text{out}$ (1).
- State: $\text{in}=[]$, $\text{out}=[3,2]$.
3. $\text{enqueue}(4)$:
- Push 4 directly onto the $\text{in}$ stack (do not touch $\text{out}$).- State: $\text{in}=[4]$, $\text{out}=[3,2]$.
4. $\text{dequeue}()$ (Second Dequeue):
- Check the $\text{out}$ stack. It is not empty ($\text{out}=[3,2]$ with 2 at the top).
- Pop the top of $\text{out}$ (2) directly without touching $\text{in}$.
- State: $\text{in}=[4]$, $\text{out}=[3]$.
5. $\text{dequeue}()$ (Third Dequeue):
- Pop the next item from $\text{out}$ (3).
- State: $\text{in}=[4]$, $\text{out}=[]$.
6. $\text{dequeue}()$ (Fourth Dequeue):
- Check $\text{out}$. It is empty. Transfer remaining elements from $\text{in}$ to $\text{out}$.
- Pop 4 from $\text{in}$ and push to $\text{out}$. $\text{out}=[4]$.
- Pop the top of $\text{out}$ (4).
- State: $\text{in}=[]$, $\text{out}=[]$.

Result:
The dequeue outputs are 1, then 2, then 3, then 4. FIFO order is perfectly maintained.

Try this: Trace the stack states for: enqueue(5); dequeue(); enqueue(6); dequeue(). Assume starting from empty stacks.

Now it is time to test your mental model against a specific moment in our locked sequence. Recall our working flow: we enqueued $1,2,3$ (all landing in the input stack), performed one dequeue (which flipped them into the output stack as $[3,2,1]$ from bottom to top and popped 1), and then enqueued 4.

Take a moment to reason through where that new element 4 lives right now. Does it go straight to the output stack to keep it full, or does it wait in the input stack while the remaining items (2 and 3) drain from the output stack? Write down or mentally picture the exact contents of both the input stack and output stack right before the next dequeue operation occurs.

Current operation sequence:

Question: What are the exact contents of the input stack and output stack immediately after enqueue(4) is completed?

Now that you have traced the exact state changes for our locked sequence—where $\{1,2,3\}$ entered in, flipped to out, and handled incoming 4 while out still drained—let us look at where else this exact structural trick lives. The core pattern of a Two-Stack Queue is not just an interview quirk; it is a general technique for turning batch-reversal costs into amortized cheap operations whenever you must reconcile Last-In-First-Out hardware with First-In-First-Out consumption.

Consider a real-time text editor or a video game command buffer receiving rapid user input while simultaneously flushing network packets. If you need to process commands in strict chronological order but your incoming socket buffer writes to the back of a LIFO memory pool, applying the two-stack model lets you buffer incoming events in in and batch-flush them to out only when the consumer demands them. This guarantees that your worst-case $O(n)$ flush is amortized across $n$ operations, resulting in a reliable $O(1)$ average time per command.

To test your mastery of this structural transfer, answer the following scenario-based challenge using the exact principles you learned while tracing our locked sequence.