最小栈与栈/队列互转

最小栈（LeetCode 155）

O(1) 获取栈中最小值。

解法：辅助栈

用一个辅助栈 minStack 同步维护当前最小值。

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();

    public void push(int val) {
        stack.push(val);
        int min = minStack.isEmpty() ? val : Math.min(minStack.peek(), val);
        minStack.push(min);
    }

    public void pop() {
        stack.pop();
        minStack.pop();
    }

    public int top() { return stack.peek(); }

    public int getMin() { return minStack.peek(); }
}

要点：辅助栈每次压入的是"到目前为止的最小值"，而不仅是最新最小值。

用栈实现队列（LeetCode 232）

两个栈模拟队列（FIFO）：pushStack（接收新元素）和 popStack（按 FIFO 弹出）。

class MyQueue {
    private Deque<Integer> pushStack = new ArrayDeque<>();
    private Deque<Integer> popStack = new ArrayDeque<>();

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

    public int pop() {
        move();
        return popStack.pop();
    }

    public int peek() {
        move();
        return popStack.peek();
    }

    public boolean empty() { return pushStack.isEmpty() && popStack.isEmpty(); }

    private void move() {
        if (popStack.isEmpty()) {
            while (!pushStack.isEmpty()) popStack.push(pushStack.pop());
        }
    }
}

均摊复杂度：每个元素只被移动一次，pop/peek 均摊 O(1)。

用队列实现栈（LeetCode 225）

用一个队列实现：每次 push 后，将前 n-1 个元素轮转到队尾。

class MyStack {
    private Deque<Integer> queue = new ArrayDeque<>();

    public void push(int x) {
        queue.offer(x);
        for (int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() { return queue.poll(); }

    public int top() { return queue.peek(); }

    public boolean empty() { return queue.isEmpty(); }
}

单调栈（设计角度）

设计浏览器历史（LeetCode 1472）

class BrowserHistory {
    private List<String> history = new ArrayList<>();
    private int cur = -1;

    public BrowserHistory(String homepage) { visit(homepage); }

    public void visit(String url) {
        // 清除 cur 之后的历史
        while (history.size() > cur + 1) history.removeLast();
        history.add(url);
        cur++;
    }

    public String back(int steps) {
        cur = Math.max(0, cur - steps);
        return history.get(cur);
    }

    public String forward(int steps) {
        cur = Math.min(history.size() - 1, cur + steps);
        return history.get(cur);
    }
}

扁平化嵌套列表迭代器（LeetCode 341）

public class NestedIterator implements Iterator<Integer> {
    private Deque<NestedInteger> stack = new ArrayDeque<>();

    public NestedIterator(List<NestedInteger> nestedList) {
        for (int i = nestedList.size() - 1; i >= 0; i--)
            stack.push(nestedList.get(i));
    }

    public Integer next() { return stack.pop().getInteger(); }

    public boolean hasNext() {
        while (!stack.isEmpty() && !stack.peek().isInteger()) {
            NestedInteger top = stack.pop();
            List<NestedInteger> list = top.getList();
            for (int i = list.size() - 1; i >= 0; i--)
                stack.push(list.get(i));
        }
        return !stack.isEmpty();
    }
}