Implement Stack Using Queue in DSA C - Execution Trace

Concept Flow - Implement Stack Using Queue

Initialize empty queue

↓

Push operation: enqueue new element

↓

Rotate queue to move new element to front

↓

Pop operation: dequeue front element

↓

Top operation: peek front element

↓

Check if queue is empty for isEmpty

Use one queue to simulate stack by pushing elements and rotating queue so last pushed is always at front.

Execution Sample

DSA C

void push(int x) {
  enqueue(x);
  for (int i = 0; i < size - 1; i++) {
    enqueue(dequeue());
  }
}

int pop() {
  return dequeue();
}

Push adds element then rotates queue to front; pop removes front element simulating stack pop.

Execution Table

Step	Operation	Queue State Before	Pointer Changes	Queue State After	Visual State
1	Initialize queue	[]	head=0, tail=0	[]	[]
2	push(10)	[]	enqueue 10	[10]	[10]
3	rotate after push	[10]	no rotation needed	[10]	[10]
4	push(20)	[10]	enqueue 20	[10, 20]	[10 -> 20]
5	rotate after push	[10, 20]	dequeue 10, enqueue 10	[20, 10]	[20 -> 10]
6	push(30)	[20, 10]	enqueue 30	[20, 10, 30]	[20 -> 10 -> 30]
7	rotate after push	[20, 10, 30]	dequeue 20, enqueue 20; dequeue 10, enqueue 10	[30, 20, 10]	[30 -> 20 -> 10]
8	pop()	[30, 20, 10]	dequeue 30	[20, 10]	[20 -> 10]
9	top()	[20, 10]	peek front	[20, 10]	top = 20
10	pop()	[20, 10]	dequeue 20	[10]	[10]
11	pop()	[10]	dequeue 10	[]	[]
12	pop() on empty	[]	no dequeue	[]	stack empty

💡 All operations complete; stack simulated by queue rotations.

Variable Tracker

Variable	Start	After push(10)	After push(20)	After push(30)	After pop()	After pop()	After pop()
queue	[]	[10]	[20, 10]	[30, 20, 10]	[20, 10]	[10]	[]
size	0	1	2	3	2	1	0

Key Moments - 3 Insights

Why do we rotate the queue after each push?

Rotating moves the newly added element to the front, so pop() can dequeue it first, simulating stack's LIFO order (see steps 4-7 in execution_table).

What happens if we pop when the queue is empty?

No dequeue happens; the stack is empty and pop returns nothing or error (see step 12 in execution_table).

Why does pop() just dequeue the front element?

Because after rotation, the last pushed element is always at the front, so dequeue simulates stack pop (see step 8 in execution_table).

Visual Quiz - 3 Questions

Look at the execution_table, what is the queue state after push(20) and rotation?

A [20]

B [10, 20]

C [20, 10]

D [10]

💡 Hint

Check step 5 in execution_table for queue state after push(20) rotation.

At which step does the queue first contain three elements?

A Step 4

B Step 6

C Step 5

D Step 7

💡 Hint

Look at queue state before and after push(30) in execution_table steps 6 and 7.

If we skip the rotation after push, what would pop() remove first?

A The first pushed element

B The last pushed element

C An error occurs

D The middle element

💡 Hint

Without rotation, queue order is FIFO, so pop removes oldest element (see concept_flow).

Concept Snapshot

Use one queue to build stack:
- push: enqueue then rotate queue to front
- pop: dequeue front element
- top: peek front
- isEmpty: check queue empty
Rotation ensures last pushed is always front for LIFO behavior.

Full Transcript

This concept shows how to use a single queue to behave like a stack. When pushing, we add the element to the queue and then rotate the queue so that the new element moves to the front. This way, when we pop, we just dequeue the front element, which is the last pushed, simulating stack's last-in-first-out order. The execution table traces each step, showing queue states and pointer changes. Key moments clarify why rotation is needed and what happens on empty pop. The visual quiz tests understanding of queue states and operation effects. The snapshot summarizes the approach for quick recall.

Practice

1. What is the main idea behind implementing a stack using a queue?

easy

A. Use one or two queues to simulate stack operations like push and pop

B. Use a queue to sort elements in ascending order

C. Use a stack to implement queue operations

D. Use two stacks to implement a queue

Solution

1. Step 1: Understand stack and queue differences

   A stack follows Last-In-First-Out (LIFO), while a queue follows First-In-First-Out (FIFO).

2. Step 2: Simulate stack using queue(s)

   By using one or two queues cleverly, we can reorder elements to behave like a stack for push and pop operations.

