Queue Using Two Stacks in DSA C - Execution Trace

Concept Flow - Queue Using Two Stacks

Enqueue Operation

↓

Push element onto Stack1

↓

Done

↓

Dequeue Operation

↓

Is Stack2 empty?

No→Pop element from Stack2

Yes↓

Transfer all elements from Stack1 to Stack2

↓

Pop element from Stack2

↓

Done

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

Execution Sample

DSA C

push(Stack1, 1);
push(Stack1, 2);
if (empty(Stack2)) transfer from Stack1 to Stack2;
pop(Stack2);  // dequeues 1
pop(Stack2);  // dequeues 2

This code enqueues 1 and 2, then dequeues 1 (transferring first if needed) and then dequeues 2 using two stacks.

Execution Table

Step	Operation	Stack1 (top->bottom)	Stack2 (top->bottom)	Pointer Changes	Visual State
1	Enqueue 1	1	empty	Stack1 push 1	Stack1: [1] Stack2: []
2	Enqueue 2	2 -> 1	empty	Stack1 push 2	Stack1: [2, 1] Stack2: []
3	Dequeue - Stack2 empty, transfer all from Stack1 then pop	empty	1	Pop all from Stack1, push to Stack2 then pop 1 from Stack2	Stack1: [] Stack2: []
4	Dequeue - Pop from Stack2	empty	empty	Stack2 pop 2	Stack1: [] Stack2: []
5	Dequeue - Both stacks empty	empty	empty	No elements to dequeue	Stack1: [] Stack2: []
6	Dequeue - Both stacks empty	empty	empty	No elements to dequeue	Stack1: [] Stack2: []

💡 Execution stops when both stacks are empty and dequeue is requested.

Variable Tracker

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

Key Moments - 3 Insights

Why do we transfer all elements from Stack1 to Stack2 during dequeue?

Because Stack2 holds elements in reverse order for dequeue. When Stack2 is empty, transferring reverses Stack1's order to maintain queue order. See Step 3 in execution_table.

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

There are no elements to dequeue, so the operation cannot proceed. This is shown in Step 6 where both stacks are empty.

Why do we push new elements only onto Stack1 during enqueue?

Stack1 collects new elements in order. We only transfer to Stack2 when dequeuing to reverse order. This keeps enqueue simple and efficient. See Steps 1 and 2.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of Stack2 after Step 3?

A empty

B [2, 1]

C [1, 2]

D [2]

💡 Hint

Check the 'Stack2 (top->bottom)' column in Step 3.

At which step does Stack1 become empty for the first time?

A Step 2

B Step 4

C Step 3

D Step 5

💡 Hint

Look at the 'Stack1 (top->bottom)' column and find when it changes to empty.

If we enqueue 3 after Step 5, what will be the state of Stack1?

A [3, 2]

B [3]

C empty

D [2, 3]

💡 Hint

Enqueue pushes onto Stack1; after Step 5 Stack1 is empty.

Concept Snapshot

Queue Using Two Stacks:
- Enqueue: push element onto Stack1
- Dequeue: pop from Stack2 if not empty
- If Stack2 empty, transfer all from Stack1 to Stack2
- This reverses order to maintain FIFO
- Efficient amortized enqueue and dequeue

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 the queue's FIFO behavior. The execution table tracks each step, showing the contents of both stacks and pointer changes. Key moments clarify why transfer is needed and what happens when stacks are empty. The visual quiz tests understanding of stack states at different steps. This method efficiently simulates a queue using stack operations.