Why Queue Using Two Stacks in DSA C?

The Big Idea

What if you could turn a stack into a queue using just one extra stack? Let's see how!

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 exact order using just stacks is tricky because stacks work like a pile where you can only take the top item. If you try to serve the first person who came, you might have to move many tickets around, which is slow and confusing.

The Solution

Using two stacks together cleverly solves this problem. One stack holds new tickets, and the other stack helps reverse the order when serving. This way, you can add tickets quickly and serve them in the right order without moving everything every time.

Before vs After

✗ Before

void enqueue(int x) {
    stack[top++] = x; // just push
}

int dequeue() {
    // no direct way to get first element
}

✓ After

void enqueue(int x) {
    push(stack1, x);
}

int dequeue() {
    if (isEmpty(stack2)) {
        while (!isEmpty(stack1)) {
            push(stack2, pop(stack1));
        }
    }
    return pop(stack2);
}

What It Enables

This method lets you build a queue using only stacks, keeping the order correct and operations efficient.

Real Life Example

Think of a cafeteria where food trays are stacked in two piles. One pile is for new trays, and when serving, trays are moved to the other pile to serve in the order they arrived.

Key Takeaways

Stacks alone can't serve in first-in-first-out order easily.

Two stacks together can simulate a queue efficiently.

This technique helps when only stack operations are allowed but queue behavior is needed.