★ FEATURED ARTICLE 最近在带一个模拟项目小组发现不少同学学到“数据结构1-2栈”这里上课一听就懂回头自己写代码却连栈顶指针该指向哪都理不清。有个同学写了15分钟的括号匹配结果一跑就段错误查了半天才发现是出栈的时候根本没判空。这其实不是笨而是栈这个结构太“反直觉”了——它明明是个最老实的线性表却偏偏要后进先出。所以这篇就来把“数据结构1-2栈”这个知识点彻底说透不只是贴一段数组实现就算完而是把顺序栈和链式栈的实现细节、栈顶指针的边界条件、几个经典应用括号匹配、进制转换、表达式求值的完整思路全部拆开最后再附上我这些年见过的高频报错和调试心得。不管你是正在跟课的学生、准备面试的求职者还是工作中要手写栈的开发者这篇都能给你一份直接能抄作业的参考。1. 先搞懂栈到底是个什么东西1.1 后进先出一个把“插队”变成“排队”的结构栈的本质其实特别简单它是一种只允许在一端进行插入和删除操作的线性表。这一端就叫栈顶另一端叫栈底。所有数据都只能从栈顶进、从栈顶出这就是“后进先出”LIFOLast In First Out。你可以把它想象成一个只有顶部开口的羽毛球筒。你要取最底下的那只球必须先把上面压着的球全部拿出来。咖啡馆里店员叠盘子也是这个道理后放上去的盘子总是先被取走。这种“越晚进来越先出去”的规则乍一看好像很受限但正是这种严格的限制反而让栈在处理“嵌套”“回溯”“撤销”这类场景时有着天然的优势。我上课时经常问一个问题栈和数组、链表有什么区别很多人的第一反应是“栈更简单”。这其实只说对了一半。数组和链表是存储结构它们解决的是“数据在内存里怎么摆”的问题而栈是一种逻辑结构它解决的是“数据以什么顺序被访问”的问题。实现栈的时候底层既可以用数组也可以用链表但无论底层怎么变对外暴露的接口永远是那固定的几个操作入栈push、出栈pop、取栈顶peek、判空isEmpty。理解到这一层栈才不只是“一个能装数据的盒子”而是一套管理数据顺序的规则。1.2 栈顶指针的三种写法直接决定你会不会翻车很多初学者写栈最纠结的就是栈顶指针的指向。这里其实有套路不同教材、不同代码风格出的题也不一样最常见的是下面三种。第一种写法top 初始化为 -1入栈时先 top 再存值出栈时先取值再 top--。这种写法下top 指向的是栈中最后一个有效元素的位置也就是真正的栈顶。第二种写法top 初始化为 0入栈时先存值再 top出栈时先 top-- 再取值。这种写法下top 指向的是栈中下一个空闲位置判断栈满的条件是 top MAXSIZE。第三种写法在链式栈里比较常见top 初始化指向头结点或者直接指向栈顶节点入栈用头插法出栈用删除头结点的方式这时候 top 始终指向栈顶元素。这三种写法本身没有绝对的对错但你必须保证整套逻辑内部是自洽的。最翻车的组合是初始化用了 -1 的写法判断空栈却用了 top MAXSIZE结果程序跑起来全是莫名其妙的内存乱读。我见过太多同学在这里踩坑所以建议平时练习固定用一种写法代码里把“判空”“判满”“入栈”“出栈”写成四个清晰的小函数不要让这些判断散落在主函数里。提示面试或考试时如果题目没有明确说明栈顶指针的初始值默认按 top-1 的写法处理通常是最稳妥的因为它最符合“top 指向当前栈顶元素”的直觉。2. 顺序栈与链式栈两种实现适用场景完全不同2.1 顺序栈的数组实现边界条件一个都不能错顺序栈就是用一段连续的内存空间通常是数组来存放栈元素再用一个整数变量 top 记录栈顶位置。这种实现最大的优点是简单、访问快因为有数组下标可以直接定位。先看完整的可运行代码C语言版我尽量把注释写详细#include stdio.h #include stdlib.h #include stdbool.h #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top; // 栈顶指针初始化为 -1指向栈顶元素 } SeqStack; // 初始化 void InitStack(SeqStack *s) { s-top -1; } // 判空 bool IsEmpty(SeqStack *s) { return s-top -1; } // 判满 bool IsFull(SeqStack *s) { return s-top MAXSIZE - 1; } // 入栈 bool Push(SeqStack *s, int x) { if (IsFull(s)) { printf(栈满无法入栈\n); return false; } s-top; s-data[s-top] x; return true; } // 出栈 bool Pop(SeqStack *s, int *x) { if (IsEmpty(s)) { printf(栈空无法出栈\n); return false; } *x s-data[s-top]; s-top--; return true; } // 取栈顶元素不弹出 bool GetTop(SeqStack *s, int *x) { if (IsEmpty(s)) { printf(栈空\n); return false; } *x s-data[s-top]; return true; } int main() { SeqStack s; InitStack(s); for (int i 1; i 5; i) { Push(s, i); } int x; while (!IsEmpty(s)) { Pop(s, x); printf(%d , x); } // 输出5 4 3 2 1 return 0; }这段代码里最容易出错的两个地方一是判满条件。数组下标从 0 到 MAXSIZE-1所以 top 到 MAXSIZE-1 时栈就满了不是 MAXSIZE。我第一次写栈的时候就在这个边界上翻过车push 到第 101 个元素时数组越界程序直接崩后来养成习惯所有边界条件都拿小例子手推一遍。二是出栈函数为什么要传指针。老有人问我出栈的时候函数内部已经把 top 改了为什么不直接返回元素值因为栈空的时候你没法用一个合法的 int 值既表示“出栈失败”又表示“弹出的数据”所以常规做法是用返回值表示操作是否成功用指针参数带回弹出的数据。这个小习惯能让你的栈接口变得非常健壮不至于调用方拿到一个负数就以为是一堆垃圾数据。2.2 链式栈的实现不用判满但要小心头结点顺序栈有一个天生的短板容量固定。MAXSIZE 定得太小业务高峰期直接栈溢出定得太大平时又白白浪费一大片内存。链式栈就是为了解决这个问题存在的。链式栈本质上是“只能从一端插入/删除的单链表”。我们把链表的头结点位置作为栈顶这样入栈就是头插法出栈就是删除头结点后的第一个数据节点。#include stdio.h #include stdlib.h #include stdbool.h typedef struct StackNode { int data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; // 指向栈顶节点栈空时为 NULL int count; // 记录节点数方便获取长度可选 } LinkStack; // 初始化 void InitStack(LinkStack *s) { s-top NULL; s-count 0; } bool IsEmpty(LinkStack *s) { return s-top NULL; } // 入栈头插 void Push(LinkStack *s, int x) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (node NULL) { printf(内存分配失败\n); return; } node-data x; node-next s-top; s-top node; s-count; } // 出栈 bool Pop(LinkStack *s, int *x) { if (IsEmpty(s)) { printf(栈空无法出栈\n); return false; } StackNode *tmp s-top; *x tmp-data; s-top tmp-next; free(tmp); s-count--; return true; } int main() { LinkStack s; InitStack(s); Push(s, 10); Push(s, 20); Push(s, 30); int x; while (!IsEmpty(s)) { Pop(s, x); printf(%d , x); } // 输出30 20 10 return 0; }链式栈不用判满因为理论上只要内存够就能一直入栈但这也带来了新的注意点每个节点都是 malloc 出来的出栈后必须 free否则内存泄漏。有些同学平时练习代码量小泄漏一点无所谓可一旦放到服务端程序里跑几天内存占用就肉眼可见地往上涨最后 OOM 被系统杀掉。那到底选顺序栈还是链式栈我的建议很明确能预估到最大容量的场景比如编译器语法分析里嵌套深度有限的括号匹配用顺序栈容量不确定、可能动态增长比如实现浏览器的前进后退历史记录用链式栈。顺序栈胜在简单、连续内存访问快链式栈胜在灵活、不浪费两者各有主场。一道面试题如果是“请用栈实现某个功能”通常默认你可以选用任意一种但最好在代码里用注释说明你的选择理由——这会让面试官觉得你不仅会写代码还懂取舍。3. 栈的经典应用这些场景你每天都在用3.1 括号匹配不到30行代码解决的经典入门题括号匹配是栈最经典的入门应用。算法思路清晰简单从左到右扫描表达式遇到左括号就入栈遇到右括号就取出栈顶元素看是否匹配扫描完所有字符后如果栈为空说明所有括号都配对成功否则说明有多余的左括号。这里有个很容易被新手忽略的细节遇到右括号时如果栈本身就是空的那就说明右括号是多余的直接判定不匹配不用等扫描完再判断。很多同学只在最后判一次栈空把这种提前失败的情况漏了。下面是一份完整的代码#include stdio.h #include stdbool.h #include string.h #define MAXSIZE 100 typedef struct { char data[MAXSIZE]; int top; } CharStack; void InitStack(CharStack *s) { s-top -1; } bool IsEmpty(CharStack *s) { return s-top -1; } bool Push(CharStack *s, char c) { if (s-top MAXSIZE - 1) return false; s-top; s-data[s-top] c; return true; } bool Pop(CharStack *s, char *c) { if (IsEmpty(s)) return false; *c s-data[s-top]; s-top--; return true; } bool IsMatch(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool CheckBrackets(const char *expr) { CharStack s; InitStack(s); for (int i 0; i strlen(expr); i) { char c expr[i]; if (c ( || c [ || c {) { Push(s, c); } else if (c ) || c ] || c }) { char topChar; if (!Pop(s, topChar)) { return false; // 栈空却遇到右括号 } if (!IsMatch(topChar, c)) { return false; // 栈顶不匹配 } } // 其他字符直接忽略 } return IsEmpty(s); } int main() { const char *expr1 {[()()]}; const char *expr2 ([)]; printf(%s - %s\n, expr1, CheckBrackets(expr1) ? 匹配 : 不匹配); printf(%s - %s\n, expr2, CheckBrackets(expr2) ? 匹配 : 不匹配); // 输出 // {[()()]} - 匹配 // ([)] - 不匹配 return 0; }这段代码里有一处值得琢磨([)]这个例子左括号和右括号的数量都是两个但结果是不匹配。因为扫描到]时栈顶是((和]不是合法配对。很多初学者第一次写出这个用例都会觉得反直觉但这正是括号匹配和纯计数比如只统计左右括号数量相等的本质区别栈不仅关心数量还关心顺序。3.2 进制转换除基取余你手动算过的每一位都在入栈十进制转二进制最常规的手算方法是不断除以 2 取余数然后把余数倒着从下往上读。这个“倒着读”的动作就是栈的后进先出。比如把 13 转二进制13 ÷ 2 6 余 16 ÷ 2 3 余 03 ÷ 2 1 余 11 ÷ 2 0 余 1手算结果是 1101。你手动算的时候最后一个余数 1 最先被写下第一个余数 1 最后才被写下——换句话说余数是后产生的先被读取这不就是栈吗。实现的时候核心逻辑只需要三件事不断对进制数取余数入栈、更新商继续循环、循环结束后依次出栈输出。这里有一个正则表达式写多了容易踩的坑——如果转换目标大于 10比如十六进制余数会达到 10 到 15不能直接当字符用得做一层映射把 10 映射成 A11 映射成 B以此类推。这个应用虽然代码短但非常适合用来理解“栈到底解决了什么”。进制转换的核心需求是把一个序列逆序输出而逆序输出正是栈最擅长的场景。理解了这一点以后再看到“反转字符串”“判断回文”这类问题你第一反应就应该是栈。3.3 表达式求值中缀转后缀栈的完整作战演习如果说前两个应用是热身那么表达式求值就是栈的集大成者。你需要先理解后缀表达式逆波兰表达式为什么存在——因为计算机读中缀表达式像3 4 * 2时需要处理运算符优先级很麻烦而后缀表达式3 4 2 * 只用从左到右扫一遍遇到数字入栈遇到运算符弹出两个数计算后把结果入栈没有任何优先级问题。中缀转后缀的具体算法调度场算法本身就是一套栈操作修炼遇到操作数直接输出。遇到左括号入栈。遇到右括号弹出栈顶元素并输出直到遇到左括号左括号弹出但不输出。遇到运算符弹出栈中所有优先级高于或等于它的运算符并输出然后该运算符入栈。我把整个过程拆开看表达式3 4 * 2 - 1扫描过程是这样——数字 3 输出 入栈数字 4 输出*的优先级比栈顶高直接入栈数字 2 输出遇到-它的优先级比栈顶*低所以先把*弹出输出再把弹出输出-入栈数字 1 输出扫描结束把栈中剩余运算符依次弹出。最终得到后缀3 4 2 * 1 -。后缀表达式的计算过程同样用栈数字就入栈遇到运算符就弹出两个数字先弹出的放右边后弹出的放左边算完把结果压回栈。这里有个细节我反复强调运算时a - b和a / b的顺序不能反。如果弹出来的是p和q应该是p - q还是q - p正确答案是“先弹出的 op 后弹出的”。因为入栈顺序是左操作数先进、右操作数后进所以后弹出的才是左操作数。表达式求值这个应用的价值在于它把栈的“入栈、出栈、取栈顶、优先级判断”全都串起来了而且每一步都有明确的业务含义。做完这一题你对栈的理解基本就过关了。4. 实操中那些高频报错和排查心得4.1 段错误、栈溢出、逻辑错乱三个典型的翻车现场我见过最多的三种问题几乎每个写栈的人都会经历一次。第一种是段错误Segmentation Fault数组越界导致的。典型场景是顺序栈判满条件写错比如 top 初始化为 -1判满却写成top MAXSIZE结果最后几个元素写到了数组外面程序崩溃。排查思路很简单先确认判满条件maxsize 为 100 时top 的范围是 -1 到 99满了是 99不是 100。实在心虚就写个断言或者打印 top 值看它到底跑到哪了。第二种是栈溢出Stack Overflow。这里有两种情况大家容易混。一种是数据结构作业里“栈空间不够”那就是 MAXSIZE 太小改大或者换链式栈。另一种是程序运行时的调用栈溢出比如递归没有正确退出条件每次调用都往系统栈里压入一帧压到系统崩溃。这两种“栈”虽然都叫栈但前者是你自己定义的数据结构后者是系统维护的函数调用栈排查手段完全不同。前者打断点看 push 了多少次后者用调试器看调用栈帧数。第三种是逻辑错乱但程序不崩最典型的是出栈顺序不对或者取到的栈顶数据是脏值。这种问题九成出在指针上——初始化忘了把 top 设为 -1或者链式栈出栈时没有把节点的 next 接好。有一个我常用的调试手法在每个关键函数入口打印当前栈的状态比如打印 top 值和 data 数组的前几个元素。数据结构的代码只要允许我都建议加上 debug 输出这比在栈溢出的现场一步一步单步调试高效十倍。4.2 常见问题速查表直接照着排下面这张表是我平时带项目常用到的几乎把所有初学者踩过的坑都整理了进去问题现象可能原因排查思路输入数据后程序崩溃数组越界/判满条件错误检查 top 初始值和判满边界出栈顺序和预期相反栈顶指针写反了手推一次 push/pop 序列栈空时还在出栈没判空出栈前调用 IsEmpty链式栈内存一直涨出栈后没 free 节点检查 Pop 函数是否释放内存括号匹配漏判遇到右括号没先判栈空扫描过程中提前失败表达式结果错误运算符优先级处理错对照调度场算法逐步打印取到的栈顶是脏数据未初始化就使用InitStack 后确认 top 值这张表看着简单但每条背后都是实打实的调试时间。我自己的习惯是写完栈先不写主业务逻辑先写一个 10 行的测试用例push 三个数、pop 三个数打印结果。基础能力验证通过后再往上叠加括号匹配、表达式求值这些业务逻辑。模块化验证能让你把“栈本身的问题”和“应用逻辑的问题”快速分离不至于混在一起查半天。4.3 一个小技巧用空栈哨兵挡住一大半bug分享一个我用了很久的写栈小技巧在顺序栈里把数组的最后一个位置留一个“哨兵”叫它空栈哨兵也行叫它边界保护也好。实现上很简单初始化的时候多预留一个格子实际可用长度是MAXSIZE - 1。这样即使你判满写错数据也不会立刻越界到全程序的内存地盘而是会被哨兵位置接住调试时通过打印 top 位置更容易四两拨千斤定位到哪一步越界。这个技巧不是标准教材的写法但它确实降低了不少初学者的调试心理门槛。做数据结构项目时我总是鼓励大家在自己容易犯错的位置主动加一层“防御性编程”比如入栈前检查参数合法性、malloc 之后马上检查返回值。这些看起来多余的代码其实是在给未来的自己留后路。5. 栈这套逻辑学完还能往哪走5.1 递归与系统调用栈栈不只是你写的那个栈很多人学完栈之后以为它的应用就停留在作业和面试题里。其实还有一个更底层的舞台递归函数的背后就是系统在维护调用栈。每次函数调用都会把一个栈帧压入系统栈里面保存着参数、局部变量和返回地址函数返回时系统弹出这个栈帧程序接着上次的位置继续执行。理解了这个机制你就能解释很多“奇怪”的现象。比如递归深度过大为什么会段错误——不是你的代码逻辑写错了而是系统栈的容量是有限的递归一层层压帧终究会把栈空间耗尽这就是经典的栈溢出。手动模拟递归到非递归的转换本质上也经常是在用一个显式的栈替代隐式的系统调用栈。比如经典的非递归二叉树遍历就是程序员自己维护一个栈手动控制什么时候入栈、什么时候出栈而不是依赖函数递归系统帮我们压栈。5.2 浏览器、编辑器到操作系统栈是无处不在的基础设施栈的现实应用比想象中广泛得多。浏览器里的后退按钮保存的是你访问过的页面地址每次点击“后退”就是一次出栈操作。文本编辑器里的撤销功能记录的是每一次操作状态CtrlZ 就是在不断地弹出历史记录。操作系统里的函数调用、中断处理、任务切换底层全是栈在支撑。编译器做语法分析像括号匹配、作用域处理核心数据结构就是栈。甚至递归下降解析器里的调用关系也是靠栈来维护的。学完“数据结构1-2栈”这一小节别急着往下翻书。你可以自己动手把上面那几个应用写一遍比较顺序栈和链式栈的代码量、内存占用、边界条件差异。这个结构虽然小但它是你后续学习队列、树、图、算法设计的一条重要线索。把栈真正吃透后面很多东西学起来会顺很多。我在实际写代码的过程中最大的体会是栈题目写错九成不是不懂栈而是边界条件和指针管理没做好。所以每次写完先静下心把 push、pop 执行一遍手推流程把每一步 top 的变化写出来再跑程序。这个习惯救过我无数次。最后再分享一个可以立刻上手的练习用两个栈模拟一个队列。这个题目很多大厂面试都爱问思路不复杂但特别考验对栈操作的熟练度——一个栈管入队、一个栈管出队出队时如果第二个栈为空就把第一个栈的元素全部倒过去。这个题做熟了你对栈的理解就能真正内化成自己的东西了。
阅读完成 · 觉得有帮助？
