跳到主要内容

栈

栈是一种基础且重要的线性数据结构，它的核心特征是"后进先出"（LIFO, Last In First Out）。这种特性使得栈在许多场景中都有独特的作用，比如函数调用管理、表达式求值、括号匹配等。

理解栈的本质​

想象一摞盘子：你只能从最上面放盘子（push），也只能从最上面取盘子（pop）。最后放上去的盘子，最先被取走——这就是栈的工作方式。

栈只允许在一端（称为栈顶，Top）进行操作：

  • 入栈（Push）：将元素放到栈顶
  • 出栈（Pop）：移除并返回栈顶元素
  • 查看栈顶（Peek）：返回栈顶元素但不移除

由于只能在栈顶操作，所有基本操作的时间复杂度都是 O(1)O(1)。

栈与数组的对比​

特性数组栈
访问方式随机访问，O(1)只能访问栈顶
插入/删除位置任意位置只能在栈顶
时间复杂度中间插入/删除 O(n)所有操作 O(1)
适用场景需要随机访问需要追踪"最近"元素

栈的实现​

数组实现​

数组实现栈需要维护一个指针记录栈顶位置，并处理容量问题。

public class ArrayStack<E> {
    private E[] data;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public ArrayStack() {
        this.data = (E[]) new Object[DEFAULT_CAPACITY];
        this.size = 0;
    }
    
    // 入栈 - 均摊 O(1)
    public void push(E element) {
        if (size == data.length) {
            resize(data.length * 2);
        }
        data[size++] = element;
    }
    
    // 出栈 - 均摊 O(1)
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        E element = data[--size];
        data[size] = null;  // 帮助垃圾回收
        
        // 缩容：当元素数量小于容量的 1/4 时
        if (size > 0 && size == data.length / 4) {
            resize(data.length / 2);
        }
        return element;
    }
    
    // 查看栈顶 - O(1)
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return data[size - 1];
    }
    
    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
    
    private void resize(int newCapacity) {
        @SuppressWarnings("unchecked")
        E[] newData = (E[]) new Object[newCapacity];
        System.arraycopy(data, 0, newData, 0, size);
        data = newData;
    }
}

为什么缩容阈值是 1/4 而不是 1/2？

如果在 1/2 处缩容，可能会出现"复杂度震荡"：反复在边界处进行 pop 和 push，每次都触发扩容/缩容。使用 1/4 阈值可以避免这个问题。

链表实现​

链表实现更加简洁，不需要考虑容量问题。

public class LinkedStack<E> {
    private static class Node<E> {
        E val;
        Node<E> next;
        Node(E val) { this.val = val; }
    }
    
    private Node<E> top;
    private int size;
    
    // 入栈 - O(1)
    public void push(E element) {
        Node<E> newNode = new Node<>(element);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    // 出栈 - O(1)
    public E pop() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        E element = top.val;
        top = top.next;
        size--;
        return element;
    }
    
    // 查看栈顶 - O(1)
    public E peek() {
        if (isEmpty()) {
            throw new IllegalStateException("Stack is empty");
        }
        return top.val;
    }
    
    public boolean isEmpty() { return size == 0; }
    public int size() { return size; }
}

实现方式对比​

特性数组实现链表实现
时间复杂度均摊 O(1)严格 O(1)
空间效率可能有未使用空间每个节点有额外指针开销
扩容开销偶尔需要复制数组无
缓存友好是（内存连续）否

实际应用中，数组实现通常更高效，因为内存连续带来的缓存优势。

栈的经典应用​

括号匹配​

判断一个字符串中的括号是否匹配是栈最经典的应用。

问题分析：遇到左括号时，我们期望后续能遇到对应的右括号。这个"期望"可以用栈来记录：遇到左括号入栈，遇到右括号时检查栈顶是否匹配。

public boolean isValid(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    Map<Character, Character> pairs = Map.of(')', '(', ']', '[', '}', '{');
    
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') {
            stack.push(c);
        } else {
            // 右括号：检查栈顶是否匹配
            if (stack.isEmpty() || stack.pop() != pairs.get(c)) {
                return false;
            }
        }
    }
    // 所有括号都匹配后，栈应该为空
    return stack.isEmpty();
}

为什么用栈？ 因为括号匹配遵循"最近匹配原则"：一个右括号应该匹配离它最近的、尚未匹配的左括号。栈正好能追踪"最近的未匹配元素"。

表达式求值​

计算机处理数学表达式需要解决两个问题：运算符优先级和括号。人类习惯的"中缀表达式"（如 3 + 4 * 2）对计算机来说不够直观。更友好的形式是"后缀表达式"（逆波兰表达式）。

三种表达式形式：

形式示例特点
中缀A + B * C人类习惯，需处理优先级
后缀A B C * +计算机友好，无需括号
前缀+ A * B C波兰表示法，较少使用

中缀转后缀：使用栈保存运算符，遇到更高优先级的运算符时，先弹出栈中的运算符。

public String infixToPostfix(String expr) {
    Map<Character, Integer> precedence = Map.of('+', 1, '-', 1, '*', 2, '/', 2);
    Deque<Character> stack = new ArrayDeque<>();
    StringBuilder result = new StringBuilder();
    
    for (char c : expr.toCharArray()) {
        if (Character.isLetterOrDigit(c)) {
            result.append(c);
        } else if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            // 弹出直到遇到左括号
            while (!stack.isEmpty() && stack.peek() != '(') {
                result.append(stack.pop());
            }
            stack.pop(); // 弹出左括号
        } else {
            // 运算符：弹出栈中优先级 >= 当前的运算符
            while (!stack.isEmpty() && stack.peek() != '(' &&
                   precedence.getOrDefault(stack.peek(), 0) >= precedence.get(c)) {
                result.append(stack.pop());
            }
            stack.push(c);
        }
    }
    // 弹出剩余运算符
    while (!stack.isEmpty()) {
        result.append(stack.pop());
    }
    return result.toString();
}

后缀表达式求值：遇到数字入栈，遇到运算符弹出两个操作数计算。

public int evaluatePostfix(String expr) {
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (char c : expr.toCharArray()) {
        if (Character.isDigit(c)) {
            stack.push(c - '0');
        } else {
            // 注意：先弹出的是第二个操作数
            int b = stack.pop();
            int a = stack.pop();
            switch (c) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/': stack.push(a / b); break;
            }
        }
    }
    return stack.pop();
}

最小栈​

设计一个支持 O(1) 获取最小值的栈。关键思路是使用辅助栈同步记录当前的最小值。

public class MinStack {
    private Deque<Integer> stack;
    private Deque<Integer> minStack;  // 同步记录最小值
    
    public MinStack() {
        stack = new ArrayDeque<>();
        minStack = new ArrayDeque<>();
    }
    
    public void push(int val) {
        stack.push(val);
        // 最小值栈：如果为空或新值更小，推入新值；否则推入当前最小值
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            minStack.push(minStack.peek());
        }
    }
    
    public void pop() {
        stack.pop();
        minStack.pop();
    }
    
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

为什么辅助栈要同步 push？ 因为每个位置都应该知道"当前的最小值"。当栈顶元素被弹出后，最小值可能也会改变。

单调栈​

单调栈是栈的高级应用，专门解决"寻找下一个更大/更小元素"类问题。它通过维护栈内元素的单调性，将原本需要 O(n2)O(n^2) 的暴力解法优化到 O(n)O(n)。

单调栈的本质​

单调栈顾名思义，就是栈内元素保持单调递增或单调递减。根据元素是否可以相等，分为四种类型：

类型栈内元素顺序典型应用
严格递增[1, 3, 5, 7]找下一个更小元素（严格）
非递减[1, 3, 5, 5, 7]找下一个更小元素（允许相等）
严格递减[7, 5, 3, 1]找下一个更大元素（严格）
非递增[7, 5, 5, 3, 1]找下一个更大元素（允许相等）

核心技巧：找更大元素用递减栈，找更小元素用递增栈（这是反直觉的，记住"相反原则"）。

通用模板​

// 单调栈通用模板
public int[] monotonicStackTemplate(int[] arr) {
    Deque<Integer> stack = new ArrayDeque<>();
    int[] result = new int[arr.length];
    Arrays.fill(result, -1);  // -1 表示不存在
    
    for (int i = 0; i < arr.length; i++) {
        // 栈不为空 且 栈顶元素满足某种条件
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            int stackTop = stack.pop();
            // 处理栈顶元素，它的下一个更大元素就是 i
            result[stackTop] = i;
        }
        // 栈不为空时，栈顶就是当前元素的"前一个更大/更小元素"
        // if (!stack.isEmpty()) { ... }
        stack.push(i);
    }
    return result;
}

时间复杂度分析：虽然有两层循环，但每个元素最多入栈一次、出栈一次，所以是 O(n)O(n)。

四种基本问题的实现​

1. 下一个更大元素（Next Greater）

public int[] nextGreater(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 严格递减栈：找下一个更大的元素
        while (!stack.isEmpty() && arr[stack.peek()] < arr[i]) {
            result[stack.pop()] = i;
        }
        stack.push(i);
    }
    return result;
}
// 输入: [13, 8, 1, 5, 2, 5, 9]
// 输出: [6, 6, 3, 6, 5, 6, -1]

2. 前一个更大元素（Previous Greater）

public int[] previousGreater(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 弹出所有小于等于当前元素的值
        while (!stack.isEmpty() && arr[stack.peek()] <= arr[i]) {
            stack.pop();
        }
        // 栈顶就是前一个更大的元素
        if (!stack.isEmpty()) {
            result[i] = stack.peek();
        }
        stack.push(i);
    }
    return result;
}

3. 下一个更小元素（Next Smaller）

public int[] nextSmaller(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 严格递增栈：找下一个更小的元素
        while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
            result[stack.pop()] = i;
        }
        stack.push(i);
    }
    return result;
}

4. 前一个更小元素（Previous Smaller）

public int[] previousSmaller(int[] arr) {
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 弹出所有大于等于当前元素的值
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            stack.pop();
        }
        if (!stack.isEmpty()) {
            result[i] = stack.peek();
        }
        stack.push(i);
    }
    return result;
}

关键点总结：

问题类型栈类型while 条件赋值位置
下一个更大非递增<while 内部
前一个更大严格递减<=while 外部
下一个更小非递减>while 内部
前一个更小严格递增>=while 外部

经典问题详解​

每日温度（LeetCode 739）​

给定每日温度数组，返回一个数组 answer，其中 answer[i] 表示要等待多少天才能遇到更暖和的温度。

分析：这就是"下一个更大元素"问题，只是返回的是距离而不是索引。

public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] answer = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 当前温度比栈顶温度高，栈顶位置找到了答案
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            answer[prev] = i - prev;  // 等待的天数
        }
        stack.push(i);
    }
    return answer;
}

接雨水（LeetCode 42）​

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

核心思想：对于每个位置，能接多少水取决于它左边最高的柱子和右边最高的柱子中较小的那个，再减去当前柱子高度。

单调栈解法：维护一个递减栈，当遇到更高的柱子时，可以计算之前低洼处能接的雨水。

public int trap(int[] height) {
    int water = 0;
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < height.length; i++) {
        // 当前柱子比栈顶高，形成凹槽
        while (!stack.isEmpty() && height[i] >= height[stack.peek()]) {
            int bottom = stack.pop();  // 凹槽底部
            if (!stack.isEmpty()) {
                // 栈顶是左边界，当前是右边界
                int leftBound = stack.peek();
                int h = Math.min(height[leftBound], height[i]) - height[bottom];
                int w = i - leftBound - 1;
                water += h * w;
            }
        }
        stack.push(i);
    }
    return water;
}

图解理解：想象高度为 [0,1,0,2,1,0,1,3,2,1,2,1]。

当处理到索引 5（高度 0）时，栈中是 [1(高度1), 3(高度2), 4(高度1)]。继续处理索引 6（高度 1），发现比栈顶高，弹出 4 和 5，此时能计算凹槽中的雨水。

柱状图中最大矩形（LeetCode 84）​

给定 n 个非负整数表示柱状图中各柱子的高度，求能勾勒出的矩形的最大面积。

分析：对于每个柱子，如果知道它向左和向右能延伸多远（直到遇到更矮的柱子），就能计算以它为高的最大矩形面积。这正是"前一个更小"和"下一个更小"问题。

public int largestRectangleArea(int[] heights) {
    int n = heights.length;
    int[] nextSmaller = new int[n];
    int[] prevSmaller = new int[n];
    Arrays.fill(nextSmaller, n);
    Arrays.fill(prevSmaller, -1);
    Deque<Integer> stack = new ArrayDeque<>();
    
    // 同时计算前一个更小和下一个更小
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
            int top = stack.pop();
            nextSmaller[top] = i;
        }
        if (!stack.isEmpty()) {
            prevSmaller[i] = stack.peek();
        }
        stack.push(i);
    }
    
    // 计算最大面积
    int maxArea = 0;
    for (int i = 0; i < n; i++) {
        int width = nextSmaller[i] - prevSmaller[i] - 1;
        maxArea = Math.max(maxArea, heights[i] * width);
    }
    return maxArea;
}

关键理解：矩形的宽度 = 右边界 - 左边界 - 1。右边界是下一个更小元素的位置，左边界是前一个更小元素的位置。

单调栈问题识别​

当遇到以下类型的问题时，考虑使用单调栈：

  1. "下一个..."问题：下一个更大/更小元素
  2. "前一个..."问题：前一个更大/更小元素
  3. "最近的..."问题：最近的满足某条件的元素
  4. 凹槽/山谷问题：接雨水、最大矩形等
  5. 循环数组问题：环形数组中的下一个更大元素

其他应用场景​

函数调用栈​

程序运行时的函数调用天然就是栈结构：最后调用的函数最先返回。递归就是利用了这一点。

当递归层次过深时，会出现"栈溢出"错误（Stack Overflow），因为每个函数调用都会占用栈帧空间。

撤销/重做功能​

编辑器的撤销和重做可以用两个栈实现：

public class TextEditor {
    private StringBuilder text;
    private Deque<String> undoStack;
    private Deque<String> redoStack;
    
    public void type(String newChars) {
        undoStack.push(text.toString());
        text.append(newChars);
        redoStack.clear();  // 新操作清除重做栈
    }
    
    public void undo() {
        if (!undoStack.isEmpty()) {
            redoStack.push(text.toString());
            text = new StringBuilder(undoStack.pop());
        }
    }
    
    public void redo() {
        if (!redoStack.isEmpty()) {
            undoStack.push(text.toString());
            text = new StringBuilder(redoStack.pop());
        }
    }
}

浏览器前进后退​

浏览器的前进后退按钮本质上也是两个栈：一个记录后退历史，一个记录前进历史。

最佳实践​

选择正确的实现​

Java 中推荐使用 ArrayDeque 而不是 Stack 类：

// 推荐
Deque<Integer> stack = new ArrayDeque<>();

// 不推荐（Stack 是遗留类，线程安全但性能差）
Stack<Integer> stack = new Stack<>();

注意空栈检查​

在 pop 或 peek 前务必检查栈是否为空：

// 错误：可能抛出异常
int top = stack.pop();

// 正确：先检查
if (!stack.isEmpty()) {
    int top = stack.pop();
}

操作数顺序​

在表达式求值时，注意操作数的顺序：

// 先弹出的是第二个操作数
int b = stack.pop();
int a = stack.pop();
int result = a - b;  // 正确顺序：a - b

小结​

栈是一种简单但强大的数据结构，它的核心价值在于：

  1. 追踪"最近"：括号匹配、函数调用都是追踪最近的需要处理的事物
  2. 单调性优化：单调栈将 O(n2)O(n^2) 的问题优化到 O(n)O(n)
  3. 状态管理：撤销/重做、前进/后退等场景

掌握栈的关键是理解"后进先出"的语义：哪些场景下"最近"的元素是最重要的？

练习​

基础：

  1. LeetCode 20：有效的括号
  2. LeetCode 155：最小栈
  3. LeetCode 232：用栈实现队列

单调栈： 4. LeetCode 739：每日温度 5. LeetCode 496：下一个更大元素 I 6. LeetCode 503：下一个更大元素 II（循环数组） 7. LeetCode 42：接雨水 8. LeetCode 84：柱状图中最大的矩形 9. LeetCode 85：最大矩形

进阶： 10. LeetCode 224：基本计算器 11. LeetCode 316：去除重复字母 12. LeetCode 456：132 模式