Queue Using Two Stacks in DSA C# - Execution Trace

Concept Flow - Queue Using Two Stacks

Enqueue Operation

↓

Push element onto Stack1

↓

Done Enqueue

↓

Dequeue Operation

↓

Is Stack2 empty?

No→Pop from Stack2

Yes↓

Transfer all from Stack1 to Stack2

↓

Pop from Stack2

↓

Done Dequeue

Enqueue pushes elements onto Stack1. Dequeue pops from Stack2; if Stack2 is empty, transfer all from Stack1 to Stack2 first.

Execution Sample

DSA C#

Enqueue(1)
Enqueue(2)
Dequeue()
Enqueue(3)
Dequeue()
Dequeue()

This code enqueues 1 and 2, dequeues one element, enqueues 3, then dequeues two elements, showing queue behavior using two stacks.

Execution Table

Step	Operation	Stack1 (top->bottom)	Stack2 (top->bottom)	Action	Visual State
1	Enqueue(1)			Push 1 to Stack1	Stack1: [1] Stack2: []
2	Enqueue(2)	1		Push 2 to Stack1	Stack1: [2,1] Stack2: []
3	Dequeue()	2,1		Stack2 empty, transfer all from Stack1 to Stack2	Stack1: [] Stack2: [1,2]
4	Dequeue()		1,2	Pop top of Stack2 (1)	Stack1: [] Stack2: [2]
5	Enqueue(3)		2	Push 3 to Stack1	Stack1: [3] Stack2: [2]
6	Dequeue()	3	2	Pop top of Stack2 (2)	Stack1: [3] Stack2: []
7	Dequeue()	3		Stack2 empty, transfer all from Stack1 to Stack2, then pop (3)	Stack1: [] Stack2: []

💡 All operations completed; queue is empty after last dequeue.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
Stack1	[]	[1]	[2,1]	[]	[]	[3]	[3]	[]
Stack2	[]	[]	[]	[1,2]	[2]	[2]	[]	[]

Key Moments - 3 Insights

Why do we transfer all elements from Stack1 to Stack2 only when Stack2 is empty during dequeue?

Because Stack2 holds elements in reverse order for dequeue. Transferring only when Stack2 is empty avoids unnecessary moves and preserves correct order, as shown in steps 3 and 7 in the execution_table.

What happens if we try to dequeue when both stacks are empty?

The queue is empty, so dequeue cannot proceed. This case is not shown in the sample but would stop operation or raise an error.

Why does Stack2 have elements in reverse order compared to Stack1 after transfer?

Because elements are popped from Stack1 (top to bottom) and pushed onto Stack2, reversing their order. This reversal makes Stack2's top the oldest element, ready for dequeue, as seen in step 3.

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the state of Stack1 and Stack2 after transferring elements?

A Stack1: [2,1], Stack2: []

B Stack1: [], Stack2: [1,2]

C Stack1: [], Stack2: [2,1]

D Stack1: [1], Stack2: [2]

💡 Hint

Refer to the 'Stack1 (top->bottom)' and 'Stack2 (top->bottom)' columns in row for step 3.

At which step does Stack2 become empty after a dequeue operation?

A Step 4

B Step 7

C Step 6

D Step 5

💡 Hint

Check the 'Stack2 (top->bottom)' column for empty state after dequeue operations.

If we enqueue(4) after step 7, what will be the state of Stack1 and Stack2?

A Stack1: [4], Stack2: []

B Stack1: [], Stack2: [4]

C Stack1: [3,4], Stack2: []

D Stack1: [], Stack2: []

💡 Hint

Enqueue always pushes to Stack1 as shown in steps 1, 2, and 5.

Concept Snapshot

Queue Using Two Stacks:
- Enqueue: push element onto Stack1
- Dequeue: if Stack2 empty, transfer all from Stack1 to Stack2
- Then pop from Stack2
- Stack2 reverses order to maintain FIFO
- Efficient amortized queue using two LIFO stacks

Full Transcript

This visualization shows how a queue can be implemented using two stacks. Enqueue operations push elements onto Stack1. Dequeue operations pop elements from Stack2. If Stack2 is empty during dequeue, all elements from Stack1 are moved to Stack2, reversing their order to maintain queue order. The execution table traces each step, showing stack contents and actions. Variable tracker follows Stack1 and Stack2 states after each operation. Key moments clarify why transfer happens only when Stack2 is empty and how order is preserved. Visual quiz questions test understanding of stack states and operations. The concept snapshot summarizes the approach for quick reference.

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