栈的数组与链表实现：从后进先出到StackOverflowError

递归写多了，迟早会遇到一个让新手头皮发麻的报错：StackOverflowError，直译过来就是“栈溢出”。我第一次看到这个异常时整个人是懵的——明明代码逻辑看起来没毛病，怎么就溢出了？后来把调试器里的调用栈(Stack)面板打开，一层一层往上翻，才发现问题不在眼前这一帧，而是藏在几百次调用之前的某个循环里。想明白这件事之后，我对数据结构里最基础的“栈”算是彻底开了窍。

这篇文章就把栈的两种典型实现——数组版和链表版——从头到尾拆开讲清楚，包括底层原理、完整代码、性能对比和真实排错经验。适合正在啃数据结构教材、被栈的实现搞得云里雾里的初学者，也适合面试前想把栈相关知识点过一遍的人。我不会光说理论，每一步都会告诉你我为什么这么写，哪些地方容易踩坑，以及实际项目里怎么选。

1. 从“后进先出”说起：栈这个数据结构到底解决了什么问题

1.1 栈的定义：操作受限的线性表

栈本质上是一种线性表，只不过它比普通线性表多一些限制：所有的插入和删除操作，都只能在表的一端进行。这一端叫作栈顶（Top），另一端叫作栈底（Bottom）。往栈顶放元素叫入栈（Push），从栈顶拿掉元素叫出栈（Pop），只看栈顶元素不出栈叫取栈顶（Peek）。

这种“只在一端操作”的限制，天然形成了一种顺序：后进来的元素先出去，经典的后进先出（LIFO，Last In First Out）。

很多人学栈的时候觉得这就是个简单的规则，没什么好深入的。实际上，这个“限制”恰恰是栈的精华。普通线性表的好处是灵活，想插哪里插哪里；但栈主动放弃这种灵活性，换来的是极少数几个操作在O(1)时间内稳定完成，而且语义极其清晰——你永远只关心当前栈顶那一个元素。计算机底层很多机制都靠这种“只处理最近入口”的规则来保证不会乱套。

1.2 生活里的栈：一摞盘子、浏览器返回和撤销按钮

理解栈最常用的类比是食堂里的那摞盘子。新洗好的盘子总是堆在最上面，取盘子的人也是先拿最上面的那个。你要是想从下面抽一个盘子，大概率整摞都得塌。

浏览器里的后退按钮是另一个典型场景。你从首页点进文章，又从文章点进作者主页，再从作者主页点进他的另一篇文章。点“后退”的时候，顺序一定是文章→作者主页→文章→首页，跟你访问的顺序完全相反。这就是栈。编辑器里的撤销（Undo）也是一样，每次都撤销最近一次操作。这些场景的共同点在于：需要按时间顺序记录历史，但处理的时候要倒着来。

1.3 为什么函数调用天然就是栈

我真正理解栈的必要性，是弄懂函数调用机制之后。程序运行时，函数A可以调用函数B，函数B里面还能继续调用函数C。如果C先执行完毕了，接下来应该回到B中调用C的那一行继续跑，然后B执行完，再回到A。也就是说，执行顺序是C→B→A，跟调用的顺序A→B→C正好相反。

这种“调用谁先，返回谁后”的规则，就是栈的规则。操作系统给每个线程维护的就是一个调用栈：每次函数调用，就把这次调用的返回地址、参数、局部变量打包成一个栈帧，压进调用栈；函数返回时，再把栈帧弹出，回到上一层继续执行。递归为什么容易栈溢出？因为递归每一层调用都要压入一个栈帧，如果递归深度过大或者终止条件写错，栈里积累的栈帧越来越多，最后把内存空间耗尽，就报StackOverflowError。

所以栈不是一个只在教科书里被“实现”着玩的数据结构，它是程序运行的基础设施。理解了这一点，后面去看栈的实现，视角会完全不一样。

2. 数组实现栈：最直观也最值得抠细节的写法

2.1 结构设计：top指针到底应该指向哪里

用数组实现栈是最自然的思路。数组本身有连续的内存空间，我们只需要一个变量来记录“栈顶到了哪个位置”。

