Queue Using Two Stacks in DSA Python - 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 adds elements to Stack1. Dequeue removes from Stack2. If Stack2 is empty, elements from Stack1 are moved to Stack2 to reverse order.

Execution Sample

DSA Python

stack1 = []
stack2 = []

# Enqueue 1
stack1.append(1)

# Enqueue 2
stack1.append(2)

# Dequeue
if not stack2:
    while stack1:
        stack2.append(stack1.pop())
stack2.pop()

This code enqueues 1 and 2, then dequeues one element using two stacks.

Execution Table

Step	Operation	Stack1 State	Stack2 State	Action Description	Visual State
1	Enqueue 1	[]	[]	Push 1 onto Stack1	Stack1: [1], Stack2: []
2	Enqueue 2	[1]	[]	Push 2 onto Stack1	Stack1: [1, 2], Stack2: []
3	Dequeue check Stack2 empty	[1, 2]	[]	Stack2 empty, transfer all from Stack1	Stack1: [], Stack2: [2, 1]
4	Dequeue pop from Stack2	[]	[2, 1]	Pop top element (1) from Stack2	Stack1: [], Stack2: [2]
5	End	[]	[2]	Dequeue complete, returned 1	Stack1: [], Stack2: [2]

💡 Dequeue stops after popping from Stack2 which now has elements reversed from Stack1

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	Final
stack1	[]	[1]	[1, 2]	[]	[]	[]
stack2	[]	[]	[]	[2, 1]	[2]	[2]

Key Moments - 3 Insights

Why do we transfer all elements from stack1 to stack2 during dequeue?

Because stack1 stores elements in enqueue order (newest on top), transferring to stack2 reverses order so oldest element is on top for dequeue, as shown in step 3 of execution_table.

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

There is no element to dequeue; the code would not pop from stack2 because it is empty. This is not shown in the table but is important to check before dequeue.

Why don't we pop directly from stack1 during dequeue?

Popping directly from stack1 would remove the newest element, not the oldest. Using stack2 after transfer ensures FIFO order, as seen in step 4 where stack2.pop() returns the oldest element.

Visual Quiz - 3 Questions

Look at the execution_table, what is the state of stack2 after step 3?

A [2, 1]

B [1, 2]

C []

D [1]

💡 Hint

Refer to the 'Stack2 State' column in row for step 3 in execution_table.

At which step does the oldest element get removed from the queue?

A Step 2

B Step 3

C Step 4

D Step 5

💡 Hint

Check the 'Action Description' column for when pop from Stack2 happens.

If we enqueue another element 3 after step 5, what will be the state of stack1?

A [2, 3]

B [3]

C []

D [1, 3]

💡 Hint

Look at variable_tracker for stack1 final state and recall enqueue pushes onto stack1.

Concept Snapshot

Queue Using Two Stacks:
- Enqueue: push element onto stack1
- Dequeue: if stack2 empty, move all from stack1 to stack2
- Pop from stack2 to dequeue
- This reverses order to maintain FIFO
- Efficient amortized operations

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 so the oldest element is on top. This ensures the queue behaves in FIFO order. The execution table traces enqueueing 1 and 2, then dequeuing one element, showing stack states and actions at each step. Variable tracker shows how stack1 and stack2 change after each operation. Key moments clarify why elements are transferred and why popping directly from stack1 would break queue order. The quiz tests understanding of stack states and operation steps. This method efficiently simulates a queue using two stacks.