栈的实现与选型：数组栈与链表栈的原理、复杂度及工程实践-编程实验室

1. 项目概述与核心思路

前两天在整理技术栈笔记的时候，又翻到了这个古老但极其经典的问题：用链表和数组分别实现栈。说它经典，是因为这两个东西几乎就是数据结构的敲门砖，链表靠指针串起一片离散的内存，数组靠连续的存储空间把数据排排站好，而栈恰好是一种既能用连续结构承载、也能用链式结构承载的抽象数据类型。从面试到实际开发，从单片机到分布式系统，凡是涉及“先进后出”语义的场景，十有八九都会和栈打交道。

这次我准备把这两种实现方式从头到尾过一遍，不是只贴两段能跑的代码，而是把背后的思路、关键参数、时间空间开销和工程选型逻辑都讲清楚。主要面向三类读者：刚开始学数据结构、被链表指针绕晕的同学；准备面试、想系统整理基础知识的求职者；以及工作中需要自己实现轻量级栈结构、又不方便引入重量级容器的开发者。

至于为什么值得花时间研究这个项目，我的理解是：栈本身足够简单，却完整覆盖了数据结构设计里的几个核心问题——容量管理、内存布局、边界条件、复杂度的权衡。把数组栈和链表栈都写明白，其实就等于把“线性表”的两种存储形态搞透了，后面再去看队列、树、图这些更复杂的结构，思路会清晰很多。

2. 数组实现栈的设计与实操要点

2.1 数组栈的底层逻辑和容量策略

数组实现栈，本质上是把一端固定为栈底，用另一个整数变量记录“栈顶位置”。所有入栈和出栈操作都发生在数组的末端，这样能保证操作复杂度是 O(1)。这句话说起来简单，但实际编码时马上会碰到第一个关键问题：数组的容量是固定的，而栈的长度是动态变化的。

一种处理方式是直接定义一个足够大的固定数组，比如int stack[1024]，然后用一个top变量标记当前栈顶。这种方案在嵌入式开发里很常见，因为嵌入式环境内存有限、忌讳动态申请，所以宁可预先分配一大块静态空间。但缺点也很明显：如果实际入栈的数据量很小，会造成内存浪费；如果数据量超过了预设值，直接溢出，结果就是数据被写到相邻内存甚至程序崩溃。

另一种方式是让数组栈具备自动扩容能力，这也是标准库里动态数组（比如 C++ 的 vector、Java 的 ArrayList）的常见做法。我这次实现的数组栈采用的就是这种策略：栈满时按倍数扩容，栈空时按需缩容。扩容倍率按 2 倍计算，因为弹出入栈的时间复杂度均摊下来还是 O(1)。如果把扩容写成固定增加一段长度，比如每次多给 10 个元素的空间，频繁入栈时扩容次数会大幅上升，导致元素搬运的总开销变大，这在数据量级大时差距很明显。