结构体长这样：

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #define INIT_CAPACITY 4 typedef struct { int *data; // 存放元素的数组 int top; // 栈顶指针，-1 表示空栈 int capacity; // 当前数组容量 } SqStack;

这里有个值得抠的细节：top的初始值到底设为-1还是0？

两种写法的逻辑分别是：

• top = -1：top指向栈顶元素本身。空栈时top为-1；push时先top++，再把元素写入data[top]；pop时取出data[top]，然后top--。
• top = 0：top指向栈顶元素的下一个空位。空栈时top为0；push时先写data[top]，再top++；pop时先top--，再取data[top]。

我推荐第一种。原因很简单：取栈顶元素的时候直接data[top]就行，不需要在脑子里先减1；判空也只要判断top == -1，直观。第二种写法在C语言动态数组的实现里逻辑上也成立，但新手容易在pop的时候搞混顺序，是先取还是先减？选择top = -1的写法能把这种心智负担降到最低。

2.2 入栈、出栈、取栈顶：核心三件套

下面直接给出完整实现。我按照“先判断、再操作”的原则来做，这样每个函数在非法调用时都能安全返回false，而不是让程序崩溃。

// 初始化栈 void initStack(SqStack *s) { s->data = (int *)malloc(sizeof(int) * INIT_CAPACITY); s->top = -1; s->capacity = INIT_CAPACITY; } // 入栈 bool push(SqStack *s, int value) { // 动态扩容，后面专门讲 if (s->top == s->capacity - 1) { int newCapacity = s->capacity * 2; int *newData = (int *)realloc(s->data, sizeof(int) * newCapacity); if (newData == NULL) { return false; // 扩容失败，入栈失败 } s->data = newData; s->capacity = newCapacity; } s->top++; s->data[s->top] = value; return true; } // 出栈 bool pop(SqStack *s, int *value) { if (s->top == -1) { return false; // 空栈不能出栈 } *value = s->data[s->top]; s->top--; return true; } // 取栈顶，不出栈 bool peek(SqStack *s, int *value) { if (s->top == -1) { return false; } *value = s->data[s->top]; return true; } // 销毁，释放内存 void destroyStack(SqStack *s) { free(s->data); s->data = NULL; s->top = -1; s->capacity = 0; }

这里反复出现top == -1这个判断，它对应的就是“空栈”。我用返回值true/false来标记操作是否成功，而不是写一个if把栈顶当负数去访问。调试的时候这样写省心很多。如果哪天你忘记了判空直接pop，不出意外的话你会拿到一个随机数或者在Debug模式下触发越界断言。

2.3 扩容：数组栈装满了怎么办

固定大小的数组有一个硬伤——容量写死之后，装满了就只能返回“入栈失败”。实际工程里往往不知道栈的最大深度，所以比较成熟的做法是动态扩容。

我在push里的扩容策略是：当top == capacity - 1，也就是数组满员时，申请一块新内存，容量翻倍，然后让原来的数据搬到新内存里。为什么翻倍而不是每次加1或者加10？因为如果每入栈一个元素就要扩容一次，那入栈n个元素会触发n次搬移，总耗时O(n^2)；而翻倍扩容的话，虽然单次扩容慢，但均摊到每一次入栈操作上，时间复杂度仍然是O(1)。这个问题面试经常问，你答出“均摊分析”这个词会加分不少。

具体实现上，我用了C语言自带的realloc。它的好处是：如果原内存后面有足够空间，可以直接扩展，不需要搬数据；如果后面空间不够，它会自动分配一块新内存，把旧数据搬过去，然后释放旧内存。但有一点要注意：realloc失败的时候会返回NULL，而原本的内存指针并不会被释放。所以我先把返回值存到临时变量newData里，确认不是NULL之后才赋给s->data。如果直接写成s->data = realloc(...)，扩容失败时你不仅丢了原来的数据指针，还会造成内存泄漏——旧内存已经找不回来了。

缩容我在这个版本里没做，因为栈大部分场景下是高频进出，内存一会儿扩大一会儿缩小反而浪费。如果你确需在栈变空时回收内存，可以在pop里检查s->top < s->capacity / 4之类的阈值再缩容，避免频繁在临界点来回扩容缩容，这个思路在Java的HashMap和C++的vector里都能看到影子。

