Implementing a queue with stacks, and back again

Building one restricted structure out of another is a standard question because the answer hinges on amortised analysis rather than cleverness.

A queue from two stacks

One stack takes arrivals, the other serves departures. Reversing between them converts LIFO into FIFO.

class QueueFromStacks {
  #inbox = [];
  #outbox = [];

  enqueue(value) { this.#inbox.push(value); }

  dequeue() {
    if (!this.#outbox.length) {
      // Pour everything across — the order flips, which is the point.
      while (this.#inbox.length) this.#outbox.push(this.#inbox.pop());
    }

    return this.#outbox.pop();
  }

  peek() {
    if (!this.#outbox.length) {
      while (this.#inbox.length) this.#outbox.push(this.#inbox.pop());
    }

    return this.#outbox.at(-1);
  }

  get size() { return this.#inbox.length + this.#outbox.length; }
}

A single dequeue can cost O(n) when the transfer happens. Yet each element is moved exactly once from inbox to outbox in its lifetime, so across any sequence of n operations the total work is O(n): amortised O(1) per operation.

The mistake to avoid is transferring on every dequeue. Only refill the outbox when it is empty; otherwise you break both the order and the complexity.

A stack from two queues

The mirror problem, and the trade is unavoidable: one of push or pop must be O(n).

class StackFromQueues {
  #main = [];
  #spare = [];

  // Costly push: rotate the new element to the front.
  push(value) {
    this.#spare.push(value);
    while (this.#main.length) this.#spare.push(this.#main.shift());
    [this.#main, this.#spare] = [this.#spare, this.#main];
  }

  pop() { return this.#main.shift(); }    // O(1)
}

Unlike the queue-from-stacks, there is no amortisation to rescue you here — every push pays O(n). Say which operation you chose to make expensive and why; that choice is the answer.

What this exercise is really testing

Three things: whether you know the ADT contracts precisely, whether you can reason about amortised versus worst-case cost, and whether you notice that the two directions are not symmetric. The last point is the one that separates a memorised answer from an understood one.