Coding Interview Questions | Implement a Queue Using Two Stacks

December 22nd, 2023

Introduction:

This summary will talk about my solution to the implementing a FIFO queue using two stacks coding problem as seen on leetcode here.

Solution:

class MyQueue {
  private enqueueStack: number[];
  private dequeueStack: number[];

  constructor() {
    this.enqueueStack = [];
    this.dequeueStack = [];
  }

  push(x: number): void {
    this.enqueueStack.push(x);
  }

  pop(): number {
    if (this.dequeueStack.length === 0) {
      // Amortize the cost of popping by
      // populating the dequeueStack when it is empty
      // using the pop operation on enqueueStack
      while (this.enqueueStack.length > 0) {
        const element = this.enqueueStack.pop()!;
        this.dequeueStack.push(element);
      }
    }

    return this.dequeueStack.pop() ?? 0;
  }

  peek(): number {
    if (this.dequeueStack.length) {
      return this.dequeueStack[this.dequeueStack.length - 1];
    }

    if (this.enqueueStack.length) {
      return this.enqueueStack[0];
    }

    return 0;
  }

  empty(): boolean {
    return this.enqueueStack.length === 0 && this.dequeueStack.length === 0;
  }
}

Overview

Using two stacks to implement a queue is mainly done to optimize the performance of certain operations. The idea is to simulate the behavior of a queue, where elements are added to one end (enqueue) and removed from the other end (dequeue), using two stacks.

Here are a couple of reasons why you might want to use two stacks for this implementation:

1. Optimized Dequeue Operation:

   • When you use a single stack to simulate a queue, dequeuing an element (removing from the front) becomes an O(n) operation. This is because you need to pop all elements from the original stack, push them onto a temporary stack, pop the top element (which is the front of the queue), and then push the remaining elements back.
   • With two stacks, you can optimize the dequeue operation. When you want to dequeue an element, you can check if the second stack (used for dequeueing) is not empty. If it’s not empty, you can directly pop from it. If it’s empty, you can transfer all elements from the first stack (used for enqueuing) to the second stack. This way, the dequeue operation becomes amortized O(1).

2. Simplified Implementation:

   • Using two stacks can simplify the implementation logic. Each stack has a clear purpose: one for enqueueing, and the other for dequeueing.