Queue Using Two Stacks in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of enqueue and dequeue operations

What is the printed state of the queue after the following operations using two stacks?

DSA Javascript

class QueueUsingStacks {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }

  enqueue(val) {
    this.stack1.push(val);
  }

  dequeue() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop();
  }

  printQueue() {
    const combined = [...this.stack2.slice().reverse(), ...this.stack1];
    console.log(combined.join(' -> ') + ' -> null');
  }
}

const q = new QueueUsingStacks();
q.enqueue(1);
q.enqueue(2);
q.enqueue(3);
q.dequeue();
q.enqueue(4);
q.printQueue();

A 1 -> 2 -> 3 -> 4 -> null

B 4 -> null

C 3 -> 4 -> null

D 2 -> 3 -> 4 -> null

💡 Hint

Remember that dequeue removes the oldest element, and elements are moved between stacks to maintain order.

After enqueueing 1, 2, 3, the queue is 1 -> 2 -> 3. Dequeue removes 1. Then enqueue 4 adds it to the end. The queue is now 2 -> 3 -> 4.

❓ Predict Output

intermediate

Result after multiple dequeues

What will be the output of the queue after these operations?

DSA Javascript

const q = new (class {
  constructor() {
    this.s1 = [];
    this.s2 = [];
  }
  enqueue(x) { this.s1.push(x); }
  dequeue() {
    if (this.s2.length === 0) {
      while (this.s1.length) this.s2.push(this.s1.pop());
    }
    return this.s2.pop();
  }
  print() {
    const arr = [...this.s2.slice().reverse(), ...this.s1];
    console.log(arr.join(' -> ') + ' -> null');
  }
})();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
q.dequeue();
q.dequeue();
q.print();

A 30 -> null

B 10 -> 20 -> 30 -> null

C 20 -> 30 -> null

D null

💡 Hint

Two dequeues remove the first two enqueued elements.

Enqueued 10, 20, 30. Dequeue removes 10, then 20. Remaining queue is 30.

🔧 Debug

advanced

Identify the error in dequeue method

What error will this code raise when calling dequeue on an empty queue?

DSA Javascript

class QueueTwoStacks {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }
  enqueue(val) {
    this.inStack.push(val);
  }
  dequeue() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }
    return this.outStack.pop();
  }
}
const q = new QueueTwoStacks();
q.dequeue();

A RangeError: Maximum call stack size exceeded

B ReferenceError: q is not defined

C undefined

D TypeError: Cannot read property 'pop' of undefined

💡 Hint

What happens when pop is called on an empty array?

Calling pop on an empty array returns undefined, so dequeue returns undefined without error.

❓ Predict Output

advanced

Queue state after interleaved operations

What is the queue state after these operations?

DSA Javascript

const q = new (class {
  constructor() {
    this.s1 = [];
    this.s2 = [];
  }
  enqueue(x) { this.s1.push(x); }
  dequeue() {
    if (this.s2.length === 0) {
      while (this.s1.length) this.s2.push(this.s1.pop());
    }
    return this.s2.pop();
  }
  print() {
    const arr = [...this.s2.slice().reverse(), ...this.s1];
    console.log(arr.join(' -> ') + ' -> null');
  }
})();
q.enqueue(5);
q.enqueue(6);
q.dequeue();
q.enqueue(7);
q.dequeue();
q.enqueue(8);
q.print();

A 6 -> 7 -> 8 -> null

B 7 -> 8 -> null

C 5 -> 6 -> 7 -> 8 -> null

D 8 -> null

💡 Hint

Track each enqueue and dequeue carefully, noting when stacks transfer elements.

Enqueue 5,6; dequeue removes 5; enqueue 7; dequeue removes 6; enqueue 8; queue is 7 -> 8.

🧠 Conceptual

expert

Time complexity of dequeue operation

What is the amortized time complexity of the dequeue operation in a queue implemented using two stacks?

A O(1) amortized time

B O(n) worst case for every dequeue

C O(log n) amortized time

D O(n^2) worst case

💡 Hint

Consider how often elements are moved between stacks.

Each element is moved at most twice (push and pop), so amortized dequeue is O(1).

Practice

1. What is the main idea behind implementing a Queue using two stacks?

easy

A. Use two stacks to reverse the order twice to maintain queue order

B. Use one stack for enqueue and another for dequeue operations

C. Use two stacks to store elements in sorted order

D. Use one stack to hold even numbers and another for odd numbers

Solution

1. Step 1: Understand queue order

   A queue follows FIFO (First In First Out), so the first element added should be the first removed.

2. Step 2: Use two stacks to reverse order twice

   One stack reverses the order when pushing elements, and the second stack reverses it back when popping, preserving FIFO.

3. Final Answer:

   Use two stacks to reverse the order twice to maintain queue order -> Option A

4. Quick Check:

   Two stacks reverse order twice = Queue order [OK]

