Typorithm · medium

Queue Using Stacks

queue-using-stacksstacks-queuestwo-stacksamortizedfifo-from-lifo

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Queue Using Stacks

Stacks & Queues

Push to an inbox stack; transfer to an outbox stack only when it empties, giving amortized O(1).

JavaScript arrays make great stacks (O(1) push/pop) but shift() for a queue front is O(n).

Two stacks fix this: the inbox holds new items, the outbox serves them in FIFO order.

Transferring inbox to outbox reverses LIFO into FIFO, and is done lazily only when the outbox empties.

Inbox for push, outbox for pop.

Transfer only when outbox is empty.

Amortized O(1) per operation.

class MyQueue {
  constructor() {
    this.inStack = [];
    this.outStack = [];
  }

  push(x) {
    this.inStack.push(x);
  }

  peek() {
    if (this.outStack.length === 0) {
      while (this.inStack.length > 0) {
        this.outStack.push(this.inStack.pop());
      }
    }

    return this.outStack[this.outStack.length - 1];
  }

  pop() {
    this.peek();
    return this.outStack.pop();
  }

  empty() {
    return this.inStack.length === 0 && this.outStack.length === 0;
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Two stacks

An inbox stack and an outbox stack together act as a queue.

this.inStack = [];
    this.outStack = []

2. Enqueue

New items always go onto the inbox stack.

this.inStack.push(x)

3. Reverse on demand

Moving inbox to outbox reverses order, exposing the oldest item.

this.outStack.push(this.inStack.pop())

4. Only when empty

Refill the outbox only when it runs dry.

if (this.outStack.length === 0)

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.