Implement Stack Using Queue in DSA Python - Execution Trace

Concept Flow - Implement Stack Using Queue

Push operation

↓

Enqueue element in queue

↓

Rotate queue to put new element at front

↓

Top element is at front of queue

↓

Pop operation

↓

Dequeue front element from queue

↓

Stack size decreases

↓

Repeat for next operations

Push adds element by enqueue and rotates queue to keep stack order; pop removes front element simulating stack pop.

Execution Sample

DSA Python

class StackUsingQueue:
    def __init__(self):
        self.q = []
    def push(self, x):
        self.q.append(x)
        for _ in range(len(self.q)-1):
            self.q.append(self.q.pop(0))
    def pop(self):
        if self.q:
            return self.q.pop(0)
        else:
            return None

This code pushes elements onto a stack using a single queue by rotating elements.

Execution Table

Step	Operation	Queue State Before	Action	Queue State After	Visual State
1	push(1)	[]	Enqueue 1, rotate 0 times	[1]	1 -> null
2	push(2)	[1]	Enqueue 2, rotate 1 time	[2, 1]	2 -> 1 -> null
3	push(3)	[2, 1]	Enqueue 3, rotate 2 times	[3, 2, 1]	3 -> 2 -> 1 -> null
4	pop()	[3, 2, 1]	Dequeue front (3)	[2, 1]	2 -> 1 -> null
5	pop()	[2, 1]	Dequeue front (2)	[1]	1 -> null
6	push(4)	[1]	Enqueue 4, rotate 1 time	[4, 1]	4 -> 1 -> null
7	pop()	[4, 1]	Dequeue front (4)	[1]	1 -> null
8	pop()	[1]	Dequeue front (1)	[]	empty
9	pop()	[]	Queue empty, cannot pop	[]	empty

💡 Execution stops after last pop attempt on empty queue.

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	After Step 8	After Step 9
q (queue)	[]	[1]	[2, 1]	[3, 2, 1]	[2, 1]	[1]	[4, 1]	[1]	[]	[]
stack size	0	1	2	3	2	1	2	1	0	0

Key Moments - 3 Insights

Why do we rotate the queue after enqueue during push?

Rotating moves the newly added element to the front, so pop can remove it first, simulating stack's LIFO order (see steps 2 and 3 in execution_table).

What happens if we pop when the queue is empty?

Pop operation cannot remove any element and the queue remains empty, as shown in step 9 of execution_table.

Why does the queue state after push show the newest element at front?

Because after enqueue, we rotate the queue so the newest element moves to front, making it the next to pop (see steps 2, 3, and 6).

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue state after step 3 (push(3))?

A [3, 2, 1]

B [2, 1, 3]

C [1, 2, 3]

D [3, 1, 2]

💡 Hint

Check the 'Queue State After' column for step 3 in execution_table.

At which step does the stack size become 0 according to variable_tracker?

A After Step 7

B After Step 8

C After Step 9

D After Step 6

💡 Hint

Look at the 'stack size' row in variable_tracker for when it reaches 0.

If we skip rotating the queue after enqueue in push, what would happen to the pop operation?

A Pop would remove the newest element correctly

B Queue would become empty immediately

C Pop would remove the oldest element, not the newest

D Push would fail to add elements

💡 Hint

Refer to key_moments about why rotation is needed after enqueue.

Concept Snapshot

Implement Stack Using Queue:
- Use one queue to simulate stack
- push(x): enqueue x, then rotate queue to move x to front
- pop(): dequeue front element
- Top element is always at front of queue
- Maintains LIFO order using queue operations

Full Transcript

This concept shows how to build a stack using a single queue. When pushing, we add the element to the queue and then rotate the queue so the new element moves to the front. This way, when we pop, we remove the front element, which is the last pushed element, simulating stack behavior. The execution table tracks each step showing queue states and visual linked list style representation. The variable tracker shows how the queue and stack size change after each operation. Key moments clarify why rotation is necessary and what happens when popping from an empty queue. The visual quiz tests understanding of queue states and stack size changes during execution.