Hint: Two reversals with stacks keep queue order intact [OK]

Common Mistakes:

• Thinking one stack alone can maintain queue order
• Confusing stack sorting with queue behavior
• Using stacks for odd/even separation incorrectly

2. Which of the following is the correct syntax to push an element x onto a stack named stack1 in JavaScript?

easy

A. stack1.push(x);

B. stack1.add(x);

C. stack1.insert(x);

D. stack1.enqueue(x);

Solution

1. Step 1: Recall JavaScript stack push method

   JavaScript arrays use push() to add elements at the end, simulating stack push.

2. Step 2: Verify other options

   add(), insert(), and enqueue() are not valid array methods for pushing.

3. Final Answer:

   stack1.push(x); -> Option A

4. Quick Check:

   Array push method = stack1.push(x) [OK]

Hint: Use push() to add elements to stack in JavaScript [OK]

Common Mistakes:

• Using enqueue() which is for queues, not stacks
• Using add() or insert() which are not JavaScript array methods
• Confusing stack push with queue enqueue

3. What will be the output of the following code snippet implementing a queue using two stacks?

class QueueTwoStacks {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }
  enqueue(x) {
    this.stack1.push(x);
  }
  dequeue() {
    if (this.stack2.length === 0) {
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop();
  }
}

const q = new QueueTwoStacks();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log(q.dequeue());
q.enqueue(40);
console.log(q.dequeue());

medium

A. 20
30

B. 30
40

C. 10
30

D. 10
20

Solution

1. Step 1: Trace enqueue operations

   Elements 10, 20, 30 are pushed into stack1 in order: [10, 20, 30].

2. Step 2: Trace first dequeue

   stack2 is empty, so pop all from stack1 to stack2: stack2 becomes [30, 20, 10]. Then pop from stack2 returns 10.

3. Step 3: Enqueue 40 and second dequeue

   40 is pushed to stack1: [40]. stack2 still has [30, 20]. Dequeue pops from stack2 returning 20.

4. Final Answer:

   10 20 -> Option D

5. Quick Check:

   FIFO order maintained: 10 then 20 dequeued [OK]

Hint: Dequeue empties stack2 first, then pops top [OK]

Common Mistakes:

• Assuming dequeue pops directly from stack1
• Not transferring all elements to stack2 before dequeue
• Mixing order of elements after transfer

4. Identify the bug in this dequeue method of a queue implemented using two stacks:

dequeue() {
  while (this.stack1.length > 0) {
    this.stack2.push(this.stack1.pop());
  }
  return this.stack2.pop();
}

medium

A. It pops from stack1 instead of stack2

B. It never transfers elements from stack1 to stack2

C. It empties stack1 every dequeue without checking if stack2 is empty

D. It returns undefined always

Solution

1. Step 1: Analyze the transfer logic

   The method transfers all elements from stack1 to stack2 every time dequeue is called, without checking if stack2 is empty.

2. Step 2: Understand consequence

   This causes new elements to be appended to stack2 (which may have remaining older elements), violating FIFO as new elements are popped before older ones.

3. Final Answer:

   It empties stack1 every dequeue without checking if stack2 is empty -> Option C

4. Quick Check:

   Transfer only if stack2.length === 0 [OK]

Hint: Transfer only when stack2 is empty to keep elements safe [OK]

Common Mistakes:

• Transferring elements every dequeue call
• Not checking if stack2 is empty before transfer
• Confusing which stack to pop from

5. You want to implement a queue using two stacks where enqueue and dequeue operations are both efficient. Which approach below achieves amortized O(1) time per operation?

hard

A. Push elements alternately to stack1 and stack2 on enqueue; pop from stack1 on dequeue

B. Push all elements to stack1 on enqueue; transfer to stack2 only when stack2 is empty during dequeue

C. Push elements to stack1 and stack2 simultaneously on enqueue; pop from stack2 on dequeue

D. Push all elements to stack2 on enqueue; pop from stack1 on dequeue

Solution

1. Step 1: Understand amortized O(1) with two stacks

   Enqueue pushes to stack1 only. Dequeue pops from stack2. Transfer happens only when stack2 is empty, moving all elements from stack1 to stack2.

2. Step 2: Analyze other options

   Alternating pushes or pushing to both stacks simultaneously breaks queue order or wastes operations. Pushing all to stack2 and popping from stack1 is incorrect.

3. Final Answer:

   Push all elements to stack1 on enqueue; transfer to stack2 only when stack2 is empty during dequeue -> Option B

4. Quick Check:

   Lazy transfer on dequeue = amortized O(1) [OK]

Hint: Transfer only when needed during dequeue for efficiency [OK]

Common Mistakes:

• Transferring elements on every enqueue or dequeue
• Pushing to both stacks simultaneously
• Ignoring stack2 emptiness check before transfer