3. Final Answer:

   Use one or two queues to simulate stack operations like push and pop -> Option A

4. Quick Check:

   Stack via queue = simulate push/pop with queues [OK]

Hint: Remember stack is LIFO, queue is FIFO; simulate LIFO with queue(s) [OK]

Common Mistakes:

• Confusing stack and queue order
• Trying to sort elements instead of simulating stack
• Using stack to implement queue instead

2. Which of the following is the correct syntax to declare a queue in C using the standard library?

easy

A. queue<int> q;

B. struct queue q;

C. #include \nqueue q;

D. No standard queue in C; must implement manually

Solution

1. Step 1: Check C standard library support

   C language does not have a built-in queue data structure in its standard library.

2. Step 2: Understand queue implementation in C

   Queues must be implemented manually using arrays or linked lists in C.

3. Final Answer:

   No standard queue in C; must implement manually -> Option D

4. Quick Check:

   C lacks built-in queue; manual implementation needed [OK]

Hint: C has no built-in queue; implement yourself [OK]

Common Mistakes:

• Assuming C has STL-like queue
• Using C++ syntax in C code
• Including non-existent headers

3. Consider the following code snippet implementing push operation of a stack using one queue in C-like pseudocode:

void push(int x) {
    q.push(x);
    int size = q.size();
    for (int i = 0; i < size - 1; i++) {
        int val = q.front();
        q.pop();
        q.push(val);
    }
}

What will be the order of elements in the queue after pushing 1, then 2, then 3?

medium

A. 3 -> 2 -> 1 -> null

B. 1 -> 2 -> 3 -> null

C. 2 -> 3 -> 1 -> null

D. 3 -> 1 -> 2 -> null

Solution

1. Step 1: Push 1

   Queue after push: [1]

2. Step 2: Push 2

   Push 2: queue becomes [1,2], then rotate first element: pop 1, push 1 -> queue is [2,1]

3. Step 3: Push 3

   Push 3: queue is [2,1,3], rotate first two elements: pop 2 push 2, pop 1 push 1 -> queue is [3,2,1]

4. Final Answer:

   3 -> 2 -> 1 -> null -> Option A

5. Quick Check:

   Newest element at front after push = 3 -> 2 -> 1 [OK]

Hint: After push, rotate queue to put new element front [OK]

Common Mistakes:

• Not rotating queue after push
• Assuming queue order is same as push order
• Confusing front and back of queue

4. The following code attempts to implement pop operation for a stack using two queues. Identify the error:

int pop() {
    if (q1.empty()) return -1;
    while (q1.size() > 1) {
        q2.push(q1.front());
        q1.pop();
    }
    int top = q1.front();
    q1.pop();
    swap(q1, q2);
    return top;
}

medium

A. The queues q1 and q2 are not initialized properly

B. The pop operation does not handle empty stack correctly

C. No error; the code correctly implements pop

D. The swap(q1, q2) should be before popping the last element

Solution

1. Step 1: Analyze pop logic

   Elements except last are moved from q1 to q2, last element is popped from q1.

2. Step 2: Swap queues

   Swapping q1 and q2 makes q1 the queue with remaining elements for next operations.

3. Final Answer:

   No error; the code correctly implements pop -> Option C

4. Quick Check:

   Pop moves all but last, returns last, swaps queues [OK]

Hint: Pop moves all but last to second queue, then swap [OK]

Common Mistakes:

• Swapping queues too early
• Not checking empty queue before pop
• Forgetting to swap queues after pop

5. You want to implement a stack using two queues. Which approach ensures that the pop() operation is O(1) time complexity, and push() is O(n)?

hard

A. Make pop costly by moving all but last from q1 to q2, then popping last from q1

B. Make push costly by pushing element to empty q2, then moving all from q1 to q2, swap q1 and q2

C. Use a single queue and rotate elements after each push

D. Use two stacks instead of queues

Solution

1. Step 1: Understand push costly approach

   Push inserts element into empty q2, moves all q1 elements to q2, then swaps q1 and q2. This makes newest element front in q1.

2. Step 2: Pop becomes O(1)

   Pop just dequeues from q1 front, which is the top of stack, so pop is O(1).

3. Final Answer:

   Make push costly by pushing element to empty q2, then moving all from q1 to q2, swap q1 and q2 -> Option B

4. Quick Check:

   Push costly + pop O(1) = push rearranges queues [OK]

Hint: Push costly rearranges queues; pop just dequeues front [OK]

Common Mistakes:

• Confusing which operation is costly
• Using single queue for O(1) pop incorrectly
• Choosing two stacks instead of queues