Implement Stack Using Queue in DSA Javascript - Execution Trace

Concept Flow - Implement Stack Using Queue

Initialize empty queue

↓

Push operation: enqueue element

↓

Rotate queue to move new element to front

↓

Pop operation: dequeue front element

↓

Top operation: peek front element

↓

Check if queue is empty

Stack operations are done by using a single queue where push adds element and then rotates the queue to keep the last pushed element at front, pop removes front, top peeks front.

Execution Sample

DSA Javascript

class Stack {
  constructor() {
    this.queue = [];
  }
  push(x) {
    this.queue.push(x);
    for (let i = 0; i < this.queue.length - 1; i++) {
      this.queue.push(this.queue.shift());
    }
  }
  pop() {
    return this.queue.shift();
  }
  top() {
    return this.queue[0];
  }
  empty() {
    return this.queue.length === 0;
  }
}

This code uses one queue (array) to simulate stack push by rotating queue after enqueue, pop by dequeue front, top by peeking front.

Execution Table

Step	Operation	Queue Before	Action	Queue After	Visual State
1	Initialize stack	[]	Create empty queue	[]	[]
2	push(1)	[]	Enqueue 1, rotate 0 times	[1]	[1]
3	push(2)	[1]	Enqueue 2, rotate 1 time: move 1 to back	[2,1]	[2 -> 1]
4	push(3)	[2,1]	Enqueue 3, rotate 2 times: move 2, then 1 to back	[3,2,1]	[3 -> 2 -> 1]
5	top()	[3,2,1]	Peek front element	[3,2,1]	Top is 3
6	pop()	[3,2,1]	Dequeue front element 3	[2,1]	[2 -> 1]
7	empty()	[2,1]	Check if queue empty	[2,1]	False
8	pop()	[2,1]	Dequeue front element 2	[1]	[1]
9	pop()	[1]	Dequeue front element 1	[]	[]
10	empty()	[]	Check if queue empty	[]	True
11	pop()	[]	Dequeue from empty queue returns undefined	[]	[]

💡 Execution stops after empty queue pop returns undefined and empty() confirms stack is empty

Variable Tracker

Variable	Start	After Step 2	After Step 3	After Step 4	After Step 6	After Step 8	After Step 9	Final
queue	[]	[1]	[2,1]	[3,2,1]	[2,1]	[1]	[]	[]

Key Moments - 3 Insights

Why do we rotate the queue after pushing a new element?

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

What happens if we pop from an empty stack?

Popping from an empty queue returns undefined (step 11), which means the stack is empty and no element can be popped.

Why does top() return the first element of the queue?

Because after rotation in push, the last pushed element is always at the front of the queue, so top() peeks queue[0] as in step 5.

Visual Quiz - 3 Questions

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

A [2, 1, 3]

B [1, 2, 3]

C [3, 2, 1]

D [3, 1, 2]

💡 Hint

Check step 4 in execution_table where push(3) results in queue [3,2,1]

At which step does the stack become empty?

A Step 9

B Step 10

C Step 11

D Step 8

💡 Hint

Check step 9 in execution_table where after pop(1), Queue After is []

If we skip rotating the queue after push, what would happen to pop()?

A pop() would remove the last pushed element correctly

B pop() would remove the oldest element, not the last pushed

C pop() would remove nothing

D pop() would throw an error

💡 Hint

Rotation moves last pushed to front; without it, queue behaves FIFO, so pop removes oldest element

Concept Snapshot

Use one queue to implement stack:
- push(x): enqueue x, then rotate queue to move x to front
- pop(): dequeue front element
- top(): peek front element
- empty(): check if queue is empty
Rotation ensures LIFO order using FIFO queue

Full Transcript

We implement a stack using a single queue. When pushing, we add the element to the queue and then rotate the queue by moving all elements before the new one to the back. This makes the new element appear at the front, simulating stack's last-in-first-out behavior. Popping removes the front element, which is the last pushed. Top peeks the front element. Empty checks if the queue is empty. The execution table shows step-by-step how the queue changes with each operation, confirming the stack behavior.

Practice

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

easy

A. Use two stacks to implement a queue

B. Use an array to implement a queue

C. Use a linked list to implement a stack

D. Use a queue to simulate stack operations by reversing order

Solution

1. Step 1: Understand stack and queue behavior

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

2. Step 2: Simulate stack using queue

   To implement stack using queue, we reverse the order of elements in the queue to mimic LIFO behavior.

3. Final Answer:

   Use a queue to simulate stack operations by reversing order -> Option D

4. Quick Check:

   Stack via queue = reverse order [OK]

