Solving Implement Queue using Stacks in JavaScript: Step-by-Step Guide

Introduction to Implementing Queue Using Stacks

The "Implement Queue using Stacks" problem is a classic algorithmic challenge that frequently appears in coding interviews and computer science curricula. At its core, the problem asks you to simulate the behavior of a queue — a First-In-First-Out (FIFO) data structure — using only two stacks, which are inherently Last-In-First-Out (LIFO) data structures. This exercise forces developers to think deeply about data structure manipulation, trade-offs between time complexity, and the fundamental properties of abstract data types.

What Is a Queue?

A queue is a linear data structure that follows the FIFO principle. The first element added to the queue is the first one removed. Think of it like a line at a coffee shop: the first person to arrive is the first person served. Queues support two primary operations:

enqueue — add an element to the back of the queue
dequeue — remove and return the element at the front of the queue

What Is a Stack?

A stack is a linear data structure that follows the LIFO principle. The last element added is the first one removed. Think of a stack of plates: you add plates to the top and remove plates from the top. Stacks support two primary operations:

push — add an element to the top of the stack
pop — remove and return the element at the top of the stack

Why This Problem Matters

Understanding how to implement a queue using stacks is valuable for several reasons. First, it deepens your understanding of abstract data types and how they can be built on top of one another. Second, it teaches you about amortized time complexity, a concept crucial for evaluating the real-world performance of algorithms. Third, it is a common interview question at major tech companies because it reveals how candidates reason about constraints and trade-offs.

In real-world applications, you may encounter scenarios where you only have access to stack-like primitives — for example, when working with certain recursive systems, call stacks, or constrained environments — and you need queue-like behavior. Knowing how to bridge that gap is a practical skill.

The Core Idea: Two Stacks

The key insight is that by using two stacks, you can reverse the order of elements. When you push elements onto a stack and then pop them all into another stack, the order reverses. Since a queue is essentially a reversed stack in terms of output order, this reversal is exactly what we need.

We will call our two stacks stackIn and stackOut. The stackIn stack receives all incoming elements during enqueue operations. The stackOut stack provides elements during dequeue operations. When stackOut is empty and we need to dequeue, we transfer all elements from stackIn to stackOut, which reverses their order and makes the oldest element available at the top.

Approach 1: Making Enqueue Costly

In this approach, every enqueue operation ensures that the newest element is at the bottom of stackIn, preserving queue order. This makes enqueue O(n) but keeps dequeue O(1).

Implementation

class QueueUsingStacks {
  constructor() {
    this.stackIn = [];
    this.stackOut = [];
  }

  enqueue(x) {
    // Move all elements from stackIn to stackOut
    while (this.stackIn.length > 0) {
      this.stackOut.push(this.stackIn.pop());
    }

    // Push the new element onto stackIn
    this.stackIn.push(x);

    // Move everything back from stackOut to stackIn
    while (this.stackOut.length > 0) {
      this.stackIn.push(this.stackOut.pop());
    }
  }

  dequeue() {
    if (this.stackIn.length === 0) {
      return null; // or throw an error
    }
    return this.stackIn.pop();
  }

  peek() {
    if (this.stackIn.length === 0) {
      return null;
    }
    return this.stackIn[this.stackIn.length - 1];
  }

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

// Usage example
const q = new QueueUsingStacks();
q.enqueue(10);
q.enqueue(20);
q.enqueue(30);
console.log(q.dequeue()); // 10
console.log(q.dequeue()); // 20
console.log(q.peek());    // 30

This approach works but is inefficient for write-heavy workloads because every enqueue requires moving all existing elements twice.

Approach 2: Making Dequeue Costly (Amortized O(1))

The second approach is generally preferred. Here, enqueue is always O(1) — we simply push onto stackIn. The dequeue operation pops from stackOut if it has elements, or transfers everything from stackIn to stackOut first. While a single dequeue can be O(n), the amortized cost across many operations is O(1).

Implementation

class MyQueue {
  constructor() {
    this.stackIn = [];
    this.stackOut = [];
  }

  // Push element x to the back of queue — O(1)
  enqueue(x) {
    this.stackIn.push(x);
  }

  // Remove and return the front element — amortized O(1)
  dequeue() {
    this._transferIfNeeded();
    if (this.stackOut.length === 0) {
      throw new Error("Queue is empty");
    }
    return this.stackOut.pop();
  }

  // Return the front element without removing it — amortized O(1)
  peek() {
    this._transferIfNeeded();
    if (this.stackOut.length === 0) {
      throw new Error("Queue is empty");
    }
    return this.stackOut[this.stackOut.length - 1];
  }

  // Check if the queue is empty — O(1)
  isEmpty() {
    return this.stackIn.length === 0 && this.stackOut.length === 0;
  }

