Implement Queue Using Stacks

Try It Yourself

Use the editor below to process queue operations while relying only on stack behavior internally. Separate newly pushed values from values ready to leave.

Submit your implementation when it passes the examples. Interleaved pushes, peeks, pops, and empty checks must preserve FIFO order.

Implement Queue Using Stacks

easyQueue · Stack · Design30 minLC 232

Problem

Process queue operations using only stack-style push and pop behavior internally.

Return one output per operation. Constructor and push produce null; pop and peek return values; empty returns a boolean.

Example 1:

Input: operations = ["MyQueue", "push", "push", "peek", "pop", "empty"], values = [[], [1], [2], [], [], []]

Output: [null, null, null, 1, 1, false]

Example 2:

Input: operations = ["MyQueue", "push", "pop", "empty"], values = [[], [7], [], []]

Output: [null, null, 7, true]

Constraints

At most 100 operations are performed.
pop and peek are called only on a non-empty queue.

0 attempts

Solution

Push new values onto an input stack. When a front value is needed and the output stack is empty, move every input value to the output stack.

That reversal places the oldest value on top. Reuse the output stack until it becomes empty instead of transferring values for every operation.

function runQueueUsingStacks(operations, values) {
  class MyQueue {
    constructor() {
      this.input = [];
      this.output = [];
    }

    moveIfNeeded() {
      if (this.output.length > 0) return;

      while (this.input.length > 0) {
        this.output.push(this.input.pop());
      }
    }

    push(value) {
      this.input.push(value);
    }

    pop() {
      this.moveIfNeeded();
      return this.output.pop();
    }

    peek() {
      this.moveIfNeeded();
      return this.output[this.output.length - 1];
    }

    empty() {
      return this.input.length === 0 && this.output.length === 0;
    }
  }

  let queue;
  const output = [];

  for (let index = 0; index < operations.length; index++) {
    const operation = operations[index];

    if (operation === "MyQueue") {
      queue = new MyQueue();
      output.push(null);
    } else if (operation === "push") {
      queue.push(values[index][0]);
      output.push(null);
    } else {
      output.push(queue[operation]());
    }
  }

  return output;
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	Across n operations, each value moves between stacks at most once and is popped once.
Auxiliary space	`O(n)`	The two stacks together store all queued values.