Why Queue Using Two Stacks in DSA Python?

The Big Idea

What if you could turn a last-in-first-out tool into a first-in-first-out line with just two stacks?

The Scenario

Imagine you have a line of people waiting to buy tickets, but you only have two stacks of trays to hold their tickets. You want to serve them in the order they arrived, but the trays only let you add or remove tickets from the top. How do you keep the order correct?

The Problem

Trying to serve people in the right order using just stacks is tricky because stacks only let you add or remove items from the top. If you try to serve the first person who came, you might have to move many tickets around manually, which is slow and confusing.

The Solution

Using two stacks together cleverly lets you reverse the order twice, so you can serve people in the order they arrived. One stack holds incoming tickets, and the other stack helps reverse the order when serving, making the process smooth and efficient.

Before vs After

✗ Before

stack.push(item)
stack.pop()  # only top item accessible
# No direct way to serve first item

✓ After

stack_in.push(item)
if stack_out.is_empty():
    while not stack_in.is_empty():
        stack_out.push(stack_in.pop())
stack_out.pop()  # serves first item

What It Enables

This method lets you build a queue (first-in, first-out) using only stacks (last-in, first-out), enabling you to use simple tools to solve complex ordering problems.

Real Life Example

Think of a printer queue where print jobs arrive and must be printed in order, but the printer only accepts jobs from a stack-like tray. Using two stacks helps manage the jobs so they print in the right order.

Key Takeaways

Stacks alone can't serve items in arrival order easily.

Two stacks together reverse order twice to mimic a queue.

This technique helps manage order with limited tools.