Leetcode - Implement Queue Using Stacks Solution

Implementing a queue with two stacks works because transferring every item to a second stack reverses the order. One stack accepts new items, and the other exposes the oldest item when a read is needed.

The queue contract

I needed to implement a queue with these operations:

• push(x): Add element to the end
• pop(): Remove element from the front
• peek(): Look at front element without removing
• empty(): Check if queue is empty

But I could only use stack operations: push, pop, peek, and checking if empty.

I was confused at first because a stack exposes only its top item. Moving all items from an inbox stack to an outbox stack reverses their order, putting the oldest queue item on top. A second transfer later restores the same relationship for the remaining items.

Transfer rule and implementation

The inbox receives every new item. A pop or peek checks the outbox first. If the outbox is empty, the implementation transfers all inbox items to it. The front of the queue is then at the top of the outbox.

class MyQueue {
  constructor() {
    this.inbox = []; // Stack for incoming elements
    this.outbox = []; // Stack for outgoing elements
  }

  push(x) {
    // Just push to inbox - simple!
    this.inbox.push(x);
  }

  pop() {
    // Make sure outbox has elements
    this.moveInboxToOutbox();
    // Pop from outbox (this is the front of the queue)
    return this.outbox.pop();
  }

  peek() {
    // Make sure outbox has elements
    this.moveInboxToOutbox();
    // Look at top of outbox without removing
    return this.outbox[this.outbox.length - 1];
  }

  empty() {
    // Queue is empty if both stacks are empty
    return this.inbox.length === 0 && this.outbox.length === 0;
  }

  // Helper: transfer inbox to outbox when outbox is empty
  moveInboxToOutbox() {
    if (this.outbox.length === 0) {
      // Transfer all elements from inbox to outbox
      // This reverses the order, so first-in becomes first-out!
      while (this.inbox.length > 0) {
        this.outbox.push(this.inbox.pop());
      }
    }
  }
}

State changes and amortized cost

For the sequence below, the stacks change as follows:

1. push(1): inbox = [1], outbox = []
2. push(2): inbox = [1, 2], outbox = []
3. push(3): inbox = [1, 2, 3], outbox = []
4. pop(): Transfer inbox to outbox → outbox = [3, 2, 1], inbox = []
   • Pop from outbox → returns 1 (correct! first in, first out)
5. push(4): inbox = [4], outbox = [3, 2]
6. pop(): outbox not empty, so pop → returns 2 (correct!)

The transfer happens only when the outbox is empty. push is O(1). A single pop can move O(n) items. But the implementation transfers each item from the inbox to the outbox at most once before removal. Thus, pop and peek each have an amortized cost of O(1). Both stacks together use O(n) space.

Why the lazy transfer works

This implementation shows how one data structure can simulate another when the operations are rearranged. The important detail is delaying the transfer until the outbox is empty, rather than moving items on every queue operation.

Two stacks simulate FIFO order by separating writes from reads. The inbox preserves insertion order while the outbox reverses it for removal, and the lazy transfer keeps the amortized operation cost constant.