Skip to main content

15. Implement Queue using Stacks

easyAsked at Wix

Build a FIFO queue from two LIFO stacks — Wix uses this to check your grasp of amortised cost, which is the same reasoning behind batched DOM mutation queues that keep the drag-drop editor smooth.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Implement a first-in-first-out queue using only two stacks. The queue should support push (add to back), pop (remove from front), peek (get front element), and empty (check if empty). You must use only standard stack operations: push to top, pop from top, peek top, size, and isEmpty.

Constraints

  • 1 <= x <= 9
  • At most 100 calls will be made to push, pop, peek, and empty
  • All pop and peek calls are made on non-empty queues

Examples

Example 1

Input
push(1); push(2); peek(); pop(); empty();
Output
[1, 1, false]

Explanation: peek returns front element 1, pop removes and returns 1, queue still has 2 so not empty

Example 2

Input
push(5); pop(); empty();
Output
[5, true]

Approaches

1. Two stacks — eager transfer on push

Keep one stack in queue order by reversing into a second stack on every push. Push is O(n), pop/peek are O(1).

Time
O(n) push, O(1) pop/peek
Space
O(n)
class MyQueue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
  }
  push(x) {
    while (this.outbox.length) {
      this.inbox.push(this.outbox.pop());
    }
    this.inbox.push(x);
    while (this.inbox.length) {
      this.outbox.push(this.inbox.pop());
    }
  }
  pop() {
    return this.outbox.pop();
  }
  peek() {
    return this.outbox[this.outbox.length - 1];
  }
  empty() {
    return this.outbox.length === 0;
  }
}

Tradeoff:

2. Two stacks — lazy transfer on pop

Push always goes to inbox. Pop transfers inbox to outbox only when outbox is empty, giving O(1) amortised pop because each element crosses once.

Time
O(1) amortised all operations
Space
O(n)
class MyQueue {
  constructor() {
    this.inbox = [];
    this.outbox = [];
  }
  push(x) {
    this.inbox.push(x);
  }
  _transfer() {
    if (this.outbox.length === 0) {
      while (this.inbox.length) {
        this.outbox.push(this.inbox.pop());
      }
    }
  }
  pop() {
    this._transfer();
    return this.outbox.pop();
  }
  peek() {
    this._transfer();
    return this.outbox[this.outbox.length - 1];
  }
  empty() {
    return this.inbox.length === 0 && this.outbox.length === 0;
  }
}

Tradeoff:

Wix-specific tips

Wix cares most about the amortised analysis: say 'each element crosses from inbox to outbox exactly once across its lifetime' and you've shown the same reasoning the rendering team uses to justify batching expensive layout passes.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Implement Queue using Stacks and other Wix interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →