Implement Queue using Stacks

Why it belongs on this sheet

This problem is useful because it pushes you to explain amortized complexity clearly, not just code mechanics.

Pattern

Input stack plus output stack

Approach

Push everything into the input stack. Only when the output stack is empty, move all input elements across so their order reverses and queue front becomes available.

Java solution

import java.util.ArrayDeque;
import java.util.Deque;

class MyQueue {
  private final Deque<Integer> in = new ArrayDeque<>();
  private final Deque<Integer> out = new ArrayDeque<>();

  public void push(int x) {
    in.push(x);
  }

  public int pop() {
    moveIfNeeded();
    return out.pop();
  }

  public int peek() {
    moveIfNeeded();
    return out.peek();
  }

  public boolean empty() {
    return in.isEmpty() && out.isEmpty();
  }

  private void moveIfNeeded() {
    if (out.isEmpty()) {
      while (!in.isEmpty()) {
        out.push(in.pop());
      }
    }
  }
}

Complexity

• Amortized time per operation: O(1)
• Space: O(n)

Interview note

Be ready to justify amortized O(1) instead of worst-case O(n) for a single transfer.