Solving Implement Stack using Queues in JavaScript: Step-by-Step Guide

The "Implement Stack using Queues" problem is a classic data structure challenge that frequently appears in coding interviews and algorithm courses. At its core, it asks you to build a Last-In-First-Out (LIFO) stack using only First-In-First-Out (FIFO) queue operations. While it may seem counterintuitive at first, this exercise deepens your understanding of how abstract data types can be simulated using other primitives, and it sharpens your ability to reason about time and space complexity trade-offs.

What Is a Stack and What Is a Queue?

Before diving into the implementation, it is important to revisit the two foundational data structures involved. 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 where you can only add or remove from the top. A queue, on the other hand, follows the FIFO principle: the first element added is the first one removed, much like a line of people waiting at a ticket counter.

A stack typically supports these operations:

push(x) — add an element to the top
pop() — remove and return the top element
top() — return the top element without removing it
empty() — check whether the stack is empty

A queue typically supports these operations:

enqueue(x) or push(x) — add an element to the back
dequeue() or pop() — remove and return the front element
peek() or front() — return the front element without removing it
empty() — check whether the queue is empty

Why This Problem Matters

You might wonder why anyone would implement a stack using queues when native arrays in JavaScript can do both jobs effortlessly. The answer lies in what the problem teaches rather than what it produces. This challenge forces you to think about how to reverse ordering using only FIFO operations. It also exposes you to the concept of amortized complexity, where some operations may be expensive occasionally but cheap on average.

In real-world systems, you sometimes work with constrained environments where only certain primitives are available. For example, message brokers, task schedulers, and certain embedded systems may expose only queue-like interfaces. Understanding how to layer abstractions on top of limited primitives is a valuable engineering skill. Additionally, this problem is a common interview question because it tests both data structure knowledge and algorithmic creativity.

Approach 1: Making Push Costly

The first strategy is to make the push operation expensive while keeping pop and top cheap. The idea is to maintain the queue such that the most recently pushed element is always at the front. When you push a new element, you add it to the queue and then rotate all the existing elements behind it by dequeuing and re-enqueuing them.

Here is how it works step by step:

Enqueue the new element to the queue
Dequeue and re-enqueue all elements that were already in the queue before the new element
This places the new element at the front, simulating the top of a stack

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

  push(x) {
    const sizeBeforePush = this.queue.length;
    this.queue.push(x);

    // Rotate all previous elements behind the newly added one
    for (let i = 0; i < sizeBeforePush; i++) {
      this.queue.push(this.queue.shift());
    }
  }

  pop() {
    if (this.empty()) {
      throw new Error("Stack is empty");
    }
    return this.queue.shift();
  }

  top() {
    if (this.empty()) {
      throw new Error("Stack is empty");
    }
    return this.queue[0];
  }

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

// Example usage
const stack = new MyStack();
stack.push(1);
stack.push(2);
stack.push(3);
console.log(stack.top()); // 3
console.log(stack.pop()); // 3
console.log(stack.pop()); // 2
console.log(stack.empty()); // false
console.log(stack.pop()); // 1
console.log(stack.empty()); // true

In this approach, push runs in O(n) time because we rotate all existing elements, while pop, top, and empty all run in O(1) time. This is a good choice when your workload is dominated by pop and top operations.

Approach 2: Making Pop Costly

The second strategy flips the trade-off. Here, push is cheap and runs in O(1), while pop and top become expensive, running in O(n). This approach uses two queues. The main queue holds the elements in insertion order, and when you need to pop, you transfer all but the last element into a secondary queue, then remove that last element.

class MyStackTwoQueues {
  constructor() {
    this.q1 = [];
    this.q2 = [];
  }

  push(x) {
    // Always push to the queue that currently holds elements
    this.q1.push(x);
  }

  pop() {
    if (this.empty()) {
      throw new Error("Stack is empty");
    }

    // Move all elements except the last one to q2
    while (this.q1.length > 1) {
      this.q2.push(this.q1.shift());
    }

    // The last remaining element is the top of the stack
    const topElement = this.q1.shift();

    // Swap the queues so q1 always holds the active elements
    const temp = this.q1;
    this.q1 = this.q2;
    this.q2 = temp;

    return topElement;
  }

  top() {
    if (this.empty()) {
      throw new Error("Stack is empty");
    }

    // Move all elements except the last one to q2
    while (this.q1.length > 1) {
      this.q2.push(this.q1.shift());
    }

    // Peek at the last element without removing it permanently
    const topElement = this.q1[0];
    this.q2.push(this.q1.shift());

    // Swap the queues
    const temp = this.q1;
    this.q1 = this.q2;
    this.q2 = temp;

    return topElement;
  }

  empty() {
    return this.q1.length === 0 && this.q2.length === 0;
  }
}