3. 链表实现栈：弹栈入栈都在头部的另一种玩法

3.1 为什么链表栈要用头插法

数组实现靠下标，链表实现靠节点之间的指针。单链表里访问头节点是O(1)，访问尾节点要遍历到尾巴，也是O(n)。既然栈要求入栈和出栈都在O(1)时间完成，那链表栈的操作位点铁定选在链表头部，也就是“头插法入栈、头删法出栈”。

有人会想：那我在链表尾也维护一个尾指针，不也能O(1)吗？理论上确实可以，但出栈时你要删除尾节点，你得知道尾节点的前一个节点是谁，而单链表里要知道前驱只能从头遍历，做不到O(1)。除非用双向链表加尾指针，但那样的节点更大，逻辑更绕，完全没必要。所以标准的链表栈用单链表、操作头部，就够了。

还有一个细节帮助理解：链表头部是最近插入的节点，而从栈顶弹出的也是最近插入的元素。头插法构建的链表顺序，恰恰就是栈的顺序——最新节点永远在头部，完美契合LIFO。

3.2 结构体定义与初始化

typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *top; // 指向栈顶节点 int size; // 栈内元素个数，可选 } LinkStack; void initStack(LinkStack *s) { s->top = NULL; s->size = 0; }

相比数组栈，链表栈的结构体少了一个capacity，因为链表节点是动态申请的，理论上不设上限。size不是必需字段，但留着它可以在O(1)时间内知道栈的元素个数，某些场景下很有用，比如后面括号匹配要判断栈深。

3.3 入栈和出栈的实现细节

// 入栈 bool push(LinkStack *s, int value) { Node *newNode = (Node *)malloc(sizeof(Node)); if (newNode == NULL) { return false; } newNode->data = value; newNode->next = s->top; // 新节点指向当前栈顶 s->top = newNode; // 新节点成为栈顶 s->size++; return true; } // 出栈 bool pop(LinkStack *s, int *value) { if (s->top == NULL) { return false; } Node *tmp = s->top; *value = tmp->data; s->top = s->top->next; // 栈顶指针下移 free(tmp); s->size--; return true; } // 取栈顶 bool peek(LinkStack *s, int *value) { if (s->top == NULL) { return false; } *value = s->top->data; return true; }

入栈时先malloc一个新节点，把它的next指向原来的栈顶节点，然后把栈顶指针更新到新节点。出栈时把栈顶节点保存下来，取走数据，栈顶指针往next方向移动一位，最后释放旧节点。

有几个点容易出错。第一个，pop里的free(tmp)之前，一定要先把tmp->data取出来保存到*value，因为tmp和s->top最初指向同一个节点，如果你先把free(tmp)执行了，再去访问tmp->data就是悬垂指针。第二个，push中newNode->next = s->top和s->top = newNode这两行的顺序不能颠倒，颠倒之后新节点就找不到原来的链表了。第三个，判空条件用s->top == NULL，链表栈不需要维护一个“栈底”特殊节点，空栈就是栈顶指针为空。

3.4 空栈与内存释放问题

链表栈最容易忽略的是销毁内存。数组栈的销毁只要free(s->data)，而链表栈如果只释放栈顶一个节点，那链表里剩下的节点全都泄漏了。你要从栈顶往下一个个节点释放：

void destroyStack(LinkStack *s) { Node *cur = s->top; while (cur != NULL) { Node *next = cur->next; free(cur); cur = next; } s->top = NULL; s->size = 0; }

这个函数很重要。我见过不少人在课程设计里写完链表栈就扔一边，短小的测试程序跑起来用肉眼看不出来内存泄漏，但放到嵌入式或者长时间运行的服务里，这种“忘记释放”会让内存只增不减。链表栈的好处是没有容量上限、不用扩容搬移，代价就是所有内存都得你自己管理。每一块malloc出来的节点，最终都要free回去。

4. 两种实现的硬核对比：内存、性能与适用场景

4.1 一张表看透它们

很多初学者实现完两种栈之后，总觉得“也就是写法不一样而已”。实际上它们的差异在真实场景中很明显，我整理成一张表：

