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._size3.2 链表栈为什么天然无需扩容链表栈的容量只受堆内存大小的限制不需要预先设计扩容阈值和搬移策略这是它相比数组栈最大的优势。尤其是当栈内保存的元素变化幅度特别大时比如某段时间每秒入栈几万个数据之后又迅速清空链表栈能自动跟随这个节奏用到多少节点就申请多少节点清空时也能逐个释放内存。但事情都有代价。链表栈每个节点都会额外存储一个指针字段对于存储小数据类型的场景这个指针本身可能就占了存储空间的一半甚至更多。比如栈里保存的是 int4 字节在 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 模式下又不影响性能。还有一个问题是元素类型为复杂对象时的拷贝开销。数组栈扩容时需要把所有旧对象逐一拷贝到新数组如果对象是带有堆资源的类浅拷贝会造成双重释放或者无谓的深拷贝拖慢性能。这种情况下要么栈内存储指针而不是对象要么为对象正确实现移动语义。前者更通用后者在 C11 之后可以显著优化。5.2 链表栈常见的指针问题链表栈的调试难度比数组栈高主要原因是“指针跳转”对初学者不直观。最常见的错误有三种插入节点时把new_node.next self._top和self._top new_node顺序写反导致链接关系断裂删除节点时没有更新_toppop 之后栈顶还是旧节点使用已经删除的节点比如 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确认不会出现抖动导致的容量频繁变化。用这样一套用例把两种实现都跑一遍其实能很快暴露出数组栈和链表栈在边界条件下各自的脆弱点。写测试的过程也能帮自己把“栈”这个抽象数据类型的接口定义想清楚如果接口设计得不够干净测试用例写起来就会别扭。写在最后数组栈和链表栈这个题目虽然基础但每次重新写一遍我都会有新的体会。数组栈让我意识到连续内存的计算机体系结构优势会直接作用于数据结构链表栈则提醒我灵活性往往伴随着指针管理的复杂度。实际开发里我不会盲选某一种而是先估一下数据规模、波动频率、是否有连续内存限制再决定用哪个。如果你现在刚开始学建议两个都自己实现一遍不要复制粘贴。写完后用我上面提到的测试用例过一遍再试着改成泛型、线程安全的版本这样一轮折腾下来栈这个数据结构就真的属于你了。