跳到主要内容

数据结构：栈

· 阅读需 6 分钟
tanzhuo

栈(Stack)是一种先进后出(LIFO)的数据结构，它只允许在栈顶进行插入和删除操作。栈可以用数组或链表来实现。

之所以想单独写一篇栈，是因为它几乎是最简单的数据结构，却又无处不在：函数调用、异常堆栈、浏览器的后退按钮、编辑器的撤销操作，背后都是同一个模型。很多看起来复杂的问题(比如括号匹配、表达式求值)，一旦想到用栈，思路立刻就清晰了。理解栈，也是理解递归和调用栈溢出这类问题的前提。

栈的基本概念​

在栈中，插入和删除操作通常称为入栈(push)和出栈(pop)。当插入一个元素时，它被放置在栈顶，当删除一个元素时，它是从栈顶删除的。栈顶是栈中最新添加的元素，栈底是栈中最早添加的元素。

可以把栈想象成一摞盘子：新盘子只能放在最上面，取盘子也只能从最上面取。这个"只开一个口"的约束正是栈的价值所在——它天然记录了"谁最后进来"，所以特别适合处理需要"原路返回"的场景。

栈的应用非常广泛，例如，计算机中的函数调用和递归调用都是通过栈来实现的。当一个函数被调用时，它的参数、返回地址和局部变量等信息被压入栈中，当函数返回时，这些信息又从栈中弹出。

基本操作​

以下是栈的基本操作：

push(element)：将一个元素压入栈顶。

pop()：从栈顶弹出一个元素。

top()：返回栈顶元素，但不对栈进行修改。

isEmpty()：判断栈是否为空。

size()：返回栈中元素的个数。

注意 pop 和 top 的区别：pop 会移除栈顶元素并返回它，top(有些实现里叫 peek)只是"看一眼"，栈本身不变。写代码时混用这两个操作是常见的 bug 来源。

用数组实现栈非常直接，只需要维护一个指向栈顶的下标：

// 基于数组的简单栈实现，仅演示核心逻辑
public class ArrayStack {
    private int[] data;
    private int top = -1; // 栈顶下标，-1 表示空栈

    public ArrayStack(int capacity) {
        data = new int[capacity];
    }

    public void push(int element) {
        // 实际使用时这里应做扩容或抛出栈满异常
        data[++top] = element; // 先移动栈顶指针，再写入
    }

    public int pop() {
        // 空栈时应抛出异常，这里省略检查
        return data[top--]; // 返回栈顶元素，同时回退指针
    }

    public int top() {
        return data[top]; // 只读取，不修改栈
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public int size() {
        return top + 1;
    }
}

链表实现则是把链表头当作栈顶，push 就是头插，pop 就是删除头节点，好处是不需要预先分配容量。

复杂度分析​

栈的时间复杂度为O(1)，因为所有操作都是在栈顶进行的。但是，栈的空间复杂度为O(n)，因为需要存储所有元素。

换个角度说：栈的高效恰恰来自它的限制。因为不允许在中间位置插入或删除，所有操作都退化成对栈顶的一次读写，不需要移动其他元素，也不需要遍历。数组实现中唯一的例外是扩容时的搬迁，但均摊下来入栈仍然是常数时间。

栈的典型应用​

在计算机中，栈(Stack)被广泛应用于函数调用、表达式求值、编译器、操作系统等领域。

  1. 函数调用：当一个函数被调用时，它的参数、返回地址和局部变量等信息被压入栈中，当函数返回时，这些信息又从栈中弹出。这个过程被称为函数调用栈，它是实现函数调用的基础。
  2. 表达式求值：当计算机对一个表达式进行求值时，通常使用栈来实现。例如，将中缀表达式转换成后缀表达式时，需要使用栈来存储运算符，以便正确计算表达式的值。
  3. 编译器：编译器将源代码转换成目标代码的过程中，使用栈来实现语法分析和代码生成等功能。例如，在编译器中，使用栈来存储变量、函数、语句等信息。
  4. 操作系统：操作系统中的进程调度、中断处理等功能也需要使用栈来实现。例如，当一个进程被中断时，操作系统会将当前进程的上下文信息（寄存器的值、程序计数器的值等）压入栈中，然后执行中断处理程序。当中断处理程序执行完毕后，操作系统会从栈中弹出上下文信息，恢复当前进程的执行。

这四个场景有一个共同点：都存在"进入—处理—按相反顺序退出"的嵌套结构。函数嵌套调用、括号嵌套、中断嵌套，本质上都是同一类问题，所以都落在栈这个模型上。平时刷题遇到括号匹配、单调栈、深度优先遍历的非递归写法，也都是这个思路的延伸。

踩坑与注意​

  1. 空栈操作：对空栈执行 pop 或 top 是未定义行为或直接抛异常，调用前要么先用 isEmpty 判断，要么明确依赖异常处理，不能想当然。

  2. 栈溢出：递归本质上是在消耗调用栈，递归层数过深会导致栈溢出(Java 中就是 StackOverflowError)。遇到深度不可控的递归，可以改写成显式栈加循环的迭代版本，把数据挪到堆上。

提示

Java 中不建议再使用 java.util.Stack——它继承自 Vector，方法带同步开销且设计陈旧。官方文档推荐用 ArrayDeque 来充当栈。

  1. pop 与 top 混淆：只想读栈顶却调用了 pop，会悄悄丢掉元素，这类 bug 在循环里尤其难排查。

小结​

栈是"约束换效率"的典型例子：只开放栈顶一个操作口，换来所有操作 O(1) 的代价，同时天然契合一切嵌套、回溯类的问题。掌握了 push/pop/top 这几个操作和 LIFO 的心智模型，再去看函数调用栈、表达式求值这些机制，就只是同一个模型在不同层面的重复应用。

评论 / COMMENTS