两边的插入删除都是O(1)，但O(1)的“常数”差很多。数组栈的入栈只是top++和一次数组赋值；链表栈要malloc一个节点、设置指针、更新头指针，如果考虑malloc的系统调用开销，性能完全是两个量级。

4.2 内存分配方式带来的差别

数组栈用的是连续内存，CPU在访问data[top]和data[top-1]这种相邻元素时，高速缓存命中率很高。链表栈的节点分布在堆的不同角落，指针忽东忽西，缓存命中率低。对数据量大、入栈出栈频率极高的场景，这个差距会被放大。

另一个隐形开销是单节点大小。假设存一个int占4字节，链表节点里多一个next指针占8字节（64位系统），那链表栈每存一个int实际要消耗16字节左右（考虑到对齐可能更多），内存利用率只有25%。你原本可以装100万个元素的栈，用链表栈可能连60万都装不下，剩下全被指针和内存对齐浪费了。

4.3 不同场景下的选型建议

我自己的经验是：

• 如果事先能估算栈的最大深度，或者栈的规模不大，优先用数组栈。少一层malloc就少一层风险，性能也稳定。
• 如果栈的元素个数完全不可预测，而且扩容拷贝的代价让人无法接受，那就用链表栈。虽然节点有额外开销，至少不会出现“扩容到一半内存不足导致整个栈挂掉”的局面。
• 如果元素本身很大，比如栈里存的是大结构体，可以栈里只存指针，这样数组栈和链表栈的额外空间差异会变小，选哪个就看你对内存连续性的要求了。
• 开发效率优先的时候，直接用语言自带实现。Java里别用Stack类（它继承自Vector，带同步锁，性能拖后腿），用ArrayDeque；C++里std::stack默认容器是deque，大多数情况下够用；如果是自研嵌入式代码，没有标准库依赖，按本文思路自己实现也是几十分钟的事。

5. 实战：用栈解决括号匹配问题，以及一条完整的排错链路

5.1 括号匹配怎么用栈解

括号匹配是栈的经典入门题，也是很多公司面试手写代码时的保留项目。问题是这样的：给你一个字符串，里面包含(、)、[、]、{、}，判断这些括号是否合法匹配。

用栈的思路非常自然：从左到右扫描字符串，遇到左括号就入栈；遇到右括号，就把栈顶的左括号弹出来跟它配对。如果配对成功就继续；如果栈是空的说明这个右括号没有左括号跟它配对；如果栈顶的左括号跟当前右括号不是同一类，说明括号交叉了，比如([)]这种情况非法。扫描完整个字符串后，栈必须是空的，否则说明有左括号从来没被匹配。