  // Internal helper: move elements from stackIn to stackOut if needed
  _transferIfNeeded() {
    if (this.stackOut.length === 0) {
      while (this.stackIn.length > 0) {
        this.stackOut.push(this.stackIn.pop());
      }
    }
  }
}

// Usage example
const queue = new MyQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.peek());    // 1
console.log(queue.dequeue()); // 1
console.log(queue.dequeue()); // 2
queue.enqueue(4);
console.log(queue.dequeue()); // 3
console.log(queue.dequeue()); // 4
console.log(queue.isEmpty()); // true

Understanding Amortized O(1) Complexity

The amortized analysis is what makes Approach 2 powerful. Consider what happens when you enqueue n elements and then dequeue them all. Each element is pushed onto stackIn once (O(1)), then popped from stackIn and pushed onto stackOut (O(1) each), then popped from stackOut (O(1)). That is a constant number of operations per element, so the total work is O(n) for n operations, giving an amortized cost of O(1) per operation.

The worst case for a single dequeue is O(n) — when stackOut is empty and stackIn holds all n elements. However, this expensive operation only happens once for every n enqueues, so the cost is spread out.

Best Practices

Prefer the amortized approach: Approach 2 is almost always the better choice because it optimizes for the common case and provides excellent average performance.
Keep transfer logic in a helper method: Extracting the transfer logic into a private helper like _transferIfNeeded keeps your dequeue and peek methods clean and DRY.
Handle empty queue cases explicitly: Decide whether to return null, undefined, or throw an error when dequeuing from an empty queue. Throwing an error is often clearer for catching bugs.
Do not transfer back: A common mistake is transferring elements back from stackOut to stackIn after each dequeue. This is unnecessary and destroys the amortized benefit. Leave elements in stackOut until it is empty.
Use arrays as stacks carefully: In JavaScript, Array.prototype.push and Array.prototype.pop are O(1) operations, making arrays ideal stack implementations. Avoid shift and unshift, which are O(n).
Test edge cases: Always test with an empty queue, a single element, interleaved enqueue and dequeue operations, and large inputs to verify correctness and performance.

Common Mistakes to Avoid

One frequent error is transferring elements from stackIn to stackOut on every operation. This defeats the purpose of the two-stack design and makes every operation O(n). The transfer should only happen when stackOut is empty.

Another mistake is forgetting to check whether stackOut already has elements before transferring. If you blindly transfer while stackOut still contains items, you will reverse the order incorrectly and break the FIFO property.

Putting It All Together: A Complete Example

class MyQueue {
  constructor() {
    this.stackIn = [];
    this.stackOut = [];
  }

  enqueue(x) {
    this.stackIn.push(x);
  }

  dequeue() {
    this._transferIfNeeded();
    if (this.stackOut.length === 0) {
      throw new Error("Cannot dequeue from an empty queue");
    }
    return this.stackOut.pop();
  }

  peek() {
    this._transferIfNeeded();
    if (this.stackOut.length === 0) {
      throw new Error("Cannot peek an empty queue");
    }
    return this.stackOut[this.stackOut.length - 1];
  }

  isEmpty() {
    return this.stackIn.length === 0 && this.stackOut.length === 0;
  }

  size() {
    return this.stackIn.length + this.stackOut.length;
  }

  _transferIfNeeded() {
    if (this.stackOut.length === 0) {
      while (this.stackIn.length > 0) {
        this.stackOut.push(this.stackIn.pop());
      }
    }
  }
}

// Demonstration
const myQueue = new MyQueue();
console.log("Is empty?", myQueue.isEmpty()); // true

myQueue.enqueue("apple");
myQueue.enqueue("banana");
myQueue.enqueue("cherry");

console.log("Size:", myQueue.size());        // 3
console.log("Front:", myQueue.peek());       // apple
console.log("Dequeue:", myQueue.dequeue());  // apple

myQueue.enqueue("date");

console.log("Dequeue:", myQueue.dequeue());  // banana
console.log("Dequeue:", myQueue.dequeue());  // cherry
console.log("Dequeue:", myQueue.dequeue());  // date
console.log("Is empty?", myQueue.isEmpty()); // true

Conclusion

Implementing a queue using two stacks is a deceptively simple problem that reveals deep lessons about data structure design, algorithmic trade-offs, and amortized complexity analysis. By using an input stack for enqueues and an output stack for dequeues, with lazy transfers between them, you achieve amortized O(1) performance for all operations while respecting the FIFO contract of a queue. Mastering this pattern not only prepares you for technical interviews but also strengthens your ability to reason about how fundamental data structures relate to one another, a skill that pays dividends across all areas of software engineering.