Queue Using Two Stacks in DSA C#

Mental Model

Use two stacks to mimic the behavior of a queue by reversing the order twice.

Analogy: Imagine you have two trays. You put plates on the first tray (stack1). When you want to serve the oldest plate, you flip all plates onto the second tray (stack2), reversing their order, so the oldest plate is now on top and ready to serve.

stack1: top -> []
stack2: top -> []

Dry Run Walkthrough

Input: enqueue 1, enqueue 2, enqueue 3, dequeue, enqueue 4, dequeue

Goal: Simulate queue operations using two stacks and show the queue order after each operation

Step 1: enqueue 1: push 1 onto stack1

stack1: [1] top -> 1
stack2: [] top -> null

Why: New elements go to stack1 to keep insertion order

Step 2: enqueue 2: push 2 onto stack1

stack1: [1, 2] top -> 2
stack2: [] top -> null

Why: Keep adding new elements on top of stack1

Step 3: enqueue 3: push 3 onto stack1

stack1: [1, 2, 3] top -> 3
stack2: [] top -> null

Why: Stack1 holds all new elements

Step 4: dequeue: stack2 empty, move all from stack1 to stack2 reversing order

stack1: [] top -> null
stack2: [3, 2, 1] top -> 1

Why: Reversing stack1 to stack2 makes oldest element accessible on top

Step 5: dequeue: pop top of stack2 (1)

stack1: [] top -> null
stack2: [3, 2] top -> 2

Why: Remove oldest element from queue

Step 6: enqueue 4: push 4 onto stack1

stack1: [4] top -> 4
stack2: [3, 2] top -> 2

Why: New elements always go to stack1

Step 7: dequeue: pop top of stack2 (2)

stack1: [4] top -> 4
stack2: [3] top -> 3

Why: Continue removing from stack2 until empty

Result:

stack1: [4] top -> 4
stack2: [3] top -> 3
Dequeued elements in order: 1, 2

Annotated Code

DSA C#

using System;
using System.Collections.Generic;

class QueueUsingTwoStacks
{
    private Stack<int> stack1 = new Stack<int>();
    private Stack<int> stack2 = new Stack<int>();

    public void Enqueue(int value)
    {
        // Push new element onto stack1
        stack1.Push(value);
    }

    public int Dequeue()
    {
        if (stack2.Count == 0)
        {
            // Move all elements from stack1 to stack2 to reverse order
            while (stack1.Count > 0)
            {
                stack2.Push(stack1.Pop());
            }
        }

        if (stack2.Count == 0)
        {
            throw new InvalidOperationException("Queue is empty");
        }

        // Pop from stack2 which is the oldest element
        return stack2.Pop();
    }

    public void PrintState()
    {
        Console.WriteLine("stack1: [{0}] top -> {1}", string.Join(", ", stack1), (stack1.Count > 0 ? stack1.Peek().ToString() : "null"));
        Console.WriteLine("stack2: [{0}] top -> {1}", string.Join(", ", stack2), (stack2.Count > 0 ? stack2.Peek().ToString() : "null"));
    }
}

class Program
{
    static void Main()
    {
        var queue = new QueueUsingTwoStacks();

        queue.Enqueue(1);
        queue.PrintState();

        queue.Enqueue(2);
        queue.PrintState();

        queue.Enqueue(3);
        queue.PrintState();

        Console.WriteLine("Dequeued: " + queue.Dequeue());
        queue.PrintState();

        queue.Enqueue(4);
        queue.PrintState();

        Console.WriteLine("Dequeued: " + queue.Dequeue());
        queue.PrintState();
    }
}

stack1.Push(value);

push new element onto stack1 to keep insertion order

if (stack2.Count == 0)

check if stack2 is empty to decide if we need to reverse stack1

while (stack1.Count > 0) { stack2.Push(stack1.Pop()); }

move all elements from stack1 to stack2 to reverse order for dequeue

return stack2.Pop();

pop from stack2 to dequeue the oldest element

Output

stack1: [1] top -> 1

stack2: [] top -> null

stack1: [1, 2] top -> 2

stack2: [] top -> null

stack1: [1, 2, 3] top -> 3

stack2: [] top -> null

Dequeued: 1

stack1: [] top -> null

stack2: [3, 2] top -> 2

stack1: [4] top -> 4

stack2: [3, 2] top -> 2

Dequeued: 2

stack1: [4] top -> 4

stack2: [3] top -> 3

Complexity Analysis

Time: O(1) amortized because each element is pushed and popped at most twice

Space: O(n) because we store all elements in two stacks combined

vs Alternative: Compared to a normal queue with O(1) enqueue and dequeue, this uses two stacks but still achieves amortized O(1) dequeue by reversing order only when needed

Edge Cases

dequeue from empty queue

throws InvalidOperationException to indicate no elements

DSA C#

if (stack2.Count == 0) { throw new InvalidOperationException("Queue is empty"); }

enqueue then dequeue single element

element is correctly returned and stacks become empty

DSA C#

while (stack1.Count > 0) { stack2.Push(stack1.Pop()); }

multiple enqueues before any dequeue

all elements accumulate in stack1 until first dequeue triggers reversal

DSA C#

if (stack2.Count == 0) { while (stack1.Count > 0) { stack2.Push(stack1.Pop()); } }

When to Use This Pattern

When you need a queue but only have stacks, use two stacks to reverse order twice and simulate FIFO behavior efficiently.

Common Mistakes

Mistake: Popping directly from stack1 on dequeue instead of reversing to stack2
Fix: Always move elements from stack1 to stack2 if stack2 is empty before popping

