Approach

Implement Queue using Stacks

Approach

Use two stacks - one for input, one for output - to simulate FIFO behavior.

Algorithm

Push operation: add to input stack
Pop/Peek operations:
- If output stack empty, transfer all from input to output
- Pop/peek from output stack
Empty operation: check both stacks

Complexity

Time: O(1) amortized for all operations
Space: O(n) - two stacks storage

Key Insights

Transferring reverses order twice, achieving FIFO
Lazy transfer optimizes for consecutive pops
Amortized O(1) because each element transferred once

Solution

java

1class MyQueue {
2    private Stack<Integer> input;
3    private Stack<Integer> output;
4    
5    public MyQueue() {
6        input = new Stack<>();
7        output = new Stack<>();
8    }
9    
10    public void push(int x) {
11        input.push(x);
12    }
13    
14    public int pop() {
15        transfer();
16        return output.pop();
17    }
18    
19    public int peek() {
20        transfer();
21        return output.peek();
22    }
23    
24    public boolean empty() {
25        return input.isEmpty() && output.isEmpty();
26    }
27    
28    private void transfer() {
29        if (output.isEmpty()) {
30            while (!input.isEmpty()) {
31                output.push(input.pop());
32            }
33        }
34    }
35}