Hint: Remember stack is LIFO, queue is FIFO; reverse queue to mimic stack [OK]

Common Mistakes:

• Confusing stack with queue behavior
• Trying to implement queue using stack instead
• Ignoring order reversal needed for stack simulation

2. Which of the following is the correct syntax to enqueue an element `x` into a JavaScript queue implemented as an array named `queue`?

easy

A. queue.shift(x);

B. queue.push(x);

C. queue.pop(x);

D. queue.unshift(x);

Solution

1. Step 1: Identify enqueue operation in JavaScript array

   Enqueue means adding element at the end of the queue, which is done by push().

2. Step 2: Check other methods

   pop() removes from end, shift() removes from front, unshift() adds at front, so only push() adds at end.

3. Final Answer:

   queue.push(x); -> Option B

4. Quick Check:

   Enqueue = push() [OK]

Hint: Use push() to add at queue end in JavaScript arrays [OK]

Common Mistakes:

• Using pop() instead of push() to add elements
• Using shift() or unshift() incorrectly for enqueue
• Confusing enqueue with dequeue operations

3. Consider this JavaScript code implementing a stack using one queue:

class Stack {
  constructor() {
    this.queue = [];
  }
  push(x) {
    this.queue.push(x);
    for (let i = 0; i < this.queue.length - 1; i++) {
      this.queue.push(this.queue.shift());
    }
  }
  pop() {
    return this.queue.shift();
  }
}
const s = new Stack();
s.push(1);
s.push(2);
s.push(3);
console.log(s.pop());

What will be printed?

medium

A. 2

B. 1

C. 3

D. undefined

Solution

1. Step 1: Understand push operation

   Push adds element at end, then rotates queue to move new element to front, simulating stack top.

2. Step 2: Trace push and pop calls

   Push 1: queue=[1]; Push 2: queue=[2,1]; Push 3: queue=[3,2,1]; Pop removes front, which is 3.

3. Final Answer:

   3 -> Option C

4. Quick Check:

   Stack pop = last pushed = 3 [OK]

Hint: Rotate queue after push to keep newest element front [OK]

Common Mistakes:

• Assuming pop removes last element of array instead of front
• Not rotating queue after push
• Confusing queue shift() with stack pop()

4. The following code attempts to implement a stack using two queues. What is the error?

class Stack {
  constructor() {
    this.q1 = [];
    this.q2 = [];
  }
  push(x) {
    this.q1.push(x);
  }
  pop() {
    while (this.q1.length > 1) {
      this.q2.push(this.q1.shift());
    }
    return this.q1.shift();
  }
}

medium

A. pop() does not swap q1 and q2 after operation

B. push() should use q2 instead of q1

C. pop() should return q2.shift() instead of q1.shift()

D. Constructor should initialize q1 and q2 as objects, not arrays

Solution

1. Step 1: Analyze pop method

   Pop moves all but last element from q1 to q2, then removes last from q1.

2. Step 2: Identify missing step

   After pop, q1 is empty and q2 has elements, but q1 and q2 are not swapped, so next pop fails.

3. Final Answer:

   pop() does not swap q1 and q2 after operation -> Option A

4. Quick Check:

   Swap queues after pop to maintain stack [OK]

Hint: Always swap queues after pop in two-queue stack [OK]

Common Mistakes:

• Forgetting to swap queues after pop
• Returning from wrong queue
• Incorrect initialization of queues

5. You want to implement a stack using a single queue in JavaScript. Which approach correctly maintains stack order after each push operation?

class Stack {
  constructor() {
    this.queue = [];
  }
  push(x) {
    this.queue.push(x);
    // What should be done here?
  }
  pop() {
    return this.queue.shift();
  }
}

hard

A. Rotate the queue by dequeuing and enqueuing all elements except the last pushed

B. Sort the queue in descending order after each push

C. Clear the queue and add elements again in reverse order

D. Do nothing; queue order naturally matches stack order

Solution

1. Step 1: Understand stack order with one queue

   Stack is LIFO, but queue is FIFO, so after push, rotate queue to bring new element front.

2. Step 2: Rotate queue after push

   Remove elements from front and add them to back except the last pushed, so last pushed is at front.

3. Final Answer:

   Rotate the queue by dequeuing and enqueuing all elements except the last pushed -> Option A

4. Quick Check:

   Rotate queue after push to simulate stack [OK]

Hint: Rotate queue after push to keep newest element at front [OK]

Common Mistakes:

• Not rotating queue after push
• Trying to sort queue which is inefficient
• Assuming queue order matches stack without changes