Summary

Implements a queue using two stacks by reversing element order twice.

Use when only stack operations are allowed but queue behavior is needed.

The key is to reverse the order by moving elements between two stacks to access the oldest element.

Practice

1. What is the main idea behind implementing a Queue using two stacks?

easy

A. Use one stack for enqueue and another for dequeue operations

B. Use two stacks to store elements in sorted order

C. Use two stacks to reverse the order twice to maintain queue order

D. Use two stacks to store only even and odd elements separately

Solution

1. Step 1: Understand queue order

   A queue follows First-In-First-Out (FIFO) order, meaning the first element added is the first removed.

2. Step 2: Use two stacks to reverse order twice

   One stack reverses the order when pushing elements, and the second stack reverses it back when popping, maintaining FIFO.

3. Final Answer:

   Use two stacks to reverse the order twice to maintain queue order -> Option C

4. Quick Check:

   Two reversals keep FIFO order [OK]

Hint: Two stacks reverse order twice to simulate queue [OK]

Common Mistakes:

• Thinking stacks store sorted elements
• Using stacks for separate data types
• Confusing enqueue and dequeue roles

2. Which of the following is the correct syntax to push an element 5 into a stack named stack1 in C#?

easy

A. stack1.Push(5);

B. stack1.Add(5);

C. stack1.Insert(5);

D. stack1.Enqueue(5);

Solution

1. Step 1: Recall stack push method

   In C#, the Stack<T> class uses the Push method to add elements.

2. Step 2: Check method names

   Add and Insert are not stack methods; Enqueue is for queues.

3. Final Answer:

   stack1.Push(5); -> Option A

4. Quick Check:

   Stack push method = Push() [OK]

Hint: Use Push() to add elements to stack [OK]

Common Mistakes:

• Using Add() or Insert() which are not stack methods
• Confusing Enqueue() with Push()
• Using wrong method names

3. What will be the output of the following C# code implementing a queue using two stacks?

var queue = new QueueUsingTwoStacks();
queue.Enqueue(10);
queue.Enqueue(20);
queue.Enqueue(30);
Console.WriteLine(queue.Dequeue());
queue.Enqueue(40);
Console.WriteLine(queue.Dequeue());

medium

A. 30\n40

B. 10\n20

C. 20\n30

D. 10\n30

Solution

1. Step 1: Enqueue elements 10, 20, 30

   Elements are pushed into the first stack in order: 10, then 20, then 30.

2. Step 2: Dequeue operation

   On dequeue, elements are popped from the second stack after transferring from the first, so 10 is dequeued first.

3. Step 3: Enqueue 40 and dequeue again

   40 is pushed into the first stack. Next dequeue returns 20, the next in queue order.

4. Final Answer:

   10 20 -> Option B

5. Quick Check:

   FIFO order maintained: 10 then 20 [OK]

Hint: Dequeue returns oldest enqueued element first [OK]

Common Mistakes:

• Assuming dequeue returns last pushed element
• Not transferring elements between stacks correctly
• Mixing enqueue and dequeue order

4. Identify the error in the following C# code snippet for dequeue operation in a queue using two stacks:

public int Dequeue()
{
    if (stack2.Count == 0)
    {
        while (stack1.Count > 0)
            stack2.Push(stack1.Pop());
    }
    return stack1.Pop();
}

medium

A. Should pop from stack2, not stack1, after transfer

B. Should check if stack1 is empty before popping

C. Should push elements back to stack1 after popping

D. Should use Peek() instead of Pop()

Solution

1. Step 1: Understand dequeue logic

   After transferring elements from stack1 to stack2, dequeue should pop from stack2 to maintain correct order.

2. Step 2: Identify wrong pop call

   The code incorrectly pops from stack1 instead of stack2 after transfer.

3. Final Answer:

   Should pop from stack2, not stack1, after transfer -> Option A

4. Quick Check:

   Pop from stack2 after transfer [OK]

Hint: Pop from second stack after transfer for dequeue [OK]

Common Mistakes:

• Popping from wrong stack after transfer
• Not checking if stacks are empty
• Using Peek() instead of Pop() for dequeue

5. You want to implement a queue using two stacks where Enqueue is O(1) time and Dequeue is amortized O(1). Which approach is best?

hard

A. Push elements to stack2 on enqueue; pop from stack1 on dequeue

B. Push elements alternately to stack1 and stack2 on enqueue; pop from stack1 on dequeue

C. Push elements to stack1 on enqueue; pop from stack1 on dequeue without transfer

D. Push all elements to stack1 on enqueue; transfer to stack2 only when stack2 is empty during dequeue

Solution

1. Step 1: Understand enqueue O(1) requirement

   Enqueue should just push to stack1 without extra operations for O(1) time.

2. Step 2: Understand dequeue amortized O(1)

   Dequeue transfers elements from stack1 to stack2 only when stack2 is empty, making transfers infrequent and amortized O(1).

3. Step 3: Evaluate options

   Push all elements to stack1 on enqueue; transfer to stack2 only when stack2 is empty during dequeue matches this approach; others do not maintain correct order or time complexity.

4. Final Answer:

   Push all elements to stack1 on enqueue; transfer to stack2 only when stack2 is empty during dequeue -> Option D

5. Quick Check:

   Lazy transfer on dequeue gives amortized O(1) [OK]

Hint: Transfer only when needed on dequeue for amortized O(1) [OK]

Common Mistakes:

• Transferring on every enqueue causing O(n) enqueue
• Popping from wrong stack without transfer
• Alternating pushes breaking queue order