template <typename T> class ArrayStack { private: T* data; int capacity; int topIndex; // 指向栈顶元素的下标，-1 表示空栈 void resize(int newCapacity) { T* newData = new T[newCapacity]; for (int i = 0; i <= topIndex; ++i) { newData[i] = data[i]; } delete[] data; data = newData; capacity = newCapacity; } public: ArrayStack(int initialCapacity = 16) : capacity(initialCapacity), topIndex(-1) { data = new T[capacity]; } ~ArrayStack() { delete[] data; } void push(const T& value) { if (topIndex + 1 >= capacity) { resize(capacity * 2); } data[++topIndex] = value; } void pop() { if (topIndex >= 0) { --topIndex; } } T& top() { return data[topIndex]; } bool empty() const { return topIndex == -1; } int size() const { return topIndex + 1; } };

2.2 数组栈扩容为什么选 2 倍而不是固定增量

扩容这个细节是很多初学者容易忽略的地方。我见过不少同学的代码，上来就是“满了就new int[N + 10]”，结果就是频繁触发扩容，可能入栈 1000 个元素就搬了上百次数据。假设初始容量是 16，每次固定增加 10，那么插入第 17 个元素要扩容一次，第 27 个、第 37 个……总共要扩约 99 次，每次都要把旧数据搬到新数组，总搬运次数是一个近似二次方的量级。

如果按 2 倍扩容，流程是：16 → 32 → 64 → 128 → 256，达到 1000 个元素只需要扩 7 次左右。最后一次扩容时搬运的数据量虽然大，但前面的扩容次数少，整体均摊下来，每次入栈操作只需要常数级别的操作开销。这个思路在动态数组的源码里普遍存在，是理解“均摊复杂度”这个概念最好的入门案例。

另外，缩容也不能太激进。假如栈元素在 128 和 129 之间来回波动，每次缩到一半再立即翻倍扩容，就会出现抖动，性能反而不稳定。常见的策略是：元素数量降到容量的四分之一时，才把容量缩到原来的一半，保留一定的缓冲区间。这样栈在“满—空—满”的循环里能够保持稳定状态，不会反复做内存申请和拷贝。

2.3 数组栈的边界检查和内存布局

数组栈的代码本身不难，但边界条件必须盯紧。首先是空栈操作：top()和pop()在空栈的时候调用，下标会变成负数，如果不做保护，轻则读到脏数据，重则把一个非法地址传给内存操作函数。其次是push的时候忘记检查容量，直接往data[++topIndex]写值，越界写是 C++ 里比较隐蔽的一种错误，因为它通常不会立刻崩溃，而是等堆结构被破坏后才在某个随机位置炸掉。

内存布局方面，数组栈的数据存储在连续的地址空间，这对 CPU 缓存非常友好。访问一个元素时，其相邻元素也会被加载到缓存行里，入栈和出栈操作频繁访问的又是栈顶附近的元素，所以数组栈在实际运行时往往比链表栈快，这一点在大量 push/pop 场景下体现得很明显。不过它要求一段连续的内存，如果元素本身是很大的结构体，或者系统内存碎片化严重，申请大块连续内存可能会失败。这种情况下要么改用元素指针数组，要么就得考虑链表实现。

3. 链表实现栈的实现细节

3.1 链表栈的节点结构和入栈出栈原理

链表栈和数组栈的思路完全不同。它不需要连续内存，而是每次入栈时动态创建一个节点，出栈时释放对应节点。节点内部保存两个信息：当前的值，以及指向下一个节点的指针。栈顶就是链表的头节点，入栈操作等价于在链表头部插入一个节点，出栈操作等价于删除头节点。这样入栈出栈的时间复杂度同样是 O(1)，而且完全没有容量上限，内存用多少就申请多少，不会出现“预留了一大块空间却用不满”的浪费。

链表的头插头删为什么适合实现栈？因为栈只操作栈顶，也就是只操作链表的头部。如果反过来把栈顶放在链表尾部，出栈时就得从头遍历到倒数第二个节点，复杂度直接退化为 O(n)，明显不合适。这个选择是链表实现栈最核心的思路，也是面试里经常考的一个点。

class Node: def __init__(self, value): self.value = value self.next = None class LinkedListStack: def __init__(self): self._top = None self._size = 0 def push(self, value): new_node = Node(value) new_node.next = self._top self._top = new_node self._size += 1 def pop(self): if self._top is None: raise IndexError("pop from empty stack") value = self._top.value self._top = self._top.next self._size -= 1 return value def peek(self): if self._top is None: raise IndexError("peek from empty stack") return self._top.value def is_empty(self): return self._top is None def size(self): return self._size

3.2 链表栈为什么天然无需扩容

链表栈的容量只受堆内存大小的限制，不需要预先设计扩容阈值和搬移策略，这是它相比数组栈最大的优势。尤其是当栈内保存的元素变化幅度特别大时，比如某段时间每秒入栈几万个数据，之后又迅速清空，链表栈能自动跟随这个节奏，用到多少节点就申请多少节点，清空时也能逐个释放内存。

但事情都有代价。链表栈每个节点都会额外存储一个指针字段，对于存储小数据类型的场景，这个指针本身可能就占了存储空间的一半甚至更多。比如栈里保存的是 int（4 字节），在 64 位系统里 next 指针要占 8 字节，总开销是 12 字节起，再算上动态内存分配器为每个节点维护元数据所付出的额外代价，实际内存开销可能是数据本身的四五倍。所以如果明确知道数据规模不大、波动可控，数组栈在内存利用率上反而更好。

3.3 链表栈实操中的三个细节问题

第一是空栈的表示方式。链表栈的空栈意味着头指针是 null，因此peek和pop必须检查头指针是否为空，不能在空栈状态下解引用头节点。很多初学 C++ 的同学写链表栈，容易在pop里先delete p再p = p->next，这时候p已经被释放，再去访问p->next就是典型的悬空指针访问。

第二是内存释放的顺序。C++ 写链表栈，析构函数要逐个节点 delete，不能只释放头节点就结束。如果把所有节点都 new 到了堆上，却不挨个回收，会产生内存泄漏。如果析构方式写成了遍历链表、边移动边 delete 的写法，要注意先保存下一个节点的地址，再删除当前节点，防止链表断掉。Python 这类带垃圾回收的语言不需要手动释放节点，但也要注意是否形成了指向关系导致对象无法被回收。

第三是头节点问题。链表栈如果用“带头节点”的写法，相当于在真正的栈顶本面额外放了一个哨兵节点，这样空栈判定可以统一为 head->next 是否为空。这种写法在某些统一链表的实现里比较通用，但就栈的场景来说，不带头节点、直接用头指针表示栈顶会更省事，逻辑也更直观。两种写法没有绝对的优劣，但保持逻辑简单始终是重要的。

4. 两种实现方式的对比与选型逻辑

4.1 时间复杂度的表层对比与底层差异

从大 O 复杂度来看，数组栈和链表栈的 push、pop、peek 都是 O(1)，单纯的复杂度结论根本无法区分它们。但真实性能差异藏在常量因子和分布规律里。数组栈所有元素在内存上连续排列，系统访问栈顶元素时自动把附近的内存也加载到缓存行里，当紧接着访问栈顶下一个元素时，大概率直接命中缓存，延迟极低。链表栈的节点分散在堆内存的各个位置，每次入栈都要 new 一个新节点，这个分配动作本身就比数组栈仅仅移动一个下标要慢；出栈时 delete 节点还会触发内存回收，进一步增加开销。

所以如果栈的操作频繁，而且数据量在可预测范围内，我会很明确地选择数组栈。我自己压测过 100 万次 push/pop 交替的循环，链表栈的耗时大约是数组栈的 4 到 6 倍。主要开销就是节点的内存分配和释放。这个差距在嵌入式设备上会被放大，频繁动态内存分配还可能产生碎片。

4.2 内存利用率的对比

数组栈在有大量剩余容量时会浪费内存，链表栈则把内存开销花在每个节点的指针上。下面这个表格能直观地看出差异：

对比维度	数组栈	链表栈
内存连续性	连续	离散
容量管理	需要扩容缩容	天然动态
单元素内存开销	低，无指针	较高，含指针
极端数据波动	扩容缩容有明显成本	自动适配，无搬运成本
缓存友好性	高	低
实现复杂度	相对简单	指针操作容易出错

说实话，在绝大多数业务开发场景里，数组栈比链表栈更“好用”。标准库里的栈容器，比如 C++ 的 std::stack，默认底层就是 deque，用双端队列作为容器适配器，本质上也偏连续存储。链表栈真正的价值更多体现在：面试中展现对内存模型的理解、自定义内存池时需要精确控制节点分配、某些平台不允许使用动态数组但允许动态节点，以及分析问题时的逻辑推演。

4.3 从技术栈角度理解栈的选型

在讨论全栈项目的技术栈时，很容易会提到“技术栈”这个词，但很多人没意识到编程层面的栈和系统层面的调用栈其实是同源的。函数调用、局部变量保存、递归返回地址，这些全都在系统栈里展开。JVM 里有一个本地方法栈专门用来支持 native 方法的调用，这和普通方法调用栈相互配合。理解数组栈、链表栈的原理，再去看 JVM 栈帧、调用栈溢出、递归深度限制这些问题，会有一种“底层机制忽然能对上号”的感觉。

工程上还会遇到一些“看起来像栈”的业务需求。比如小程序的页面栈，页面栈层数超过 10 层时容易出现白屏或者交互异常，这时候如果非要反复往栈里 push 页面，就会出现类似数组栈满溢出的问题。正确的做法是考虑使用reLaunch或redirectTo来精简页面层级，而不是想办法扩容。当然小程序页面栈机制本身不是严格的数组实现，但用数据结构里栈的思维去理解它，能更快判断为什么不能无限跳转，以及该从哪里让一层栈出栈。

5. 常见问题排查与避坑指南

5.1 数组栈常见的隐蔽问题

数组栈最容易踩的坑是“看似正常，实则越界”。比如缩写代码时把if (topIndex + 1 >= capacity) resize(...)漏掉，代码在数据量小的时候运行正常，一旦压到容量临界点，就会往数组后面越界写数据。在 C++ 里这种越界写可能不会立刻崩溃，而是在析构或者下一次 delete 时才报错，排查起来非常头疼。我的习惯是 push 函数内部一定加一个断言，比如assert(topIndex < capacity)，这个断言在 debug 模式下能快速暴露扩容逻辑的错误，release 模式下又不影响性能。

还有一个问题是元素类型为复杂对象时的拷贝开销。数组栈扩容时需要把所有旧对象逐一拷贝到新数组，如果对象是带有堆资源的类，浅拷贝会造成双重释放，或者无谓的深拷贝拖慢性能。这种情况下，要么栈内存储指针而不是对象，要么为对象正确实现移动语义。前者更通用，后者在 C++11 之后可以显著优化。

5.2 链表栈常见的指针问题

链表栈的调试难度比数组栈高，主要原因是“指针跳转”对初学者不直观。最常见的错误有三种：插入节点时把new_node.next = self._top和self._top = new_node顺序写反，导致链接关系断裂；删除节点时没有更新_top，pop 之后栈顶还是旧节点；使用已经删除的节点，比如 C++ 里先 delete 再访问其 next 指针。要快速定位这类问题，终极工具是调试器，在 push 和 pop 处打条件断点，逐步查看头指针地址的变化，如果头指针没有按预期指向新的节点，那基本就是指针赋值的顺序错了。

Python 实现链表栈虽然不用处理内存手动释放，但删除节点时要格外注意是否真的把栈顶切到了下一个节点。如果只把当前节点从栈中逻辑上摘除，却因为某个引用仍然指向它导致它无法被 GC 回收，在极端循环引用的情况下会有内存泄漏的隐患。虽然栈结构本身一般不构成循环引用，但养成设置node.next = None的习惯是好的。

5.3 栈容量和递归溢出的排查思路

栈在实际系统中还有一层重要含义是函数调用栈。递归过深时，程序会抛出“栈溢出”错误，本质上是系统调用栈空间耗尽。这跟数组栈容量满溢其实是一个逻辑：“入栈”所在的递归函数帧太多，而“出栈”还没轮到执行。这个问题常见于深度优先搜索、递归解析等场景。排查时首先看递归深度是否可控，如果确实需要非常深的递归，可以考虑用显式的栈数据结构配合循环来模拟递归过程，这会比盲目增大线程栈空间更安全。

5.4 测试用例设计经验

写完数组栈和链表栈，别急着收工，设计一套能覆盖边界条件的测试用例比实现栈本身更有价值。我一般至少准备这些用例：空栈上调用 empty 和 size，确认返回真和 0；空栈上调用 top 或 pop，确认抛异常或安全返回；顺序 push 到扩容边界，比如容量 16 时 push 17 个元素，确认扩容后数据完整；连续 push/pop 交替操作，验证栈顶数据始终正确；大量 push 后全部 pop，最后 empty 为真；在缩容阈值附近反复 push/pop，确认不会出现抖动导致的容量频繁变化。

用这样一套用例把两种实现都跑一遍，其实能很快暴露出数组栈和链表栈在边界条件下各自的脆弱点。写测试的过程也能帮自己把“栈”这个抽象数据类型的接口定义想清楚，如果接口设计得不够干净，测试用例写起来就会别扭。