如果不算 Hello World栈大概率是你写代码时第一个真正接触的“数据结构”——尽管你可能根本没意识到它在工作。函数调用要靠栈递归返回要靠栈连你在浏览器里按后退键背后也是一套完整的栈逻辑。这篇博文就围绕“栈”这一个主题来写。我会把它的核心概念讲透给出可以直接复制运行的 C 代码实现顺序栈和链式栈都覆盖再拆几个最常见的应用场景最后把新手容易踩的坑一次性列清楚。适合正在学《数据结构》课程、准备面试算法题、或者单纯想补一补基础功的开发者阅读。1. 栈的核心概念与两种实现路线选择1.1 栈到底是个什么东西栈是一种“后进先出”LIFOLast In First Out的线性结构。它的操作被限制在表尾一端进行插入元素叫入栈push删除元素叫出栈pop只看顶端元素但不删除叫取栈顶peek。用一个生活类比来感受它你往一个瓶子里塞硬币先塞进去的硬币在瓶底最后塞进去的在瓶口想取出第一枚塞进去的硬币得先把上面的硬币全部倒出来——这就是栈的行为。又或者像食堂里叠盘子后放的盘子在上面取的时候也是先从最上面拿。栈之所以重要不只是因为它简单而是因为现实中的嵌套、回溯、撤销等问题天然就有“后进先出”的特征。递归函数的调用链、编辑器里的撤销栈、表达式求值里的运算符优先级全都依赖这个看似简单的结构。理解栈其实是在为后面学递归、树的遍历、图的深度优先搜索打底子。1.2 顺序栈与链式栈的对比实现栈可以从底层存储方式出发分成两条路线对比项顺序栈数组实现链式栈链表实现底层存储连续内存数组分散节点靠指针串联栈顶定位一个整型索引 top一个指针指向栈顶节点空间限制可能栈满需要扩容理论上只受内存总量限制入栈出栈效率O(1)常数时间O(1)常数时间内存碎片少一次性分配多每节点单独分配编码难度低容易理解稍高需要小心指针适合场景栈大小可预估大小不确定、频繁创建销毁选型核心就一句话数据量确定、操作频繁用顺序栈数据量动态变化大、需要频繁创建销毁用链式栈。C 语言里如果后天知道峰值顺序栈通常更省心写大型程序或者需要频繁动态申请资源时链式栈更灵活。1.3 一个容易被忽略的设计细节top 的语义写顺序栈时top 的初始值一般习惯设为 -1 或者 0这个细节对后续判断会带来连锁影响。top 为 -1栈为空时 top 指向数组下标 -1。入栈时先 top 再赋值出栈时先取值再 top--。判断空就是top -1判断满就是top MAX_SIZE - 1。top 为 0栈为空时 top 指向数组下标 0。入栈时先赋值再 top出栈时先 top-- 再取值。判断空是top 0。两种写法都能跑通但如果看代码的人对 top 的语义理解不一致很容易把判断条件写错。我建议入门阶段统一采用 top -1 的写法因为判空判满跟数组边界最直观不容易绕进去。后面你如果看别的教材发现 top 初始值是 0只要心里清楚它的语义代码一样能调明白。2. 顺序栈与链式栈的完整代码实现2.1 顺序栈完整代码C 语言顺序栈的核心就是一块连续数组加一个 top 下标。下面是一份可以直接编译运行的实现我在关键位置加了注释#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SeqStack; // 初始化top 置为 -1表示空栈 void initStack(SeqStack *s) { s-top -1; } // 判断空栈 bool isEmpty(SeqStack *s) { return s-top -1; } // 判断栈满 bool isFull(SeqStack *s) { return s-top MAX_SIZE - 1; } // 入栈先移动 top再写入数据 bool push(SeqStack *s, int value) { if (isFull(s)) { printf(栈已满无法入栈\n); return false; } s-top; s-data[s-top] value; return true; } // 出栈取出数据再把 top 下移 bool pop(SeqStack *s, int *value) { if (isEmpty(s)) { printf(栈为空无法出栈\n); return false; } *value s-data[s-top]; s-top--; return true; } // 只读栈顶不改变栈的结构 bool peek(SeqStack *s, int *value) { if (isEmpty(s)) { printf(栈为空无法取栈顶\n); return false; } *value s-data[s-top]; return true; } int main() { SeqStack stack; initStack(stack); push(stack, 10); push(stack, 20); push(stack, 30); int value; peek(stack, value); printf(栈顶元素: %d\n, value); // 输出 30 while (!isEmpty(stack)) { pop(stack, value); printf(出栈元素: %d\n, value); // 依次输出 30 20 10 } return 0; }这段代码把整个栈的生命周期都走了一遍。入栈前先判满出栈前先判空这两步是顺序栈的命根子。一旦漏掉极端数据量下就会出现数组越界写入或者读取一个不存在的下标。我自己早期写的时候就是没判满数据一多就写爆了数组程序直接崩溃而且崩得毫无规律查了半天才发现是这里出了问题。2.2 链式栈完整代码C 语言链式栈的思路更接近链表操作每个节点由数据域和指针域组成入栈就在链表头部插入新节点出栈就删除头节点。由于操作永远发生在头部所以入栈出栈依然是 O(1)。#include stdio.h #include stdlib.h #include stdbool.h // 栈节点结构 typedef struct StackNode { int data; struct StackNode *next; } StackNode; // 栈结构top 指针指向栈顶节点size 记录当前节点数 typedef struct { StackNode *top; int size; } LinkedStack; // 初始化链式栈 void initStack(LinkedStack *stack) { stack-top NULL; stack-size 0; } // 入栈在链表头部插入新节点 void push(LinkedStack *stack, int value) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败\n); return; } newNode-data value; newNode-next stack-top; stack-top newNode; stack-size; } // 出栈删除头节点并返回其数据 bool pop(LinkedStack *stack, int *value) { if (stack-top NULL) { printf(栈为空无法出栈\n); return false; } StackNode *temp stack-top; *value temp-data; stack-top temp-next; free(temp); stack-size--; return true; } // 取栈顶元素不删除节点 bool peek(LinkedStack *stack, int *value) { if (stack-top NULL) { printf(栈为空无法取栈顶\n); return false; } *value stack-top-data; return true; } // 销毁整个栈释放所有节点内存 void destroyStack(LinkedStack *stack) { while (stack-top ! NULL) { StackNode *temp stack-top; stack-top temp-next; free(temp); } stack-size 0; } int main() { LinkedStack stack; initStack(stack); push(stack, 5); push(stack, 15); push(stack, 25); int value; peek(stack, value); printf(栈顶元素: %d\n, value); // 输出 25 while (stack.top ! NULL) { pop(stack, value); printf(出栈元素: %d\n, value); // 依次输出 25 15 5 } destroyStack(stack); return 0; }链式栈代码里最值得琢磨的是 push 操作新节点的 next 指向原来的栈顶然后我们把栈顶指针移动到新节点上。这个“头插法”的思路非常重要它保证了后进的新节点永远在最上面取的时候也先取它天然满足 LIFO 特性。2.3 为什么链式栈的 push 需要传入指针的指针很多新手会困惑链式栈的 push 里修改的明明是stack-top为什么不直接把修改后的栈顶返回出去而是传入LinkedStack *stack核心原因是我们需要通过传地址来修改调用者的变量。stack-top本身是一个指针要修改这个指针的指向必须拿到指针本身的地址也就是LinkedStack *。如果只传一个结构体的副本函数内部修改的只是副本里的 top 字段调用者的栈顶不会发生任何变化。这个道理跟我平时总提醒的一样C 语言里想修改一个变量就要传这个变量的地址想修改一个指针变量就要传这个指针变量的地址。链式栈的 push 和 pop 都需要修改栈顶指针所以必须用LinkedStack *接收参数。真想明白了这一点C 语言指针这块就算过了第一关。2.4 动态扩容思路与另一种语言的快速参考顺序栈最大的短板就是容量固定。如果 MAX_SIZE 定小了后到的数据就没地方放。实际工程里许多场景需要栈能自动扩容做法也不复杂当top capacity - 1时把数组容量翻倍重新分配空间再拷贝旧数据。// 伪代码扩容到原来两倍 int newCapacity capacity * 2; int *newData (int *)malloc(sizeof(int) * newCapacity); for (int i 0; i top; i) { newData[i] data[i]; } free(data); data newData; capacity newCapacity;扩容的节奏选择 1.5 倍或者 2 倍是为了让均摊复杂度保持在 O(1)。每次扩容虽然要拷贝一遍 O(n) 的数据但扩容发生的频率越来越低摊还到每次 push 上仍然是常数时间。这个“均摊分析”的思路在动态数组、哈希表扩容里也都用得上值得单独记住。如果你平时写 Python 更多网上的参考实现大多数直接用 list 模拟栈。下面这段代码足够应付学习笔记和简单算法练手class Stack: def __init__(self): self._items [] def push(self, item): self._items.append(item) def pop(self): if self.is_empty(): raise IndexError(pop from empty stack) return self._items.pop() def peek(self): if self.is_empty(): raise IndexError(peek from empty stack) return self._items[-1] def is_empty(self): return len(self._items) 0 def size(self): return len(self._items)Python 的列表本身支持尾部追加和尾部弹出背后的数组会自动扩容所以拿它模仿栈最顺手。不过到了 C 语言或者 Java 这类语言里栈的实现方式就必须重新考虑这也是为什么我建议至少把 C 版本的代码手动敲一遍的原因——底层细节不过手心里总觉得悬。3. 栈的典型应用场景拆解3.1 函数调用与递归程序运行时操作系统会给每个线程维护一个调用栈。每次调用函数系统会把返回地址、参数、局部变量打包成一个栈帧压入调用栈函数返回时对应栈帧再被弹出。递归的本质就是同一个函数不断地在调用栈上压入新的栈帧直到达到终止条件再逐层弹出。这也是为什么递归深度太大会导致栈溢出每一层递归都占用一个栈帧栈空间是有限的压入的栈帧超过容量就直接崩溃。理解到这一层你就知道面试时被问“递归和栈有什么关系”该怎么答了。自己写一个简单递归时可以试着画出它的调用栈变化比如求 n 的阶乘factorial(5) - factorial(4) - factorial(3) - factorial(2) - factorial(1) - 返回 1 - 返回 2 - 返回 6 - 返回 24 - 返回 120这个逐层深入再逐层返回的过程和栈的线性记忆能力完美对应。很多算法问题——树的前序遍历、图的深度优先搜索——也都是基于这个思路展开的。3.2 括号匹配括号匹配是栈最经典的入门应用题。给定一个只包含(、)、[、]、{、}的字符串判断括号是否合法闭合。思路分三步遇到左括号就入栈。遇到右括号时先检查栈如果栈为空说明没有对应的左括号直接返回 false否则弹出栈顶元素判断是否与当前右括号匹配。字符串遍历完之后如果栈不为空说明还有左括号没闭合返回 false。// C语言括号匹配核心逻辑 bool isValid(char *s) { // 用一个顺序栈模拟这里只写关键逻辑 SeqStack stack; initStack(stack); for (int i 0; s[i] ! \0; i) { char c s[i]; if (c ( || c [ || c {) { push(stack, c); } else { if (isEmpty(stack)) return false; int topChar; pop(stack, topChar); if (c ) topChar ! () return false; if (c ] topChar ! [) return false; if (c } topChar ! {) return false; } } return isEmpty(stack); }这道题看似简单但它把栈的“嵌套匹配”能力展现得很充分。左括号按出现的顺序压入右括号按反序弹出匹配正好符合了 LIFO 的特性。实际工程里编译器检查代码语法时也是类似流程只是判断规则更复杂一些。3.3 表达式求值与中缀转后缀我们平时写的3 4 * 5是中缀表达式人看着自然但对计算机来说并不好直接计算。栈在表达式求值中的角色是把运算符和操作数组织成规范的执行顺序。经典的思路是把中缀表达式转成后缀表达式逆波兰式然后利用栈求值遇到数字直接压栈遇到运算符弹出两个操作数计算完成后把结果压回栈中。中缀转后缀时栈专门用来保存优先级不等的运算符。遇到优先级比栈顶低的运算符就把栈顶高优先级运算符弹出保证后缀表达式的顺序符合数学优先级规则。这个过程在 C 语言编译器解析表达式时被广泛使用也是理解“运算符优先级”背后机器逻辑的极佳入口。想彻底搞懂表达式求值光看书没用。我建议你在代码里手动构造几个中缀表达式比如1 2 * 3和(1 2) * 3一步步写出转换过程。等你能在纸上画出后缀表达式的生成过程再回头看这段逻辑会发现它其实非常机械完全有规律可循。3.4 撤销、后退与深度优先搜索浏览器的后退按钮和文本编辑器的撤销操作本质都是栈的应用。每访问一个新页面就把当前页面压入“历史栈”点后退就从栈顶弹出上一个页面。编辑器里的撤销栈也类似每次操作压栈按 CtrlZ 时弹栈。有意思的是如果想实现撤销和重做两个功能就用两个栈一个存撤销历史一个存重做历史。撤销时从撤销栈弹出操作结果同时把它压入重做栈重做时反向操作。这个“双栈”模式在面试中也经常出现。图论里的深度优先搜索DFS也有栈的身影。递归实现的 DFS 使用系统调用栈非递归实现则必须显式维护一个栈来记录待访问节点。遍历二叉树的前序、中序、后序同样能用栈写出非递归版本。所以说栈不是数据结构课上考完就忘的知识点它是后面几乎所有“回溯类算法”的骨心支柱。4. 新手踩坑实录与调试技巧4.1 空栈访问是头号事故刚写栈的时候最容易犯的错误就是没判空就 pop 或者 peek。顺序栈里如果 top 已经是 -1你还继续执行s-data[s-top]读到的就是数组下标为 -1 的内存链式栈里stack-top是 NULL你访问stack-top-data就是空指针解引用程序直接崩溃。这里我踩过真实的坑某一次写队列场景下的历史记录模块自认为数据肯定不为空跳过了判空逻辑结果上线一跑就崩。排查花了一下午最后定位到源头居然是一个空栈问题。所以我的习惯很明确只要涉及到 pop 和 peek一律先判空哪怕逻辑上明确不可能为空也保留判断。多一次判断对性能的影响微乎其微但能省掉无数个凌晨的排查时间。4.2 链式栈的内存泄漏隐患链式栈每个节点都是 malloc 出来的如果你只出栈却不在 pop 里 free 节点或者整栈不用了却没有一个销毁函数内存就会悄悄漏掉。程序跑得短看不出来跑一个长时间的服务内存占用只会越来越大。正确的做法是像前面代码里那样把 free 写在 pop 的节点摘除步骤里同时封装一个 destroyStack 函数遍历整个栈逐个释放。千万不能满足于“进程退出会自动回收内存”——服务端程序不会频繁退出泄漏就是慢性病。4.3 返回局部变量地址有些同学写 peek 和 pop 时试图直接返回栈顶元素的地址// 错误的示例 int* pop(SeqStack *s) { return s-data[s-top]; }这样写的问题是如果你后续继续 push 或者 pop数组里的数据可能被覆盖返回的指针内容就不可靠了。更稳妥的做法是像前面代码那样用一个输出参数int *value把值带出来或者在函数内部拷贝一份再返回。C 语言里凡是返回“内部数据地址”的设计都要想清楚数据生命周期这是比栈本身更深一层的问题。4.4 top 指针的更新顺序写反顺序栈入栈时应该是先top再data[top] value出栈时应该是先取data[top]再top--。顺序一旦反了要么新值覆盖了旧值要么取到了没初始化的垃圾数据。链式栈也有类似问题push 时必须先让新节点的 next 指向旧栈顶再更新栈顶指针。如果先把stack-top赋给新节点再更新栈顶逻辑就正确如果先更新了栈顶你就丢失了原栈顶链接整条链就断了。这一类问题最好的发现手段是打印每次 push 或者 pop 之后把 top 指针地址和数据值打出来看是否和预期一致。4.5 常见问题速查表现象可能原因解决办法程序在 pop 时崩溃空栈访问top 为 -1 或栈顶为 NULLpush 前判满pop 前判空内存越界写坏数据顺序栈满了还在 pushpush 前检查 isFull或实现扩容字符串括号匹配总失败没处理右括号到来时栈为空的情况匹配逻辑中先判空内存占用只涨不降链式栈 pop 没有 freepop 中释放节点提供销毁函数返回值错乱pop/peek 返回局部变量地址用输出参数返回数据副本这张表是我带过几位同学后总结出来的高频问题。你会发现绝大多数问题根本不是栈这个结构多难而是 C 语言对内存边界和指针的严格要求放大了每一个小疏忽。所以调试栈相关代码时第一件事不是用复杂调试器而是先把“判空判满”四个字刻在脑子里。5. 如何整理一份能长期复用的栈学习笔记5.1 笔记结构从定义到实现再到坑“栈笔记及代码实现”里的“笔记”两个字我理解不是把课本抄一遍而是要整理出一份能长期复用的参考资料。我的笔记结构一般固定为六块定义、特征、基本操作及复杂度、代码实现、典型应用、易错点。定义和特征只需要几百字重点是把 LIFO 的语义用图示或者类比讲清楚。基本操作及复杂度列一张表每个操作一句说明加一行代码。代码实现不用贴特别长的完整程序而是提炼出 push、pop、peek、isEmpty、isFull 这几个核心函数块旁边标注各自的时间和空间复杂度。典型应用写两到三个场景比如括号匹配和函数调用链。易错点就是上一步梳理出来的那一批“坑”越具体越好。这样的笔记结构不贪多但拿到手就能用。以后再遇到栈相关的题目翻出笔记看一眼核心函数和易错点就能快速进入状态。5.2 好笔记是画出来的不是抄出来的纯文字笔记看三天就忘关键知识点一定要画图。以入栈为例画一条水平数组下标从 0 到 n-1top 先指向 -1push 一个数据后top 变为 0数组第 0 格写上了值再 push 一个top 变为 1第 1 格写上了新值。出栈则反向。这个过程用箭头标注清楚比背十遍定义都管用。链式栈的画法更简单画几个方框代表节点节点之间用箭头指向下一个节点栈顶指针用一个单独的箭头标记。每次入栈操作后新节点画在最上面原来的栈顶节点被新节点用箭头指到。这些图用纸笔画也可以用画图工具也可以。我自己的习惯是手绘之后拍照存进笔记虽然不精美但信息量足够。5.3 配套测试用例笔记的另一半灵魂笔记里除了画图和代码我还会写几组测试用例空栈时 pop 和 peek验证判空逻辑入栈一个元素后 peek验证返回值为该元素入栈多个元素后依次 pop验证 LIFO 顺序顺序栈满时继续 push验证判满逻辑链式栈销毁后验证所有节点释放。每一组测试用例旁边都记录预期输出和实际输出。这个过程看起来繁琐但坚持下来收获极大。数据结构这门课最讲求精确测试用例就是精确度的试金石。如果将来你想把这份笔记升级成项目作品带完整测试用例的教程可比只有文字和代码的笔记高好几个档次。5.4 把栈放进更大的知识网络单独学栈容易学完就忘。我的经验是每学完一个数据结构都主动想一想它跟已经学过的内容之间有什么联系。栈和队列都是线性结构一个 LIFO一个 FIFO栈和递归的关系密不可分树的前序遍历可以用栈写非递归版本图的深度优先搜索本质也是栈。我会在笔记最后画一张简单的思维导图把栈放到中心位置然后往外延伸上一级是线性结构下一级是数组和链表两种存储方式再往外是递归、括号匹配、表达式求值、浏览器后退、深度优先搜索。这样整个知识体系就串起来了以后遇到新问题你会很自然地先想“这题能不能用栈”。结尾栈这个东西第一眼看觉得简单用起来却越来越有味道。它只开放一个出入口所有操作都被约束在顶部恰恰是这个约束让它在处理嵌套、回溯和撤销问题时格外顺手。我自己刚开始学的时候总觉得它比不上后面要学的树和图“高级”后来写多了才明白越是基础的结构越是渗透在程序世界的每一个角落。最后再分享一个小技巧我建议你把上面的顺序栈和链式栈代码都亲手敲一遍不要复制粘贴。手敲的过程中你会被迫去思考每一行代码的含义比如为什么 push 要传指针、为什么 pop 要带输出参数。敲完再跑一遍测试用例你会发现栈不再是一个抽象的图而是你真正掌握的工具。等这份代码沉淀成你的肌肉记忆后面学递归和非递归遍历时你会发现一个更开阔的世界已经等着你了。