Implement Queue using Stacks | Problems

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

Example:

push(1), push(2), peek() -> 1, pop() -> 1, empty() -> false

Sample Input

—

Sample Output

—

Constraints

1 <= x <= 9
At most 100 calls to push, pop, peek, empty

Topics

Stack&Queue

Approach: Two Stacks (Amortized)

Use an input stack for pushes and an output stack for pops. When the output stack is empty and a pop/peek is needed, transfer all elements from the input stack to the output stack, reversing the order. This gives amortized O(1) per operation.

function implementQueueUsingStacks() {
  const inStack = [], outStack = [];
  return {
    push(x) { inStack.push(x); },
    pop() {
      if (!outStack.length) while (inStack.length) outStack.push(inStack.pop());
      return outStack.pop();
    },
    peek() {
      if (!outStack.length) while (inStack.length) outStack.push(inStack.pop());
      return outStack[outStack.length - 1];
    },
    empty() { return !inStack.length && !outStack.length; }
  };
}

Time Complexity: Amortized O(1) per operation

Space Complexity: O(n)

Saved in this browser only. Private to you.