为什么这个题非用栈不可？因为最近出现的左括号要第一个被处理，这本身就是后进先出的场景。比如((){})，扫描到最后一个)的时候，之前压入的(、(、{，栈顶正好是跟)同类的那个(。如果不用栈，你就得自己记录“最近未匹配的左括号在哪”，记来记去非常容易出错。

5.2 最简实现：数组模拟栈

很多C语言面试题不让用太多库，所以我直接用数组模拟栈，代码最精简，也最能展示思路：

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> #include <string.h> bool isMatching(char left, char right) { return (left == '(' && right == ')') || (left == '[' && right == ']') || (left == '{' && right == '}'); } bool isValid(char *s) { int len = strlen(s); // 栈的最大深度不会超过字符串长度，因此一次性分配合适大小 char *stack = (char *)malloc(sizeof(char) * (len + 1)); int top = -1; for (int i = 0; i < len; i++) { char ch = s[i]; if (ch == '(' || ch == '[' || ch == '{') { stack[++top] = ch; } else if (ch == ')' || ch == ']' || ch == '}') { if (top == -1) { free(stack); return false; // 右括号来了，栈里却没有左括号 } char left = stack[top--]; if (!isMatching(left, ch)) { free(stack); return false; // 左右括号类型不匹配 } } // 其他字符直接忽略 } bool result = (top == -1); // 栈必须是空的 free(stack); return result; }

这里有个我特别想强调的工程细节：栈的大小直接开成len + 1，因为栈里最多放len个字符（全是左括号的情况），不会超过这个上界。这样写就不用动态扩容，又把内存申请控制在了极小的范围内。如果你用动态栈来做这道题，也能跑，但会显得绕——明明能确定上界，何必扩容。

5.3 新手最容易踩的三个坑

我帮别人review这种代码时，发现错误几乎集中在三个地方。

第一个，出栈前没判空。遇到右括号直接弹栈，碰上")("这种字符串，就会去访问一个空栈的栈顶，结果不可预知。处理方式就是判断top == -1，栈空说明右括号多余，直接返回false。

第二个，弹出左括号后忘了比较类型。有人觉得“弹出就行，数量对得上就合法”，于是([)]这种字符串也会被判断成合法。必须逐对比较左右括号是不是同类。

第三个，扫描完忘了检查栈是否为空。"()({"这种左括号多出来的情况，如果不做最后的top == -1检查，会错误地返回true。我看到不少同学写完只测了正确用例，一上来跑“左括号多余”的用例就露馅。

5.4 一次真实排错过程还原

有一次我在一个C项目里写了一个表达式解析器，里面用了括号匹配的类似逻辑。程序跑起来后在某个固定输入上崩溃，报错信息在Debug模式下指向了pop函数里访问数组的那一行。

我第一步不是去看pop，而是先想：崩溃在pop，说明它访问了一个非法的索引，而索引来自top，top变成了-2或者更大的负数。第二步，我在pop入口处加了打印：

printf("before pop, top = %d\n", s->top);

跑一次，发现top第一次变-2的时候，正好是解析器处理")"类型字符的分支。这时候我意识到：处理右括号时，我的代码忘记先判断栈是否为空。空栈里根本没有左括号可以弹，而这一支当时也接受了“空栈时pop”的调用，top从-1继续减到-2，下次再访问就崩了。

第三步，我沿着调用关系往上追，找到解析器处理右括号的代码块，加上判空逻辑，并且将“空栈遇到右括号”视为表达式不合法，直接返回错误码。改完再跑，崩溃消失。这个过程大概花了十分钟，但很大程度上帮我养成了一个习惯：凡是从栈里取元素的函数，调用前第一件事就是确认栈非空。这个习惯在链表栈里同样适用，否则pop会解引用空指针。

6. 从函数调用到面试题：栈在真实编程里的扩张用法

6.1 调用栈背后的栈帧

前面已经提到，程序运行时的函数调用链就是一个栈。展开讲一点底层细节：每次函数调用，系统会分配一段连续的内存区域，叫栈帧，用来保存这次调用的返回地址、实参、局部变量以及一些寄存器状态。函数开始执行时，栈帧入栈；函数return时，栈帧出栈，控制权交还给栈顶下一层的函数。

所以调试的时候，“调用栈”窗口列出的每一行，本质上就是当前线程的栈上一帧帧调用信息。你看到main → funcA → funcB → funcC这样的列表，意思是当前程序停在funcC内部，而funcC是被funcB调用的，最外层是main。

递归爆栈的原因也可以从栈帧的角度理解：每一层递归都生成一个栈帧，但函数还没返回就不会弹栈，层数一深，栈空间耗尽。默认线程栈大小通常是8MB（Linux下）或1MB（Windows下），一个简单的递归函数每层只占几十字节，也能轻松达到几十万层的深度。所以递归能不能写，不只是“逻辑对不对”的问题，还必须有足够的栈空间。

6.2 在IDE里读懂调用栈

调试程序时，我看调用栈的次数比看单步执行多得多。Eclipse的Debug视图右侧有一个堆栈窗格，列出当前线程的整个调用链，从当前执行帧到最外层，一目了然。IDEA的Debug窗口默认显示的是“Frame”面板，里面同样列出了所有栈帧，双击任何一帧，编辑器会自动跳转到对应源码行，右侧变量窗口也会切换成那一帧的局部变量。

有人可能抱怨IDEA的调用栈查看体验不如Eclipse，我的看法是：工具形态略有差异，但核心操作是一致的。最难的不是看面板，而是肯不肯一帧一帧点下去。很多新手遇到NullPointerException或者数组越界，只看当前异常那一行的代码，怎么也想不明白逻辑错在哪；其实栈里那一串Frame已经把“怎么走到这一步的”完整记录下来了。从最顶层一帧一路看到最底层那一帧，通常很快就能定位到“源头”——那个传入错误参数的外层调用。

这也是我强烈建议各位练一练的技能：每遇到异常，先打开调用栈面板，把每一帧的局部变量都看一遍，再动手改代码。它比盲目打断点效率高很多。栈这个数据结构在调试器里不是抽象的，它就是你眼前那一列表格，理解它就是理解你程序运行的路径。

6.3 高频面试题：两个栈实现队列、最小栈等

面试里栈的题很多是在考“如何用栈这个受限结构，通过组合设计去解决问题”。我挑两个高频的说说思路。

第一道，用两个栈实现队列。队列是先进先出（FIFO），栈是后进先出（LIFO），一个栈做不到，但两个栈颠倒两次就变成先进先出了。实现方式：入队时push到stackIn；出队时，先看stackOut是不是空的，如果空，就把stackIn里的元素全部pop出来再push进stackOut，然后从stackOut的栈顶取元素。这样stackIn负责“收”，stackOut负责“发”。虽然某些瞬间会触发大量搬移，但均摊下来每个元素最多被搬移两次，时间复杂度还是O(1)。这题的关键是：stackOut空的时候再倒，不能在stackOut还有元素的时候就把新元素倒进去，否则顺序会乱。

第二道，最小栈。设计一个栈，除了支持push、pop，还要能在O(1)时间取到栈中的最小值。我常用的方案是开两个栈：数据栈正常存数据，辅助栈专门存“当前最小值”。push时，如果新元素比辅助栈栈顶的值小，辅助栈push新值；否则辅助栈把栈顶的旧最小值再push一遍，这样两个栈的高度始终一致。pop时两个栈一起pop，辅助栈栈顶始终就是当前数据栈的最小值。另一种空间压缩做法是只用一个栈，push时同时压入“当前值”和“当前最小值”，但代码看起来没有双栈清晰。面试时能把双栈方案写明白，基本就过关了。

第三道相对进阶的就是单调栈，典型应用是“求数组中每个元素右边第一个比它大的元素”。从右往左扫，维护一个单调递减的栈，每次把栈中小于当前元素的元素弹出，剩下栈顶就是我们要找的数。这个题用暴力嵌套循环很好想，但O(n^2)大概率过不了大测试用例，用单调栈就能做到O(n)。面试遇到可以提一嘴，说明你对栈的理解不局限于基础操作。

6.4 我的一个习惯：把递归写成栈

说回开头的StackOverflowError。实际工作里，如果递归深度不可控，我常常不会硬调递归，而是手动维护一个栈，把递归逻辑改写成显式的循环。

比如二叉树的前序遍历，教科书版本是递归：

void preorder(TreeNode *root) { if (root == NULL) return; visit(root); preorder(root->left); preorder(root->right); }

改成显式栈就是这样：

void preorderIterative(TreeNode *root) { if (root == NULL) return; // 简单用数组模拟栈 TreeNode *stack[1000]; int top = -1; stack[++top] = root; while (top != -1) { TreeNode *node = stack[top--]; visit(node); // 先压右子树，再压左子树，出栈时才能先访问左子树 if (node->right != NULL) { stack[++top] = node->right; } if (node->left != NULL) { stack[++top] = node->left; } } }

这个改写的思路，就是把系统隐式帮我们维护的那套调用栈，换成自己控制的显式堆栈。好处有两个：一是不受系统栈大小限制，栈深度只受堆内存限制；二是每一步压栈弹栈都在眼皮底下，调试时逻辑更明确。代价是代码要自己维护栈顶指针和循环条件，可读性比递归略差。

我个人这些年用栈最多的场景，一是做表达式求值里的括号和运算符优先级，二是树和图遍历里的路径回溯，三是把各种递归改成循环来避免爆栈。但我也想说一句：不要为了显式栈而显式栈，如果递归深度有限、代码语义清晰，递归直接用就好；只有当深度可能失控，或者性能瓶颈明确出在递归调用上，才值得手写栈来替代。

栈这个东西，结构简单到可以闭着眼睛写完，但它的应用贯穿程序运行、调试、算法设计一条线。能在Debugger里看懂调用栈，能在括号匹配里写出不崩的代码，能在面试题里把双栈思路讲明白，你对栈的掌握就比单纯背定义的人深了一个层次。