第一次写链栈的时候我盯着屏幕上那行top top-next;看了很久心里反复确认这样写前一个节点是不是就丢了后来画了三遍图、把每个指针的地址标出来才真正明白链表做栈为什么这么顺——它压根不需要找前驱这件事。这篇文章就把我踩过的那些坑、画过的那些图、以及后来带别人入门时总结的讲法一次讲透。链栈这个词听起来像两个知识点的拼接实际上它是数据结构入门阶段最能体现结构选择决定操作成本的案例同样是栈用数组做和用链表做代码只差几十行但背后的取舍完全不同。不管你是刚学完单链表、正准备啃栈和队列的初学者还是写了很多年代码但一直用现成容器、没自己实现过一遍的从业者下面这些内容都能直接拿去用——完整的可编译代码、参数选择依据、边界条件处理以及一份我整理的排查速查表。1. 链栈到底解决了什么问题先想清楚为什么用链表做栈很多人学链栈的第一反应是栈不是用数组做更简单吗为什么还要折腾链表这个问题如果不回答清楚后面的代码就只是抄写。我在教别人的时候习惯先让他们回答一个问题栈的核心操作只有三个——入栈、出栈、看栈顶而且全部发生在同一端。既然如此任何能在一端高效插入和删除的结构都能当栈用。数组可以链表也可以区别只在于它们各自的高效要付出什么代价。1.1 顺序栈的天花板在哪里顺序栈的本质是一个数组加一个栈顶下标。它的优点是内存连续、访问快、代码短一个int data[MAXSIZE]加一个int top就能跑起来。但它有个绕不过去的问题容量是提前定死的。你写MAXSIZE 100第 101 次入栈就得处理栈满要么报错拒绝要么扩容。扩容听起来不难——申请一块更大的数组把老数据拷贝过去释放老数组。但这里有两个隐藏成本初学者往往意识不到。第一是拷贝开销如果按每次加 1 的方式扩容n 次入栈的总拷贝量是 O(n²)这就是为什么工程上必须按倍数扩容通常是 2 倍才能把均摊成本摊到 O(1)。第二是峰值内存扩容的那一瞬间老数组和新数组同时存在内存占用会短暂翻倍甚至达到三倍在内存紧张的嵌入式环境里这是要命的。还有一个更隐蔽的问题顺序栈的栈满是一个假问题但它必须被处理。因为数组有物理上限你在每一处入栈调用后都得考虑返回值代码里会多出一堆if (isFull(s))的判断。链栈把这个判断直接消掉了——只要系统还能malloc出内存栈就能继续长。1.2 链表头插法天然就是栈链表做栈的关键洞察只有一句话栈是后进先出而单链表的头插法正好是后插的在最前面。你在头部插入一个新节点它立刻成为新的第一个节点你从头部删除一个节点删掉的正好是最后插入的那个。这两个动作在语义上和栈的 push/pop 完全重合连转换都不需要。反过来想一下就明白了为什么不能用链表的尾部当栈顶因为在单链表里删除尾部节点必须先找到它的前驱而找前驱要从头遍历是 O(n)。当然你可以再加一个尾指针但删除尾部之后尾指针要往前退一格单链表退不回去。所以单链表做栈头就是唯一正确的栈顶位置这不是习惯问题是结构决定的。我用一个生活场景类比一摞盘子你永远从最上面拿、往最上面放。数组做栈相当于给这摞盘子做了一个固定高度的架子架子满了就放不下了链表做栈相当于这摞盘子可以无限往上叠每叠一个就单独买一个盘子申请节点缺点是盘子之间没有挨着放找的时候得多跳一步。1.3 链栈的代价与选型对照链栈不是免费的。每个节点除了存数据还要额外存一个指针这就是空间开销。在 64 位系统上一个int数据加一个指针由于内存对齐结构体实际占 16 字节而数据本身只有 4 字节——空间利用率只有 25%。如果栈里存 100 万个 int链栈要吃大约 16MB顺序栈只要 4MB 左右。另外链栈的节点是malloc出来的地址分散在堆上CPU 缓存命中率天然不如连续数组每次入栈出栈都是一次堆操作比数组下标自增要慢。这些差异在小数据量下感觉不到但在高频交易、实时信号处理这类场景里是实打实的性能差距。我把两者的取舍整理成一张表这张表我建议初学者背下来面试和实际选型都用得上对比维度顺序栈数组链栈单链表容量固定需预判或扩容动态受限于可用内存入栈时间复杂度均摊 O(1)扩容时 O(n)O(1)但含一次 malloc出栈时间复杂度O(1)O(1)但含一次 free单元素额外开销无可能预留空位一个指针对齐后常翻倍内存连续性连续缓存友好分散缓存不友好栈满判断必须处理不需要只需判断申请失败典型适用场景容量可预估、追求性能容量波动大、无法预估上限注意不要因为链表高级就无脑选链栈。绝大多数业务场景里元素数量可控顺序栈或者语言自带的动态数组反而是更优解。链栈真正的价值在于上限完全未知和教学上理解指针操作这两点。2. 结构设计与关键参数栈顶指针到底该指向谁结构设计这一步初学者最容易糊弄过去结果后面每个函数都要重新想一遍top 现在指哪儿。我的建议是动笔写代码之前先在纸上定死三件事——节点长什么样、栈用什么类型表示、空栈长什么样。这三件事定下来后面的代码基本是顺着写。2.1 节点结构与栈类型的两种写法C 语言里最经典的写法是这样typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack;这里有两个细节值得说。第一struct StackNode *next里的struct关键字不能省因为此时StackNode这个 typedef 还没生效编译器不认识它。这是初学者最常见的编译错误之一报错信息通常是 unknown type name看着吓人其实就是少写了struct。第二LinkStack被定义成指针类型意味着LinkStack s;声明的就是一个指向节点的指针它可以直接当栈顶指针用。另一种写法是把栈封装成一个结构体里面只放一个栈顶指针typedef struct { LinkStack top; // 指向栈顶节点 int count; // 可选记录元素个数 } LinkStackObj;这两种写法的区别在于传参方式。第一种写法s本身就是栈顶指针函数里要修改它就得传LinkStack *二级指针第二种写法结构体变量本身的地址不变函数里传LinkStackObj *就能改内部的top用起来更清爽还能顺手存一个count让size()变成 O(1)。我个人在写教学代码时用第一种因为它最贴近链栈就是一条链的直觉写实际项目时用第二种因为扩展字段方便。count这个字段看起来可有可无但它能省掉一次遍历。如果没有它求栈长度的length()就得从头走到尾是 O(n)有了它每次入栈加一、出栈减一就是 O(1)。代价是多 4 字节和一个维护责任——忘记同步更新count就会得到一个永远错误的长度值这种 bug 特别难查因为栈本身的操作都是对的。2.2 带头结点与不带头结点的取舍这是链栈设计里分歧最大的一个点也是我看过最多人写错的地方。两种方案的差别在于链表中是否有一个永远存在、不存有效数据的头结点栈顶元素放在头结点之后的第一个位置。不带头结点的方案top直接指向栈顶元素节点。空栈时top NULL。入栈时新节点的next指向原top然后top指向新节点。出栈时先记下toptop后移一位再释放记下的那个节点。带头结点的方案top永远指向头结点栈顶元素在top-next。空栈时top-next NULL。入栈时新节点插在头结点之后出栈时删除头结点之后的那个节点。两者在时间复杂度上没有区别真正的差别在指针修改的位置。不带头结点时入栈和出栈都会修改top本身所以函数必须能改到调用者的top变量参数要写成LinkStack *函数体里全是(*s)-next这种二级指针解引用看着眼花。带头结点时top只在初始化时设定一次之后永远不变所有操作改的都是top-next参数只要传LinkStack就够了代码干净很多。对比项不带头结点带头结点空栈表示top NULLtop-next NULL入栈是否改 top是否函数参数LinkStack *sLinkStack s代码可读性稍差多二级指针好逻辑统一内存开销少一个节点多一个节点可忽略边界情况数量多空栈插入、删到空少逻辑统一提示考试和教材里两种都会出现所以两种都得会看。但自己写项目我建议用带头结点能少写一半的if (s NULL)判断出错概率低。下面第三节的实现我用不带头结点的版本因为它更能暴露指针的细节学明白了再换带头结点会很轻松。2.3 空栈、满栈的判断与容量上限空栈判断在不带头结点时就是top NULL一句话。满栈判断在链栈里根本不存在——没有满了这个概念只有申请内存失败。所以入栈函数里要判断的是malloc的返回值而不是什么容量上限。这里有个说法要纠正很多人说链栈不会溢出这话不严谨。链栈不会因为预设容量溢出但如果系统内存耗尽malloc会返回NULL此时入栈就失败了。区别在于顺序栈的失败是可预期的写代码时就知道上限是多少链栈的失败是运行时的、不可预期的。所以链栈的入栈函数应该返回一个状态值或布尔值让调用者知道这次入栈到底成没成功。还有一个容易混淆的点栈的长度和容量在链栈里是同一个概念的上界因为每个元素占一个节点长度可以一直涨到内存耗尽。所以你在写length()的时候不用担心越界只需要担心遍历时next指针是否合法。3. 动手实现入栈、出栈、取栈顶的完整代码下面这套代码我改过好多版最终留下来的版本特点是每个函数都有明确的返回值语义、所有malloc都判空、出栈一定free。你可以直接复制到本地编译运行。3.1 初始化与入栈初始化很简单就是把栈顶指针置空。但这一步千万不能省——如果是局部变量LinkStack s;里的s是随机值直接拿去判断s NULL可能恰好不为空后面一解引用就崩。#include stdio.h #include stdlib.h typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack; /* 初始化把栈顶指针置空 */ void InitStack(LinkStack *s) { *s NULL; } /* 判空 */ int StackEmpty(LinkStack s) { return s NULL; } /* 入栈成功返回 1失败返回 0 */ int Push(LinkStack *s, ElemType x) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; // 内存不足入栈失败 } newNode-data x; newNode-next *s; // 新节点指向原栈顶 *s newNode; // 栈顶指针前移到新节点 return 1; }Push里三行赋值的顺序是有讲究的这一点必须讲透。必须先把新节点的next指向原来的栈顶再把栈顶指针改成新节点。如果反过来写*s newNode; newNode-next *s; // 错此时 *s 已经是 newNode 自己了结果是newNode-next指向了它自己形成一个自环。整个栈就从这里断掉原来那一串节点全部泄漏而遍历时会陷入死循环。这个 bug 的特征是程序不崩溃但卡住非常难查。我见过有人在调试时打印了半小时才发现是自己指向自己。3.2 出栈与返回值设计的坑出栈要处理两件事把栈顶元素的值交出去把节点还给系统。顺序上必须先取值、再移动指针、最后free。/* 出栈成功返回 1 并通过 x 带回栈顶元素空栈返回 0 */ int Pop(LinkStack *s, ElemType *x) { if (*s NULL) { return 0; // 空栈出栈失败 } StackNode *p *s; // 记住要删除的节点 *x p-data; // 先取值 *s p-next; // 栈顶下移 free(p); // 再释放 return 1; }为什么参数要用ElemType *x而不是直接return数据这是个很实际的工程问题。如果函数签名写成ElemType Pop(LinkStack *s)那么当栈是空的、或者栈里存的元素本身就是 0 时调用者根本没法区分出栈成功得到 0和出栈失败。C 语言没有异常也没有可选类型所以只能约定一个专门的返回值通道。这种状态码 出参的模式在 C 库里到处都是值得养成习惯。你也可以设计成ElemType Pop(LinkStack *s)加上空栈时直接返回 0 并打印警告但这就是把错误处理藏起来了线上出问题时你会很痛苦。注意free(p)之后的p是悬空指针虽然它已经不再指向有效内存但在很多编译器下它仍然保留着原来的地址值。如果后面不小心又用了p-data程序可能不报错、也可能崩溃行为不可预测。养成习惯free(p); p NULL;。虽然后面不再用它但这是个好习惯。3.3 取栈顶、判空、销毁取栈顶就是看一眼不动结构/* 取栈顶元素成功返回 1空栈返回 0 */ int GetTop(LinkStack s, ElemType *x) { if (s NULL) { return 0; } *x s-data; return 1; }注意这里的参数s是值传递不是LinkStack *。因为取栈顶不改变栈顶指针传值就够了。很多人习惯性地全写成指针参数其实没必要还容易让人误以为函数会改结构。销毁栈要循环出栈不能只free栈顶/* 销毁整个栈 */ void DestroyStack(LinkStack *s) { StackNode *p *s; while (p ! NULL) { StackNode *next p-next; free(p); p next; } *s NULL; }这里的顺序同样是关键先用临时变量next记住下一个节点再free(p)最后让p指向next。如果先free(p)再访问p-next那就是在访问已释放的内存属于未定义行为程序可能在小数据量下看起来正常换成大一点的数据或者在开启内存检测工具时就崩了。这种看起来能跑的 bug 是最可怕的。3.4 完整可跑示例与运行记录把上面拼起来加一个从栈顶到栈底打印的辅助函数就能验证了/* 从栈顶到栈底打印仅用于调试 */ void PrintStack(LinkStack s) { printf(栈顶 - ); for (StackNode *p s; p ! NULL; p p-next) { printf(%d , p-data); } printf(- 栈底\n); } int main(void) { LinkStack s; InitStack(s); printf(空栈判断: %d\n, StackEmpty(s)); Push(s, 10); Push(s, 20); Push(s, 30); PrintStack(s); // 期望栈顶 - 30 20 10 - 栈底 ElemType x; if (GetTop(s, x)) printf(当前栈顶: %d\n, x); if (Pop(s, x)) printf(出栈元素: %d\n, x); PrintStack(s); // 期望栈顶 - 20 10 - 栈底 if (Pop(s, x)) printf(出栈元素: %d\n, x); if (Pop(s, x)) printf(出栈元素: %d\n, x); printf(出栈后再判空: %d\n, StackEmpty(s)); if (!Pop(s, x)) printf(空栈出栈被正确拦截\n); DestroyStack(s); return 0; }实测输出空栈判断: 1 栈顶 - 30 20 10 - 栈底 当前栈顶: 30 出栈元素: 30 栈顶 - 20 10 - 栈底 出栈元素: 20 出栈元素: 10 出栈后再判空: 1 空栈出栈被正确拦截看到栈顶 - 30 20 10这个顺序时很多人会愣一下我先入的 10为什么打印出来是 30 在最前面这不是 bug恰恰说明结构是对的——栈顶就在链表头部所以从头部遍历出来的顺序天然是后进先出的倒序。如果你的打印结果是 10 20 30那才是出问题了说明你把新节点接到了链表尾部。这个打印顺序反直觉的现象是我带初学者时他们最常提出的疑问记住这一点后面的理解会顺很多。4. 常见问题与排查实录链栈的代码量很小但坑很集中几乎全部集中在指针上。我把这些年见过的、自己犯过的问题按症状分类整理了一遍你可以把它当成写不出来时的对照清单。4.1 段错误与野指针速查症状一程序一入栈就崩报 Segmentation fault。最常见原因是栈变量没初始化。LinkStack s;声明之后直接Push(s, 1)此时s是个随机值Push里执行newNode-next *s只是把随机值拷过去暂时没崩等PrintStack遍历时顺着这个随机地址走迟早踩到非法内存。解决办法就一行InitStack(s)或者干脆写LinkStack s NULL;。症状二出栈几次之后崩。检查Pop里是不是漏了*s p-next这一步。如果只free(p)不移动指针下一次Pop拿到的还是同一块已经释放的内存p-data是脏数据p-next可能是任意值于是崩溃。这个错误在单次出栈时往往看不出来连出三次必炸。症状三程序跑完不崩但退出时内存检测工具报泄漏。说明有节点没被释放。重点查两处Pop里有没有freeDestroyStack有没有在main结束前被调用。链栈的节点是堆内存程序结束不会自动回收现代操作系统会回收但那是兜底不是你的代码正确。症状四malloc返回 NULL 之后继续用。理论上很少触发但如果你在一个循环里连续入栈几百万次是有可能的。养成判空的习惯成本只有一行。4.2 数据逻辑错误的典型症状比崩溃更麻烦的是不崩但结果不对。症状五打印出来的顺序和入栈顺序一致。这说明你写成了尾插。有人为了让打印好看特意在链表尾部维护了一个指针用 tail 做栈顶结果入栈的时候确实 O(1)出栈时发现删不掉——因为删除尾节点需要前驱而单链表回不去。这个方案的补救办法是把链表改成双向链表但那样空间开销又翻倍了完全违背了用链栈的初衷。症状六栈长度永远差一。通常是count字段维护漏了某条路径比如入栈成功但没加一或者出栈失败却减了一。我的建议是如果只是教学别加count用length()遍历虽然慢但不会错如果确实要 O(1) 求长度就把count的加减紧挨着指针操作写别隔开几行。症状七连续入栈出栈后取栈顶拿到的值不对。检查GetTop的实现是不是传了值却按指针用或者反过来。GetTop(LinkStack s, ElemType *x)里如果写成s s-next那只是改了个局部副本栈本身没事但你会以为取到的是下下个元素。4.3 问题速查表下面这张表我打印出来贴在显示器边上过新手阶段查错效率能提高不少现象最可能的原因定位方法修法一运行就段错误栈顶指针未初始化printf(%p, s)看是否为 NULL加InitStack出栈几次后崩溃出栈未移动栈顶指针在Pop里打印p和*s补*s p-next打印顺序与入栈同序误用尾插法看Push里新节点挂在哪改成头插遍历陷入死循环节点next指向自己打印每个节点地址检查赋值顺序内存泄漏告警Pop或销毁漏free用内存检测工具跑一遍补齐释放逻辑栈顶值始终是第一个元素Push里没更新*s单步入栈三行代码最后一行改为*s newNode长度为 0 但栈非空count未同步在加减处下断点与指针操作绑定提示调试指针类代码我强烈建议打开地址打印功能把每次操作的节点地址和next值打出来和纸上画的图对一遍。地址对了逻辑就对了地址不对再怎么盯着代码看也没用。5. 从链栈延伸多语言写法与实际应用场景把 C 版本写通之后再看其他语言的实现会非常快因为你会发现语言内置的栈其实都是同一套思路的不同包装。这一节我顺手对比几种常见写法也说说链栈在真实场景里到底站在什么位置。5.1 用 Java、Go、Python 各写一遍看差异Java 里如果要用链表做栈最直接的是自己写节点class Node { int data; Node next; Node(int data) { this.data data; } } class LinkedStack { private Node top; private int size; void push(int x) { Node n new Node(x); n.next top; top n; size; } int pop() { if (top null) throw new IllegalStateException(栈为空); int v top.data; top top.next; size--; return v; } int peek() { if (top null) throw new IllegalStateException(栈为空); return top.data; } boolean isEmpty() { return top null; } int size() { return size; } }Java 里有个细节和 C 不同出栈不需要手动释放内存垃圾回收器会处理top移走之后那个孤立节点。所以pop只需要三行没有free也就没有释放后还被访问这类 bug。这是托管语言的优势但代价是你失去了对内存布局的控制每个节点都是一个独立对象对象头开销比 C 的指针还大。Go 和 Python 的写法更短。Go 里用container/list可以做出链栈但更常见的是直接用切片当栈type IntStack struct { items []int } func (s *IntStack) Push(x int) { s.items append(s.items, x) } func (s *IntStack) Pop() (int, bool) { if len(s.items) 0 { return 0, false } x : s.items[len(s.items)-1] s.items s.items[:len(s.items)-1] return x, true }Python 更简单list的append和pop()天然就是栈stack [] stack.append(10) stack.append(20) top stack.pop() # 20 empty not stack这里有个认知上的转换值得说Go 的切片和 Python 的列表在底层其实就是会自动扩容的顺序栈它们把扩容逻辑封装起来了所以用起来像无限容量的栈。这也从侧面说明工程实践中顺序栈才是绝大多数场景的默认答案链栈更多出现在必须手动管理内存或者教学演示的场合。如果你非要在 Python 里实现链栈也完全可以只是不建议用在生产代码里——Python 对象本身的开销远大于一个指针用链表存整数时内存占用会比list高出好几倍得不偿失。写出来当练习没问题能加深对指针的理解。5.2 链栈在真实场景里的位置栈这个结构在实际系统里到处都是我举几个你能对上号的例子。括号匹配检查。编译器和编辑器做语法高亮、格式校验时遇到左括号就入栈遇到右括号就出栈比对类型。这里元素数量一般不大但理论上可以无限嵌套用链栈就完全不用考虑嵌套太深超容量的问题。这个例子的经典度很高基本上每本教材都会拿它当链栈的第一个应用。表达式求值与中缀转后缀。计算器、SQL 解析器、规则引擎里的表达式求值都要用到运算符栈。运算符的数量很小顺序栈完全够用但如果表达式是运行时动态拼接的、长度不可预期链栈就更稳。撤销操作的实现。文本编辑器、图像处理的撤销历史本质就是一个栈每一步操作压进去撤销时弹出来。这里的容量问题很现实用户可能连续操作几万次如果你用一个固定 100 深的数组栈超过就丢历史体验很差而全存下来又可能吃光内存。所以工程上常见的是链式结构 容量上限 超限淘汰栈底这时候你就需要链栈这个基础形态去做扩展。递归转非递归。树的深度优先遍历、快速排序的非递归版本都要自己维护一个栈来存待处理节点。递归深度可能很浅也可能很深链栈在这里的意义就是不用担心栈的空间上限。当然你要注意这里的栈是你自己申请的堆内存和函数调用栈不是一回事别混淆。函数调用栈和表达式栈的关系。这一点常被问到函数调用栈是不是链栈不是。现代系统的函数调用栈是操作系统分配的连续内存区域用的是栈指针寄存器加偏移本质上是顺序栈。理解这一点很重要能让你区分数据结构课上的栈和系统实现里的栈。把这些场景过一遍你会发现选择链栈的判断标准其实很朴素元素数量完全不可预估且不能接受栈满这种失败那就用链栈其余情况优先用顺序结构。这个判断标准我用了很多年几乎没出过偏差。我先说个自己的习惯现在再写链栈我第一步不是敲代码而是拿张纸画三个方框标上top、节点 A、节点 B然后把入栈和出栈各走一遍一边走一边写出指针的赋值顺序。这个动作花不了两分钟但能避免后面半小时的调试。指针类代码的错误率和你动手前画图的次数是强相关的这话我验证过很多次。如果你的链栈写出来跑不对先别急着改代码把图重画一遍八成问题在图上就能看出来。
第一次写链栈的时候我盯着屏幕上那行top top-next;看了很久心里反复确认这样写前一个节点是不是就丢了后来画了三遍图、把每个指针的地址标出来才真正明白链表做栈为什么这么顺——它压根不需要找前驱这件事。这篇文章就把我踩过的那些坑、画过的那些图、以及后来带别人入门时总结的讲法一次讲透。链栈这个词听起来像两个知识点的拼接实际上它是数据结构入门阶段最能体现结构选择决定操作成本的案例同样是栈用数组做和用链表做代码只差几十行但背后的取舍完全不同。不管你是刚学完单链表、正准备啃栈和队列的初学者还是写了很多年代码但一直用现成容器、没自己实现过一遍的从业者下面这些内容都能直接拿去用——完整的可编译代码、参数选择依据、边界条件处理以及一份我整理的排查速查表。1. 链栈到底解决了什么问题先想清楚为什么用链表做栈很多人学链栈的第一反应是栈不是用数组做更简单吗为什么还要折腾链表这个问题如果不回答清楚后面的代码就只是抄写。我在教别人的时候习惯先让他们回答一个问题栈的核心操作只有三个——入栈、出栈、看栈顶而且全部发生在同一端。既然如此任何能在一端高效插入和删除的结构都能当栈用。数组可以链表也可以区别只在于它们各自的高效要付出什么代价。1.1 顺序栈的天花板在哪里顺序栈的本质是一个数组加一个栈顶下标。它的优点是内存连续、访问快、代码短一个int data[MAXSIZE]加一个int top就能跑起来。但它有个绕不过去的问题容量是提前定死的。你写MAXSIZE 100第 101 次入栈就得处理栈满要么报错拒绝要么扩容。扩容听起来不难——申请一块更大的数组把老数据拷贝过去释放老数组。但这里有两个隐藏成本初学者往往意识不到。第一是拷贝开销如果按每次加 1 的方式扩容n 次入栈的总拷贝量是 O(n²)这就是为什么工程上必须按倍数扩容通常是 2 倍才能把均摊成本摊到 O(1)。第二是峰值内存扩容的那一瞬间老数组和新数组同时存在内存占用会短暂翻倍甚至达到三倍在内存紧张的嵌入式环境里这是要命的。还有一个更隐蔽的问题顺序栈的栈满是一个假问题但它必须被处理。因为数组有物理上限你在每一处入栈调用后都得考虑返回值代码里会多出一堆if (isFull(s))的判断。链栈把这个判断直接消掉了——只要系统还能malloc出内存栈就能继续长。1.2 链表头插法天然就是栈链表做栈的关键洞察只有一句话栈是后进先出而单链表的头插法正好是后插的在最前面。你在头部插入一个新节点它立刻成为新的第一个节点你从头部删除一个节点删掉的正好是最后插入的那个。这两个动作在语义上和栈的 push/pop 完全重合连转换都不需要。反过来想一下就明白了为什么不能用链表的尾部当栈顶因为在单链表里删除尾部节点必须先找到它的前驱而找前驱要从头遍历是 O(n)。当然你可以再加一个尾指针但删除尾部之后尾指针要往前退一格单链表退不回去。所以单链表做栈头就是唯一正确的栈顶位置这不是习惯问题是结构决定的。我用一个生活场景类比一摞盘子你永远从最上面拿、往最上面放。数组做栈相当于给这摞盘子做了一个固定高度的架子架子满了就放不下了链表做栈相当于这摞盘子可以无限往上叠每叠一个就单独买一个盘子申请节点缺点是盘子之间没有挨着放找的时候得多跳一步。1.3 链栈的代价与选型对照链栈不是免费的。每个节点除了存数据还要额外存一个指针这就是空间开销。在 64 位系统上一个int数据加一个指针由于内存对齐结构体实际占 16 字节而数据本身只有 4 字节——空间利用率只有 25%。如果栈里存 100 万个 int链栈要吃大约 16MB顺序栈只要 4MB 左右。另外链栈的节点是malloc出来的地址分散在堆上CPU 缓存命中率天然不如连续数组每次入栈出栈都是一次堆操作比数组下标自增要慢。这些差异在小数据量下感觉不到但在高频交易、实时信号处理这类场景里是实打实的性能差距。我把两者的取舍整理成一张表这张表我建议初学者背下来面试和实际选型都用得上对比维度顺序栈数组链栈单链表容量固定需预判或扩容动态受限于可用内存入栈时间复杂度均摊 O(1)扩容时 O(n)O(1)但含一次 malloc出栈时间复杂度O(1)O(1)但含一次 free单元素额外开销无可能预留空位一个指针对齐后常翻倍内存连续性连续缓存友好分散缓存不友好栈满判断必须处理不需要只需判断申请失败典型适用场景容量可预估、追求性能容量波动大、无法预估上限注意不要因为链表高级就无脑选链栈。绝大多数业务场景里元素数量可控顺序栈或者语言自带的动态数组反而是更优解。链栈真正的价值在于上限完全未知和教学上理解指针操作这两点。2. 结构设计与关键参数栈顶指针到底该指向谁结构设计这一步初学者最容易糊弄过去结果后面每个函数都要重新想一遍top 现在指哪儿。我的建议是动笔写代码之前先在纸上定死三件事——节点长什么样、栈用什么类型表示、空栈长什么样。这三件事定下来后面的代码基本是顺着写。2.1 节点结构与栈类型的两种写法C 语言里最经典的写法是这样typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack;这里有两个细节值得说。第一struct StackNode *next里的struct关键字不能省因为此时StackNode这个 typedef 还没生效编译器不认识它。这是初学者最常见的编译错误之一报错信息通常是 unknown type name看着吓人其实就是少写了struct。第二LinkStack被定义成指针类型意味着LinkStack s;声明的就是一个指向节点的指针它可以直接当栈顶指针用。另一种写法是把栈封装成一个结构体里面只放一个栈顶指针typedef struct { LinkStack top; // 指向栈顶节点 int count; // 可选记录元素个数 } LinkStackObj;这两种写法的区别在于传参方式。第一种写法s本身就是栈顶指针函数里要修改它就得传LinkStack *二级指针第二种写法结构体变量本身的地址不变函数里传LinkStackObj *就能改内部的top用起来更清爽还能顺手存一个count让size()变成 O(1)。我个人在写教学代码时用第一种因为它最贴近链栈就是一条链的直觉写实际项目时用第二种因为扩展字段方便。count这个字段看起来可有可无但它能省掉一次遍历。如果没有它求栈长度的length()就得从头走到尾是 O(n)有了它每次入栈加一、出栈减一就是 O(1)。代价是多 4 字节和一个维护责任——忘记同步更新count就会得到一个永远错误的长度值这种 bug 特别难查因为栈本身的操作都是对的。2.2 带头结点与不带头结点的取舍这是链栈设计里分歧最大的一个点也是我看过最多人写错的地方。两种方案的差别在于链表中是否有一个永远存在、不存有效数据的头结点栈顶元素放在头结点之后的第一个位置。不带头结点的方案top直接指向栈顶元素节点。空栈时top NULL。入栈时新节点的next指向原top然后top指向新节点。出栈时先记下toptop后移一位再释放记下的那个节点。带头结点的方案top永远指向头结点栈顶元素在top-next。空栈时top-next NULL。入栈时新节点插在头结点之后出栈时删除头结点之后的那个节点。两者在时间复杂度上没有区别真正的差别在指针修改的位置。不带头结点时入栈和出栈都会修改top本身所以函数必须能改到调用者的top变量参数要写成LinkStack *函数体里全是(*s)-next这种二级指针解引用看着眼花。带头结点时top只在初始化时设定一次之后永远不变所有操作改的都是top-next参数只要传LinkStack就够了代码干净很多。对比项不带头结点带头结点空栈表示top NULLtop-next NULL入栈是否改 top是否函数参数LinkStack *sLinkStack s代码可读性稍差多二级指针好逻辑统一内存开销少一个节点多一个节点可忽略边界情况数量多空栈插入、删到空少逻辑统一提示考试和教材里两种都会出现所以两种都得会看。但自己写项目我建议用带头结点能少写一半的if (s NULL)判断出错概率低。下面第三节的实现我用不带头结点的版本因为它更能暴露指针的细节学明白了再换带头结点会很轻松。2.3 空栈、满栈的判断与容量上限空栈判断在不带头结点时就是top NULL一句话。满栈判断在链栈里根本不存在——没有满了这个概念只有申请内存失败。所以入栈函数里要判断的是malloc的返回值而不是什么容量上限。这里有个说法要纠正很多人说链栈不会溢出这话不严谨。链栈不会因为预设容量溢出但如果系统内存耗尽malloc会返回NULL此时入栈就失败了。区别在于顺序栈的失败是可预期的写代码时就知道上限是多少链栈的失败是运行时的、不可预期的。所以链栈的入栈函数应该返回一个状态值或布尔值让调用者知道这次入栈到底成没成功。还有一个容易混淆的点栈的长度和容量在链栈里是同一个概念的上界因为每个元素占一个节点长度可以一直涨到内存耗尽。所以你在写length()的时候不用担心越界只需要担心遍历时next指针是否合法。3. 动手实现入栈、出栈、取栈顶的完整代码下面这套代码我改过好多版最终留下来的版本特点是每个函数都有明确的返回值语义、所有malloc都判空、出栈一定free。你可以直接复制到本地编译运行。3.1 初始化与入栈初始化很简单就是把栈顶指针置空。但这一步千万不能省——如果是局部变量LinkStack s;里的s是随机值直接拿去判断s NULL可能恰好不为空后面一解引用就崩。#include stdio.h #include stdlib.h typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack; /* 初始化把栈顶指针置空 */ void InitStack(LinkStack *s) { *s NULL; } /* 判空 */ int StackEmpty(LinkStack s) { return s NULL; } /* 入栈成功返回 1失败返回 0 */ int Push(LinkStack *s, ElemType x) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; // 内存不足入栈失败 } newNode-data x; newNode-next *s; // 新节点指向原栈顶 *s newNode; // 栈顶指针前移到新节点 return 1; }Push里三行赋值的顺序是有讲究的这一点必须讲透。必须先把新节点的next指向原来的栈顶再把栈顶指针改成新节点。如果反过来写*s newNode; newNode-next *s; // 错此时 *s 已经是 newNode 自己了结果是newNode-next指向了它自己形成一个自环。整个栈就从这里断掉原来那一串节点全部泄漏而遍历时会陷入死循环。这个 bug 的特征是程序不崩溃但卡住非常难查。我见过有人在调试时打印了半小时才发现是自己指向自己。3.2 出栈与返回值设计的坑出栈要处理两件事把栈顶元素的值交出去把节点还给系统。顺序上必须先取值、再移动指针、最后free。/* 出栈成功返回 1 并通过 x 带回栈顶元素空栈返回 0 */ int Pop(LinkStack *s, ElemType *x) { if (*s NULL) { return 0; // 空栈出栈失败 } StackNode *p *s; // 记住要删除的节点 *x p-data; // 先取值 *s p-next; // 栈顶下移 free(p); // 再释放 return 1; }为什么参数要用ElemType *x而不是直接return数据这是个很实际的工程问题。如果函数签名写成ElemType Pop(LinkStack *s)那么当栈是空的、或者栈里存的元素本身就是 0 时调用者根本没法区分出栈成功得到 0和出栈失败。C 语言没有异常也没有可选类型所以只能约定一个专门的返回值通道。这种状态码 出参的模式在 C 库里到处都是值得养成习惯。你也可以设计成ElemType Pop(LinkStack *s)加上空栈时直接返回 0 并打印警告但这就是把错误处理藏起来了线上出问题时你会很痛苦。注意free(p)之后的p是悬空指针虽然它已经不再指向有效内存但在很多编译器下它仍然保留着原来的地址值。如果后面不小心又用了p-data程序可能不报错、也可能崩溃行为不可预测。养成习惯free(p); p NULL;。虽然后面不再用它但这是个好习惯。3.3 取栈顶、判空、销毁取栈顶就是看一眼不动结构/* 取栈顶元素成功返回 1空栈返回 0 */ int GetTop(LinkStack s, ElemType *x) { if (s NULL) { return 0; } *x s-data; return 1; }注意这里的参数s是值传递不是LinkStack *。因为取栈顶不改变栈顶指针传值就够了。很多人习惯性地全写成指针参数其实没必要还容易让人误以为函数会改结构。销毁栈要循环出栈不能只free栈顶/* 销毁整个栈 */ void DestroyStack(LinkStack *s) { StackNode *p *s; while (p ! NULL) { StackNode *next p-next; free(p); p next; } *s NULL; }这里的顺序同样是关键先用临时变量next记住下一个节点再free(p)最后让p指向next。如果先free(p)再访问p-next那就是在访问已释放的内存属于未定义行为程序可能在小数据量下看起来正常换成大一点的数据或者在开启内存检测工具时就崩了。这种看起来能跑的 bug 是最可怕的。3.4 完整可跑示例与运行记录把上面拼起来加一个从栈顶到栈底打印的辅助函数就能验证了/* 从栈顶到栈底打印仅用于调试 */ void PrintStack(LinkStack s) { printf(栈顶 - ); for (StackNode *p s; p ! NULL; p p-next) { printf(%d , p-data); } printf(- 栈底\n); } int main(void) { LinkStack s; InitStack(s); printf(空栈判断: %d\n, StackEmpty(s)); Push(s, 10); Push(s, 20); Push(s, 30); PrintStack(s); // 期望栈顶 - 30 20 10 - 栈底 ElemType x; if (GetTop(s, x)) printf(当前栈顶: %d\n, x); if (Pop(s, x)) printf(出栈元素: %d\n, x); PrintStack(s); // 期望栈顶 - 20 10 - 栈底 if (Pop(s, x)) printf(出栈元素: %d\n, x); if (Pop(s, x)) printf(出栈元素: %d\n, x); printf(出栈后再判空: %d\n, StackEmpty(s)); if (!Pop(s, x)) printf(空栈出栈被正确拦截\n); DestroyStack(s); return 0; }实测输出空栈判断: 1 栈顶 - 30 20 10 - 栈底 当前栈顶: 30 出栈元素: 30 栈顶 - 20 10 - 栈底 出栈元素: 20 出栈元素: 10 出栈后再判空: 1 空栈出栈被正确拦截看到栈顶 - 30 20 10这个顺序时很多人会愣一下我先入的 10为什么打印出来是 30 在最前面这不是 bug恰恰说明结构是对的——栈顶就在链表头部所以从头部遍历出来的顺序天然是后进先出的倒序。如果你的打印结果是 10 20 30那才是出问题了说明你把新节点接到了链表尾部。这个打印顺序反直觉的现象是我带初学者时他们最常提出的疑问记住这一点后面的理解会顺很多。4. 常见问题与排查实录链栈的代码量很小但坑很集中几乎全部集中在指针上。我把这些年见过的、自己犯过的问题按症状分类整理了一遍你可以把它当成写不出来时的对照清单。4.1 段错误与野指针速查症状一程序一入栈就崩报 Segmentation fault。最常见原因是栈变量没初始化。LinkStack s;声明之后直接Push(s, 1)此时s是个随机值Push里执行newNode-next *s只是把随机值拷过去暂时没崩等PrintStack遍历时顺着这个随机地址走迟早踩到非法内存。解决办法就一行InitStack(s)或者干脆写LinkStack s NULL;。症状二出栈几次之后崩。检查Pop里是不是漏了*s p-next这一步。如果只free(p)不移动指针下一次Pop拿到的还是同一块已经释放的内存p-data是脏数据p-next可能是任意值于是崩溃。这个错误在单次出栈时往往看不出来连出三次必炸。症状三程序跑完不崩但退出时内存检测工具报泄漏。说明有节点没被释放。重点查两处Pop里有没有freeDestroyStack有没有在main结束前被调用。链栈的节点是堆内存程序结束不会自动回收现代操作系统会回收但那是兜底不是你的代码正确。症状四malloc返回 NULL 之后继续用。理论上很少触发但如果你在一个循环里连续入栈几百万次是有可能的。养成判空的习惯成本只有一行。4.2 数据逻辑错误的典型症状比崩溃更麻烦的是不崩但结果不对。症状五打印出来的顺序和入栈顺序一致。这说明你写成了尾插。有人为了让打印好看特意在链表尾部维护了一个指针用 tail 做栈顶结果入栈的时候确实 O(1)出栈时发现删不掉——因为删除尾节点需要前驱而单链表回不去。这个方案的补救办法是把链表改成双向链表但那样空间开销又翻倍了完全违背了用链栈的初衷。症状六栈长度永远差一。通常是count字段维护漏了某条路径比如入栈成功但没加一或者出栈失败却减了一。我的建议是如果只是教学别加count用length()遍历虽然慢但不会错如果确实要 O(1) 求长度就把count的加减紧挨着指针操作写别隔开几行。症状七连续入栈出栈后取栈顶拿到的值不对。检查GetTop的实现是不是传了值却按指针用或者反过来。GetTop(LinkStack s, ElemType *x)里如果写成s s-next那只是改了个局部副本栈本身没事但你会以为取到的是下下个元素。4.3 问题速查表下面这张表我打印出来贴在显示器边上过新手阶段查错效率能提高不少现象最可能的原因定位方法修法一运行就段错误栈顶指针未初始化printf(%p, s)看是否为 NULL加InitStack出栈几次后崩溃出栈未移动栈顶指针在Pop里打印p和*s补*s p-next打印顺序与入栈同序误用尾插法看Push里新节点挂在哪改成头插遍历陷入死循环节点next指向自己打印每个节点地址检查赋值顺序内存泄漏告警Pop或销毁漏free用内存检测工具跑一遍补齐释放逻辑栈顶值始终是第一个元素Push里没更新*s单步入栈三行代码最后一行改为*s newNode长度为 0 但栈非空count未同步在加减处下断点与指针操作绑定提示调试指针类代码我强烈建议打开地址打印功能把每次操作的节点地址和next值打出来和纸上画的图对一遍。地址对了逻辑就对了地址不对再怎么盯着代码看也没用。5. 从链栈延伸多语言写法与实际应用场景把 C 版本写通之后再看其他语言的实现会非常快因为你会发现语言内置的栈其实都是同一套思路的不同包装。这一节我顺手对比几种常见写法也说说链栈在真实场景里到底站在什么位置。5.1 用 Java、Go、Python 各写一遍看差异Java 里如果要用链表做栈最直接的是自己写节点class Node { int data; Node next; Node(int data) { this.data data; } } class LinkedStack { private Node top; private int size; void push(int x) { Node n new Node(x); n.next top; top n; size; } int pop() { if (top null) throw new IllegalStateException(栈为空); int v top.data; top top.next; size--; return v; } int peek() { if (top null) throw new IllegalStateException(栈为空); return top.data; } boolean isEmpty() { return top null; } int size() { return size; } }Java 里有个细节和 C 不同出栈不需要手动释放内存垃圾回收器会处理top移走之后那个孤立节点。所以pop只需要三行没有free也就没有释放后还被访问这类 bug。这是托管语言的优势但代价是你失去了对内存布局的控制每个节点都是一个独立对象对象头开销比 C 的指针还大。Go 和 Python 的写法更短。Go 里用container/list可以做出链栈但更常见的是直接用切片当栈type IntStack struct { items []int } func (s *IntStack) Push(x int) { s.items append(s.items, x) } func (s *IntStack) Pop() (int, bool) { if len(s.items) 0 { return 0, false } x : s.items[len(s.items)-1] s.items s.items[:len(s.items)-1] return x, true }Python 更简单list的append和pop()天然就是栈stack [] stack.append(10) stack.append(20) top stack.pop() # 20 empty not stack这里有个认知上的转换值得说Go 的切片和 Python 的列表在底层其实就是会自动扩容的顺序栈它们把扩容逻辑封装起来了所以用起来像无限容量的栈。这也从侧面说明工程实践中顺序栈才是绝大多数场景的默认答案链栈更多出现在必须手动管理内存或者教学演示的场合。如果你非要在 Python 里实现链栈也完全可以只是不建议用在生产代码里——Python 对象本身的开销远大于一个指针用链表存整数时内存占用会比list高出好几倍得不偿失。写出来当练习没问题能加深对指针的理解。5.2 链栈在真实场景里的位置栈这个结构在实际系统里到处都是我举几个你能对上号的例子。括号匹配检查。编译器和编辑器做语法高亮、格式校验时遇到左括号就入栈遇到右括号就出栈比对类型。这里元素数量一般不大但理论上可以无限嵌套用链栈就完全不用考虑嵌套太深超容量的问题。这个例子的经典度很高基本上每本教材都会拿它当链栈的第一个应用。表达式求值与中缀转后缀。计算器、SQL 解析器、规则引擎里的表达式求值都要用到运算符栈。运算符的数量很小顺序栈完全够用但如果表达式是运行时动态拼接的、长度不可预期链栈就更稳。撤销操作的实现。文本编辑器、图像处理的撤销历史本质就是一个栈每一步操作压进去撤销时弹出来。这里的容量问题很现实用户可能连续操作几万次如果你用一个固定 100 深的数组栈超过就丢历史体验很差而全存下来又可能吃光内存。所以工程上常见的是链式结构 容量上限 超限淘汰栈底这时候你就需要链栈这个基础形态去做扩展。递归转非递归。树的深度优先遍历、快速排序的非递归版本都要自己维护一个栈来存待处理节点。递归深度可能很浅也可能很深链栈在这里的意义就是不用担心栈的空间上限。当然你要注意这里的栈是你自己申请的堆内存和函数调用栈不是一回事别混淆。函数调用栈和表达式栈的关系。这一点常被问到函数调用栈是不是链栈不是。现代系统的函数调用栈是操作系统分配的连续内存区域用的是栈指针寄存器加偏移本质上是顺序栈。理解这一点很重要能让你区分数据结构课上的栈和系统实现里的栈。把这些场景过一遍你会发现选择链栈的判断标准其实很朴素元素数量完全不可预估且不能接受栈满这种失败那就用链栈其余情况优先用顺序结构。这个判断标准我用了很多年几乎没出过偏差。我先说个自己的习惯现在再写链栈我第一步不是敲代码而是拿张纸画三个方框标上top、节点 A、节点 B然后把入栈和出栈各走一遍一边走一边写出指针的赋值顺序。这个动作花不了两分钟但能避免后面半小时的调试。指针类代码的错误率和你动手前画图的次数是强相关的这话我验证过很多次。如果你的链栈写出来跑不对先别急着改代码把图重画一遍八成问题在图上就能看出来。
