Implement Stack Using Queue in DSA Javascript

Mental Model

A stack works like a pile where the last item added is the first to be removed. We can use a queue, which normally removes the first item added, to act like a stack by rearranging items after each addition.

Analogy: Imagine a line of people (queue) where normally the first person in line is served first. To act like a stack, after a new person joins at the end, they move to the front by everyone else stepping back, so the newest person is served first.

Queue before push:
front -> [1, 2, 3] ← rear

After push(4) and rearranging:
front -> [4, 1, 2, 3] ← rear

Dry Run Walkthrough

Input: Start with empty stack, push 1, push 2, push 3, then pop

Goal: Use one queue to simulate stack push and pop operations correctly

Step 1: push 1: enqueue 1

front -> [1] ← rear

Why: Add first element to queue

Step 2: push 2: enqueue 2, then rotate queue to move 2 to front

front -> [2, 1] ← rear

Why: Rotate so newest element is at front to simulate stack top

Step 3: push 3: enqueue 3, then rotate queue to move 3 to front

front -> [3, 2, 1] ← rear

Why: Newest element must be at front for stack pop

Step 4: pop: dequeue front element (3)

front -> [2, 1] ← rear

Why: Remove top element of stack which is front of queue

Result:

front -> [2, 1] ← rear
pop returned 3

Annotated Code

DSA Javascript

class StackUsingQueue {
  constructor() {
    this.queue = [];
  }

  push(x) {
    this.queue.push(x); // enqueue new element
    let size = this.queue.length;
    // rotate queue to move new element to front
    for (let i = 0; i < size - 1; i++) {
      this.queue.push(this.queue.shift()); // dequeue front and enqueue at rear
    }
  }

  pop() {
    if (this.queue.length === 0) return null; // empty stack
    return this.queue.shift(); // dequeue front element as stack pop
  }

  top() {
    if (this.queue.length === 0) return null;
    return this.queue[0]; // front element is stack top
  }

  isEmpty() {
    return this.queue.length === 0;
  }

  print() {
    // print queue as stack from front to rear
    console.log(this.queue.join(' -> ') + ' -> null');
  }
}

// Driver code
const stack = new StackUsingQueue();
stack.push(1);
stack.print();
stack.push(2);
stack.print();
stack.push(3);
stack.print();
console.log('pop:', stack.pop());
stack.print();

this.queue.push(x); // enqueue new element

add new element at rear of queue

for (let i = 0; i < size - 1; i++) { this.queue.push(this.queue.shift()); }

rotate queue to move new element to front simulating stack top

return this.queue.shift(); // dequeue front element as stack pop

remove front element which is top of stack

return this.queue[0]; // front element is stack top

peek front element for stack top

Output

1 -> null

2 -> 1 -> null

3 -> 2 -> 1 -> null

pop: 3

2 -> 1 -> null

Complexity Analysis

Time: O(n) for push because we rotate all elements to move new element to front; O(1) for pop

Space: O(n) for storing n elements in the queue

vs Alternative: Naive approach uses two queues and moves elements between them, which is more complex; this single queue rotation is simpler but push is costlier

Edge Cases

pop from empty stack

returns null safely without error

DSA Javascript

if (this.queue.length === 0) return null;

push single element

element is added and is top immediately

DSA Javascript

this.queue.push(x);

push multiple elements with duplicates

duplicates are handled normally, order maintained as stack

DSA Javascript

for (let i = 0; i < size - 1; i++) { this.queue.push(this.queue.shift()); }

When to Use This Pattern

When you see a problem asking to implement a stack but only queues are allowed, use the queue rotation pattern to simulate stack behavior by rearranging elements after each push.

Common Mistakes

Mistake: Not rotating the queue after push, so the oldest element stays at front
Fix: Rotate the queue by dequeuing and enqueuing all elements except the newly added one to bring the new element to front

Mistake: Trying to pop from empty queue without check
Fix: Add a check to return null or handle empty condition before popping

Summary

Implements a stack using a single queue by rotating elements after each push.

Use when only queue operations are allowed but stack behavior is needed.

The key insight is to rotate the queue so the newest element is always at the front, simulating stack top.

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