// Example usage
const stack2 = new MyStackTwoQueues();
stack2.push(10);
stack2.push(20);
stack2.push(30);
console.log(stack2.top()); // 30
console.log(stack2.pop()); // 30
console.log(stack2.pop()); // 20
console.log(stack2.pop()); // 10
console.log(stack2.empty()); // true

This two-queue approach is conceptually clearer for some developers because it explicitly separates the "working" queue from the "transfer" queue. However, the constant swapping of references and the O(n) pop and top operations make it less efficient for read-heavy workloads.

Approach 3: Single Queue with Lazy Rotation

A subtle variation of the first approach avoids rotating on every push. Instead, you can defer the rotation until a pop or top is requested. This amortizes the cost differently and can be useful in scenarios where pushes and pops come in bursts. However, this approach is more complex to implement correctly and is rarely the expected solution in interviews.

class MyStackLazy {
  constructor() {
    this.queue = [];
    this.reversed = false;
  }

  push(x) {
    if (this.reversed) {
      // If currently reversed, rotate back to normal order first
      const front = this.queue.shift();
      this.queue.push(front);
      this.reversed = false;
    }
    this.queue.push(x);
  }

  pop() {
    if (this.empty()) {
      throw new Error("Stack is empty");
    }
    if (!this.reversed) {
      // Rotate so the last pushed element is at the front
      for (let i = 0; i < this.queue.length - 1; i++) {
        this.queue.push(this.queue.shift());
      }
      this.reversed = true;
    }
    return this.queue.shift();
  }

  top() {
    if (this.empty()) {
      throw new Error("Stack is empty");
    }
    if (!this.reversed) {
      for (let i = 0; i < this.queue.length - 1; i++) {
        this.queue.push(this.queue.shift());
      }
      this.reversed = true;
    }
    const topElement = this.queue[0];
    return topElement;
  }

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

While interesting, this lazy approach adds state management complexity and is harder to reason about. For most practical purposes, the first approach is preferred.

How to Use the Stack in Practice

Once you have implemented the stack, you can use it anywhere a standard stack would be useful. Common applications include evaluating postfix expressions, checking for balanced parentheses, implementing undo functionality, and performing depth-first traversal of graphs. Here is a small example that uses our stack to check for balanced parentheses:

function isBalanced(expression) {
  const stack = new MyStack();
  const matching = {
    ')': '(',
    ']': '[',
    '}': '{'
  };

  for (const char of expression) {
    if (char === '(' || char === '[' || char === '{') {
      stack.push(char);
    } else if (char === ')' || char === ']' || char === '}') {
      if (stack.empty() || stack.pop() !== matching[char]) {
        return false;
      }
    }
  }

  return stack.empty();
}

console.log(isBalanced("(a + b) * [c - {d / e}]")); // true
console.log(isBalanced("(a + b]")); // false
console.log(isBalanced("((())")); // false

This example demonstrates that our queue-based stack behaves identically to a native stack for real algorithmic tasks.

Best Practices

Choose the right trade-off: If your application pushes frequently and pops rarely, use the approach where pop is costly. If pops and tops dominate, use the approach where push is costly.
Handle edge cases explicitly: Always check for empty stacks before calling pop or top. Throwing a descriptive error is better than returning undefined silently.
Avoid premature optimization: The single-queue approach with costly push is simple and sufficient for most interview and educational contexts. Do not reach for the lazy rotation approach unless you have a measured performance need.
Use descriptive variable names: Names like q1 and q2 are acceptable in short snippets, but in production code, prefer names like mainQueue and helperQueue for clarity.
Document complexity: Add comments noting the time complexity of each method so future maintainers understand the trade-offs you made.
Test thoroughly: Write tests covering empty stacks, single-element stacks, repeated pushes and pops, and interleaved operations to ensure correctness.

Complexity Summary

For the single-queue approach where push is costly, the complexities are as follows:

push(x): O(n) time, O(1) extra space
pop(): O(1) time, O(1) extra space
top(): O(1) time, O(1) extra space
empty(): O(1) time, O(1) extra space

For the two-queue approach where pop is costly, the complexities are:

push(x): O(1) time, O(1) extra space
pop(): O(n) time, O(n) extra space
top(): O(n) time, O(n) extra space
empty(): O(1) time, O(1) extra space

Overall space complexity for both approaches is O(n), where n is the number of elements stored.

Conclusion

Implementing a stack using queues is a deceptively simple problem that reveals deep truths about data structure abstraction and algorithmic trade-offs. By choosing where to absorb the cost of reordering elements, you can tailor the implementation to your specific workload. The single-queue approach with a costly push is the most common and interview-friendly solution, offering O(1) pop and top operations at the expense of an O(n) push. The two-queue approach with a costly pop provides the opposite trade-off and can be preferable in write-heavy scenarios. Whichever approach you choose, the key takeaway is that understanding the underlying principles of FIFO and LIFO ordering empowers you to build any abstraction on top of any primitive, a skill that extends far beyond this single problem into the broader practice of software engineering.