185. Implement Queue using Stacks

Use an input stack for pushes and an output stack for pops. Transfer from input to output only when output is empty, reversing the order.

Approach

1. push(x): push to input stack.
2. pop(): if output is empty, transfer all from input to output. Pop from output.
3. peek(): same as pop but don't remove.
4. Amortized O(1) because each element is transferred at most once.

Complexity

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

import java.util.*;

class MyQueue {
    private Stack<Integer> inputStack;
    private Stack<Integer> outputStack;

    public MyQueue() {
        inputStack = new Stack<>();
        outputStack = new Stack<>();
    }

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

    public int pop() {
        transfer();
        return outputStack.pop();
    }

    public int peek() {
        transfer();
        return outputStack.peek();
    }

    public boolean empty() {
        return inputStack.isEmpty() && outputStack.isEmpty();
    }

    private void transfer() {
        if (outputStack.isEmpty()) {
            while (!inputStack.isEmpty()) {
                outputStack.push(inputStack.pop());
            }
        }
    }
}