栈基础应用（括号匹配 · 逆波兰表达式 · 简化路径）

有效的括号（LeetCode 20）

boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') stack.push(c);
        else {
            if (stack.isEmpty()) return false;
            char top = stack.pop();
            if (c == ')' && top != '(') return false;
            if (c == ']' && top != '[') return false;
            if (c == '}' && top != '{') return false;
        }
    }
    return stack.isEmpty();
}

最长有效括号（LeetCode 32）

栈存下标，用 -1 作为哨兵：

int longestValidParentheses(String s) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);  // 哨兵
    int max = 0;
    for (int i = 0; i < s.length(); i++) {
        if (s.charAt(i) == '(') stack.push(i);
        else {
            stack.pop();
            if (stack.isEmpty()) stack.push(i);  // 新哨兵
            else max = Math.max(max, i - stack.peek());
        }
    }
    return max;
}

逆波兰表达式求值（LeetCode 150）

int evalRPN(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String t : tokens) {
        switch (t) {
            case "+" -> stack.push(stack.pop() + stack.pop());
            case "-" -> { int b = stack.pop(), a = stack.pop(); stack.push(a - b); }
            case "*" -> stack.push(stack.pop() * stack.pop());
            case "/" -> { int b = stack.pop(), a = stack.pop(); stack.push(a / b); }
            default  -> stack.push(Integer.parseInt(t));
        }
    }
    return stack.pop();
}

简化路径（LeetCode 71）

String simplifyPath(String path) {
    Deque<String> stack = new ArrayDeque<>();
    for (String part : path.split("/")) {
        if (part.equals("..")) { if (!stack.isEmpty()) stack.pop(); }
        else if (!part.isEmpty() && !part.equals(".")) stack.push(part);
    }
    StringBuilder sb = new StringBuilder();
    for (String s : stack) sb.insert(0, "/" + s);
    return sb.length() == 0 ? "/" : sb.toString();
}

最小栈（LeetCode 155）

辅助栈同步维护最小值：

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

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

用栈实现队列 & 用队列实现栈

用两个栈实现队列（LeetCode 232）

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

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

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

    public int peek() {
        if (out.isEmpty()) while (!in.isEmpty()) out.push(in.pop());
        return out.peek();
    }

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

关键：惰性转移（只在 out 为空时才把 in 的元素转入），均摊 O(1)。

用队列实现栈（LeetCode 225）

class MyStack {
    private final Queue<Integer> queue = new LinkedList<>();

    public void push(int x) {
        queue.offer(x);
        // 将新元素转到队头（旋转 size-1 次）
        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(); }
}