学数据结构学到栈这一章很多人是从顺序栈开始的一个数组加一个栈顶下标写起来确实顺手。但真正上手写项目、做表达式求值、做括号匹配、做编辑器撤销功能的时候顺序栈的固定容量很快就会变成一根刺——栈满了要扩容扩容就得重新申请内存、搬数据稍不留神老指针就悬空了。链栈就是为了绕开这类麻烦出现的结构它把栈顶放在单链表的头部入栈出栈都在表头完成容量跟着节点走理论上只要有内存就能一直压。这篇内容面向刚学完链表、准备啃链栈的初学者也适合那些写过一遍但总觉得心里没底的读者我会从结构设计的取舍讲到一行行代码落地再把我自己踩过的坑和排查思路摊开来说尽量让你看完就能自己默写出来而不是背完就忘。1. 链栈到底解决什么问题从顺序栈的边界说起1.1 顺序栈为什么会在实战里让人难受顺序栈的本质是一段连续内存加一个栈顶位置标记。它的优点是访问快、结构简单、代码短教学演示里几乎无懈可击。但只要你把它放进一个稍微真实一点的场景问题就冒出来了栈的深度事先是不知道的。比如写一个表达式求值器用户输入的表达式嵌套层级完全不可控再比如写一个撤销操作模块用户可能连续撤销两百步。你只能拍一个初始容量然后祈祷够用。拍容量这件事本身就是一种赌博赌小了运行到一半栈满要么直接报错退出要么触发扩容。扩容听起来简单——申请一块更大的内存把老数据拷过去释放老内存——但它带来了三个隐性成本。第一是拷贝本身的开销虽然摊还下来每个元素还算便宜但某一次操作会突然变得很慢做实时交互的程序会明显卡顿一下。第二是原有的指针全部失效如果别的地方还留着指向栈内元素的地址那就是标准的悬空引用。第三是内存碎片频繁扩容释放容易让堆变得零碎。我在教学代码里见过太多人写顺序栈的时候把扩容阈值定成“满了再扩”然后把容量乘以二逻辑上没问题但他们忘了在拷贝之后更新栈顶下标也忘了检查 malloc 返回值。这些问题在链栈里其实换个形式依然会存在只是不再集中爆发在某一个扩容瞬间。理解顺序栈的边界是理解链栈为什么值得学的第一步。1.2 链栈的本质就是把栈顶搬到链表头部链栈这个名字听起来玄乎拆开看就是“用链式存储实现的栈”。它的核心思路一句话可以说完把单链表的表头当作栈顶入栈就是头插出栈就是删头。就这么简单。为什么一定是表头而不是表尾因为单链表在表尾插入需要先遍历到尾部时间复杂度是 O(n)而在表头插入和删除都只需要改两三个指针是 O(1)。栈这种结构的特点恰恰是“只在同一端反复进出”所以把这一端对准链表的表头天然就匹配上了。换个角度看链栈其实就是一条被限制了操作位置的单链表。你不能在中间插不能在中间删也不能从尾部取所有动作都锁定在头部。这种限制反而带来了好处代码路径极短没有分支没有扩容判断只要节点能申请到内存入栈就一定成功。反过来如果你把栈顶放在表尾那每次入栈都得从头走一遍链表找尾巴等于自己给自己加了一条 O(n) 的锁链完全没有必要。理解了“表头即栈顶”这一条链栈的所有操作基本就自动推出来了初始化就是把头指针置空判空就是看头指针是不是空入栈就是创建一个新节点、把它的 next 指向当前头、再把头指向它出栈就是暂存头指针、把头后移一位、释放旧头。没有例外没有特殊情况四句话覆盖全部核心操作。1.3 带头结点与不带头结点第一天就该定下来的事链栈有一个绕不开的选择题要不要一个恒定的头结点。这个头结点不存有效数据只在初始化时申请销毁时释放。这个选择在第一天做之后所有代码都会被它影响越晚改代价越大。不带头结点的写法栈空的条件是top NULL入栈时要判断“当前是不是空栈”如果是空栈新节点的 next 必须是 NULL而且栈顶指针本身要更新如果不是空栈直接头插。这多出来的一个判断就是初学者最容易写漏的地方我见过无数份代码在不带头结点的版本里第一次入栈之后 next 指向了随机值。带头结点的写法栈空的条件是top-next NULL入栈永远是同一套动作不需要区分是不是第一次。代价是多一个节点的内存以及初始化时要多一次 malloc。在真实项目里一个节点几十字节换来的是消除一整类边界判断这笔买卖我认为非常划算。所以我下面的实现全部采用带头结点的写法如果你学校的教材要求不带头结点看完逻辑自己删掉头结点也不难只需记得补上那个“首次入栈”的分支。2. 结构设计链栈的骨架与关键取舍2.1 栈顶指针为什么必须钉在表头有人会问栈顶指针一定要放在表头吗能不能放在表尾再加一个尾指针技术上可以但你要付出额外的维护成本尾部指针在出栈时没法后退除非你改成双向链表。而改成双向链表之后每个节点多一个指针域内存翻倍代码也变复杂换来的收益却只是“让栈顶在尾部”这个没有任何实际价值的心理舒适感。还有一种写法是把栈顶指针和数据节点分开定义两个结构体一个表示节点一个表示栈栈结构里存一个指针指向头顶。这种封装在工程里很常见好处是可以在栈结构里塞上元素个数、元素大小之类的元信息做泛型栈的时候特别有用。但如果你是初学阶段我建议先不要封装就把top当作一个全局或者局部的头指针参数传把最裸的操作写透等你能闭着眼睛写出入栈出栈了再去做那层封装。无论哪种写法核心不变所有有效的栈操作都发生在表头栈顶指针永远指向表头那个位置。这是我写链栈时反复提醒自己的一句话因为一旦你在脑子里把它想成“指向最后一个元素”写出来的代码就会开始往尾部使力然后陷入遍历的泥潭。2.2 结构体定义与类型约定的实操细节数据结构课上的链栈元素类型往往是int这没什么问题但你要清楚这是一个教学简化。真实场景里的栈可能存的是字符、字符串指针、甚至是结构体。所以我写的时候习惯做一层类型别名把元素类型单独拎出来typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack;这里有两个细节值得说。第一StackNode和LinkStack是两个不同的东西前者是节点类型后者是指针类型。很多教材把它们混着写导致学生在sizeof(StackNode)和sizeof(LinkStack)之间来回糊涂。我的习惯是凡是需要申请内存的地方用StackNode凡是作为函数参数传递栈的地方用LinkStack一眼就能看出这一行是在操作节点还是在操作栈。第二next的类型必须写struct StackNode *不能图省事写成StackNode *。因为在结构体定义内部StackNode这个别名还没生效编译器不认识。这个错误新手特别容易犯报错信息往往是一长串 “unknown type name”看着吓人其实改两个字就解决了。另外提醒一句如果你后面想写泛型链栈元素类型就不要用int了改用void *存指针或者用unsigned char data[]这种柔性数组。但这属于进阶内容先把int版本写稳再说。2.3 容量、内存与分配策略的取舍链栈最大的卖点是“不用预设容量”但这不等于没有上限。上限就是当前进程还能申请到的堆内存大小。这个边界在实际运行里通常是几百兆甚至几个 G对绝大多数应用来说够用但你要清楚两件事。第一malloc是可能失败的。教科书代码经常直接写StackNode *s malloc(sizeof(StackNode));然后就用这是非常危险的习惯。在内存紧张、嵌入式环境、或者被限制资源的情况下返回 NULL 是常态。每次申请都必须判空失败时要有明确的返回值和错误处理。第二频繁的小块申请和释放会带来性能损耗和内存碎片。一个链栈如果被用作高频进出的缓冲区比如解析器里的临时栈那么每次入栈都 malloc、每次出栈都 free开销其实不小。这种场景下常见的优化是做一个节点池预先申请一大块节点数组用空闲链表管理入栈从池里取出栈还回池里。这个技巧我在写词法分析器的时候用过把入栈出栈的耗时压下来差不多一半。当然这是优化阶段的事先别急着上先把裸版本写对。对比项顺序栈链栈容量固定需扩容动态按需申请单次入栈最坏耗时可能触发 O(n) 扩容稳定 O(1)每元素额外开销几乎为零一个指针8 字节64 位下缓存友好度高内存连续低节点分散实现复杂度低中需管内存适合场景深度可预估、追求速度深度不可控、频繁增删这张表我建议你记在心里它决定了你后面做题和做项目时的选型直觉。缓存友好度这一项在教学中很少提但它是顺序栈在实测中往往比链栈快好几倍的根本原因——连续内存下 CPU 预取命中率高而链栈每跳一个节点都可能是一次缓存未命中。3. 从零实现一份可以直接跑的链栈代码3.1 初始化、判空与销毁初始化做两件事申请头结点把头结点的 next 置空把栈顶指针指过去。这里我用返回值的方式传递栈而不是用二级指针因为对初学者来说二级指针是个额外的认知负担int InitStack(LinkStack *S) { *S (StackNode *)malloc(sizeof(StackNode)); if (*S NULL) { return 0; } (*S)-next NULL; (*S)-data 0; return 1; }注意这里传的是LinkStack *S也就是指针的指针。为什么因为我要修改调用方的栈顶指针本身让它指向新申请的头结点。如果你只传LinkStack S函数里改的只是形参副本调用方那边还是原来的值返回后栈顶指针依然是野的。这是初学者在链式结构上最常见的错误之一和链表初始化时犯的是同一个错。判空就一行return S-next NULL;。前提是 S 本身非空。如果 S 可能是 NULL先判 S再判 next别偷懒。销毁是整个实现里最容易被忽略、又最容易出内存泄漏的地方。正确做法是从头结点开始逐个释放void DestroyStack(LinkStack *S) { StackNode *p *S; while (p ! NULL) { StackNode *q p-next; free(p); p q; } *S NULL; }这里的顺序有讲究必须先保存 next再 free。如果你先 free 再取 p-next那是在读已释放的内存属于未定义行为运气好程序不崩运气不好跑一天才炸排查难度极高。这个坑我自己踩过后面会专门讲。3.2 入栈与出栈的核心四行入栈就是头插int Push(LinkStack S, ElemType e) { StackNode *s (StackNode *)malloc(sizeof(StackNode)); if (s NULL) { return 0; } s-data e; s-next S-next; S-next s; return 1; }四行有效代码顺序不能乱先赋值数据再挂 next最后改栈顶。如果顺序反了先把S-next指向 s再执行s-next S-next你会发现 s-next 指向了自己形成自环之后出栈就会陷入死循环或者释放自己。这个错误我见过不止一次说实话挺隐蔽的因为编译完全通过只有运行时才暴露。出栈就是删头int Pop(LinkStack S, ElemType *e) { if (S-next NULL) { return 0; } StackNode *p S-next; *e p-data; S-next p-next; free(p); return 1; }同样四行。注意出栈必须先把元素值带出来再释放节点顺序颠倒就是读已释放内存。另外出栈函数通常用返回值区分成功失败用出参带回元素值这种“返回值报错、指针带数据”的约定在 C 里非常通用建议养成习惯。取栈顶不删节点写法最简int GetTop(LinkStack S, ElemType *e) { if (S-next NULL) { return 0; } *e S-next-data; return 1; }判空和取栈顶这两件事经常被合并成“先判空再取”但在链栈里判空是 O(1)取栈顶也是 O(1)分开写更清晰。别为了省一次函数调用把两个语义混在一起代码可读性比那点开销值钱得多。3.3 取栈顶元素与遍历打印链栈的遍历和单链表完全一样从头结点的下一个开始顺次往后走直到 NULL。但这里有个语义问题需要提醒链栈的遍历是“从栈顶到栈底”而不是从栈底到栈顶。因为表头就是栈顶你先打印出来的是最近压进去的元素。如果你需要按入栈顺序输出那就得借助另一个栈或者递归倒序这一点在调试的时候经常让人犯迷糊。写一个打印函数用来观察状态void PrintStack(LinkStack S) { StackNode *p S-next; printf(栈顶 - ); while (p ! NULL) { printf(%d , p-data); p p-next; } printf(- 栈底\n); }这个函数的输出我在调试时天天用因为链栈的指针错误特别隐蔽而打印出来的序列往往能一眼看出是头插顺序错了还是 next 挂错了。比如你压入 1、2、3期望看到“3 2 1”如果打印出“1 2 3”那说明你实际上是在表尾插的问题定位瞬间完成。3.4 完整代码与测试主函数把上面的片段拼起来再加一个测试用的主函数就是一份可以编译运行的完整实现#include stdio.h #include stdlib.h typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack; int InitStack(LinkStack *S); int IsEmpty(LinkStack S); int Push(LinkStack S, ElemType e); int Pop(LinkStack S, ElemType *e); int GetTop(LinkStack S, ElemType *e); void DestroyStack(LinkStack *S); void PrintStack(LinkStack S); int main(void) { LinkStack S NULL; if (!InitStack(S)) { printf(init failed\n); return 1; } for (int i 1; i 5; i) { if (!Push(S, i * 10)) { printf(push %d failed\n, i * 10); } } PrintStack(S); ElemType top; if (GetTop(S, top)) { printf(top %d\n, top); } while (!IsEmpty(S)) { Pop(S, top); printf(pop %d, , top); } printf(\n); DestroyStack(S); printf(empty after destroy: %d\n, IsEmpty(S)); return 0; }预期输出是先把 50 40 30 20 10 打出来然后 top 是 50接着依次弹出 50 到 10最后确认销毁后为空。这个测试序列覆盖了入栈、取顶、出栈、销毁四个动作但还远远不够真正有价值的测试在下一节。3.5 边界测试用例设计我写链栈的时候测完主流程只算做了一半剩下的工作量全在边界上。下面这六个用例是我固定要跑的你可以直接抄用例操作序列预期结果检验点空栈出栈直接 Pop返回 0不出错空判断是否漏写空栈取顶直接 GetTop返回 0同上单元素进出Push(7) 后 Pop得到 7栈变空首尾节点的 next 处理连续压满再弹空Push 1000 次后 Pop 1000 次全部成功最终为空无泄漏、无越界重复判空弹空后连续判空一直返回真状态未残留销毁后再判空Destroy 后 IsEmpty返回真不崩溃指针已置 NULL第一条和第二条是最容易挂的因为很多人写 Pop 的时候直接从第一行取S-next-data压根没判空空栈一调就段错误。第三条例行测试看着简单但它能抓出“第一次入栈时 next 没置空”这类问题。第四条是压力测试重点不在结果而在用 valgrind 或者 ASan 跑一遍看看有没有泄漏。第六条最容易被忽略销毁函数如果只释放节点不把栈顶指针置 NULL那销毁之后调用方手里的指针就是野指针后续判空很可能读到随机值程序时崩时不崩。4. 边界测试与复杂度验证4.1 我常用的六个边界用例上面那张表列出来了这里补充一下每个用例背后的动机因为光知道跑什么不够得知道为什么跑。空栈出栈和空栈取顶本质是在检验你的防御性判断。这类错误在教学代码里出现率极高因为写的人脑子里默认“栈里一定有东西”。但真实系统里栈空是常态尤其是在循环里反复弹出直到空的写法一旦判空漏掉第一次调用的瞬间就崩。我见过一个解析器因为漏了这一个判断输入一个空表达式就整片崩溃。单元素进出检验的是“只有一个节点”这种特殊形态。在这种形态下头结点的 next 指向那个唯一节点那个节点的 next 是 NULL。出栈后头结点的 next 要回到 NULL。如果代码里错误地把S-next p-next写成了S-next p那出栈之后栈顶还指着已释放的旧节点下一次入栈就会在已释放内存上写数据。这类错误不看代码看不出但测试一跑就现原形。连续压满再弹空是在做大样本验证。我一般会压入十万个元素再弹出十万个跑完看两件事一是最终是否为空二是用valgrind --leak-checkfull看有没有泄漏。这个用例能抓出绝大多数内存管理问题包括忘记 free、重复 free、以及在错误的位置 free。销毁后判空则是在验证资源释放的完整性。销毁函数把栈顶指针置 NULL 这一步经常被当作可有可无的收尾其实它决定了调用方能否安全地复用这个变量。4.2 时间复杂度的实测数据理论上链栈的入栈、出栈、取顶、判空全都是一次指针操作加一次 malloc 或 free时间复杂度都是 O(1)。这个结论没有争议但“O(1)”只说明增长趋势不说明实际快慢。我在一台普通的开发机上做过对比测试压入弹出各一百万次顺序栈预先分配足够空间耗时大约是链栈的三分之一到四分之一。差距主要来自两个地方。第一是 malloc 和 free 本身的调用开销即使现代分配器做了优化每次调用依然要走一遍内部逻辑比单纯的数组下标自增要重。第二是内存局部性顺序栈的元素在内存里连续排布CPU 的缓存行能一次带进来一堆链栈的节点是散落在堆上的每访问一个节点都可能触发一次缓存未命中这个代价在数据量大时非常明显。这个测试结论不是让你别用链栈而是让你明白链栈的价值在于容量弹性和稳定 O(1)不在于绝对速度。如果你的栈深度可以预判并且对性能敏感顺序栈是更好的选择。如果深度完全不可控或者你要在链栈的基础上继续做链式扩展比如共享栈、多栈共存、把栈节点复用为其他结构链栈的优势就体现出来了。4.3 内存开销对比除了时间内存也得算。假设元素类型是 int占 4 字节指针占 8 字节64 位环境那么每个链栈节点实际占 16 字节其中有效载荷只有 4 字节超过七成是管理和对齐开销。如果栈里有十万元素链栈就是 1.6 MB而顺序栈只需要 0.4 MB。这个比例在元素类型变大时会改善。如果元素是 64 字节的结构体那么链栈每节点 72 字节有效载荷占比接近九成指针开销相对就不显眼了。所以选型的时候不能只看“链栈多一个指针”这句话得结合你的元素大小去算。元素越小链栈的相对开销越大元素越大链栈的额外成本就越可以忽略。还有一层隐形成本容易被漏掉动态分配器本身也要为每个内存块维护元数据通常是块头部的几个字节。也就是说你申请 16 字节实际占用的堆空间可能是 32 字节。这让链栈在元素很小的时候显得更加“奢侈”。如果真遇到这种场景节点池方案就非常值得考虑了——一次性申请大块内存自己做切分把分配器开销摊薄到接近零。5. 常见坑与排查实录5.1 高频错误速查表链栈的代码短但坑不少而且大多属于“编译能过、运行才炸”的类型。我把这些年见过和踩过的错误整理成一张表你写完代码对照着扫一遍能省掉大量调试时间现象最可能的原因修法入栈后打印只显示一个元素新节点的 next 没指向原栈顶检查是否是自环修正赋值顺序程序在出栈时崩溃栈空未判断就取 S-next-data首行加判空释放后程序偶发崩溃free 之后继续访问该节点先存 next 再 free第二次入栈数据错乱头结点未正确初始化next 是随机值初始化中显式置 NULL栈顶指针变了但调用方没变传参用了一级指针改为传指针的地址或用返回值内存使用量只涨不降出栈后忘了 free每次出栈都释放并置空临时指针销毁后判空仍返回非空销毁函数没把栈顶指针置 NULL结尾补一句置空压入一万个后异常退出没检查 malloc 返回值写入空指针每次申请后判空并返回错误这张表里最想强调的是第一行和第三行。第一行那个“自环”问题症状特别有迷惑性打印出来只有一个元素你会以为是入栈没成功但实际上是新节点的 next 指向了自己遍历时走到第一个就断了。第三行那个“先存后放”的规则我建议你把它当口诀背下来因为所有链式结构的批量释放都得遵守它。5.2 内存问题排查思路链栈的绝大多数崩溃都跟内存有关而内存问题最烦人的地方是它不稳定。同一份代码可能跑一次没事跑十次崩一次让你怀疑是玄学。我的排查顺序是这样的。第一步先把代码里所有 free 的地方都找出来逐个确认四件事free 的是不是 malloc 出来的地址、free 之后有没有再访问、有没有重复 free、free 之后指针有没有置空。这四问能覆盖八成问题。第二步跑一遍 ASan编译时加-fsanitizeaddress -g让它把越界和释放后使用的位置直接打出来。ASan 的报告虽然长但关键信息在最上面几行堆栈里会明确指出是哪一行代码访问了已释放内存。第三步如果 ASan 没报那就跑 valgrind 的泄漏检查看退出时还有多少块内存没释放它们的申请堆栈在哪。这里说一个我印象很深的案例。有一份链栈代码压入弹出跑几万次都没问题唯独在程序退出时偶尔段错误。查了半天发现是销毁函数里写了free(p); p p-next;先释放后取 next。多数时候那块内存还没被复用读出来的值恰好是对的所以不崩一旦分配器把这块内存还给了别人读到的就是垃圾值顺着垃圾指针 free 就炸了。这种问题靠肉眼看代码很难发现但只要 ASan 一跑位置立刻暴露。5.3 调试小技巧与实操心得第一个技巧写完 Init 之后立刻测一次 PrintStack。很多人习惯把整份代码写完再一起调结果出错时不知道是哪个函数的问题。我的做法是每写完一个函数就临时加两行测试确认行为正确再往下写。链栈一共才五六个函数逐个验证的代价很低收益是错误一旦出现你马上就知道是刚写的那几行有问题。第二个技巧在节点结构里临时加一个编号字段。调试期间每个新节点的编号自增打印的时候带上编号你就能看清楚到底哪个节点被重复入栈、哪个节点被提前释放。这个编号字段在正式代码里当然要去掉但在定位阶段它比任何断点都好使。第三个技巧不要用全局栈顶指针。初学者为了省事经常把LinkStack top写成全局变量然后所有函数直接访问。这样写确实少传参数但它让“这个函数会不会偷偷改栈顶”变得完全不可控而且没法同时存在两个栈。哪怕只写一个演示程序我也建议把栈顶当作参数传递多敲几个字换来的是逻辑清晰。第四个技巧养成出栈后把出参清零的习惯。Pop成功之后把传进来的临时变量重新赋一个哨兵值再继续用。这样如果后面某处忘了判断返回值就拿去用你会立刻看到一个明显的异常值而不是上一轮遗留的旧数据。这个习惯在处理循环弹出的时候特别有用。再补一个心得体会。链栈的代码量很小小到很多人写完就以为自己掌握了结果一上机就发现各种小毛病。我自己的经验是这个结构值得你至少完整默写三遍。第一遍照着书抄第二遍合上书默写第三遍在不看任何资料的情况下把六个函数全部写出来并且跑通边界测试。三遍之后你对指针赋值顺序的直觉就形成了再去看什么共享栈、链队列、双向链表都会觉得是一回事。这种“把一个小结构彻底吃透”的学习方式比囫囵吞枣地刷十个数据结构要有效得多。如果你后面要继续往下走链栈是一个非常合适的跳板。把它和顺序栈对照着实现一遍你会对“存储结构决定操作复杂度”这句话有切身体会再往后去写链队列你会发现两者的差别只在出队是从表头还是表尾进行继续走到树和图的深度优先遍历那个显式维护的栈其实和你今天写的这份代码是同一个东西只不过存的东西从整数变成了节点指针。真正把链栈写利索了后面这一串结构都能顺着这根线串起来。
学数据结构学到栈这一章很多人是从顺序栈开始的一个数组加一个栈顶下标写起来确实顺手。但真正上手写项目、做表达式求值、做括号匹配、做编辑器撤销功能的时候顺序栈的固定容量很快就会变成一根刺——栈满了要扩容扩容就得重新申请内存、搬数据稍不留神老指针就悬空了。链栈就是为了绕开这类麻烦出现的结构它把栈顶放在单链表的头部入栈出栈都在表头完成容量跟着节点走理论上只要有内存就能一直压。这篇内容面向刚学完链表、准备啃链栈的初学者也适合那些写过一遍但总觉得心里没底的读者我会从结构设计的取舍讲到一行行代码落地再把我自己踩过的坑和排查思路摊开来说尽量让你看完就能自己默写出来而不是背完就忘。1. 链栈到底解决什么问题从顺序栈的边界说起1.1 顺序栈为什么会在实战里让人难受顺序栈的本质是一段连续内存加一个栈顶位置标记。它的优点是访问快、结构简单、代码短教学演示里几乎无懈可击。但只要你把它放进一个稍微真实一点的场景问题就冒出来了栈的深度事先是不知道的。比如写一个表达式求值器用户输入的表达式嵌套层级完全不可控再比如写一个撤销操作模块用户可能连续撤销两百步。你只能拍一个初始容量然后祈祷够用。拍容量这件事本身就是一种赌博赌小了运行到一半栈满要么直接报错退出要么触发扩容。扩容听起来简单——申请一块更大的内存把老数据拷过去释放老内存——但它带来了三个隐性成本。第一是拷贝本身的开销虽然摊还下来每个元素还算便宜但某一次操作会突然变得很慢做实时交互的程序会明显卡顿一下。第二是原有的指针全部失效如果别的地方还留着指向栈内元素的地址那就是标准的悬空引用。第三是内存碎片频繁扩容释放容易让堆变得零碎。我在教学代码里见过太多人写顺序栈的时候把扩容阈值定成“满了再扩”然后把容量乘以二逻辑上没问题但他们忘了在拷贝之后更新栈顶下标也忘了检查 malloc 返回值。这些问题在链栈里其实换个形式依然会存在只是不再集中爆发在某一个扩容瞬间。理解顺序栈的边界是理解链栈为什么值得学的第一步。1.2 链栈的本质就是把栈顶搬到链表头部链栈这个名字听起来玄乎拆开看就是“用链式存储实现的栈”。它的核心思路一句话可以说完把单链表的表头当作栈顶入栈就是头插出栈就是删头。就这么简单。为什么一定是表头而不是表尾因为单链表在表尾插入需要先遍历到尾部时间复杂度是 O(n)而在表头插入和删除都只需要改两三个指针是 O(1)。栈这种结构的特点恰恰是“只在同一端反复进出”所以把这一端对准链表的表头天然就匹配上了。换个角度看链栈其实就是一条被限制了操作位置的单链表。你不能在中间插不能在中间删也不能从尾部取所有动作都锁定在头部。这种限制反而带来了好处代码路径极短没有分支没有扩容判断只要节点能申请到内存入栈就一定成功。反过来如果你把栈顶放在表尾那每次入栈都得从头走一遍链表找尾巴等于自己给自己加了一条 O(n) 的锁链完全没有必要。理解了“表头即栈顶”这一条链栈的所有操作基本就自动推出来了初始化就是把头指针置空判空就是看头指针是不是空入栈就是创建一个新节点、把它的 next 指向当前头、再把头指向它出栈就是暂存头指针、把头后移一位、释放旧头。没有例外没有特殊情况四句话覆盖全部核心操作。1.3 带头结点与不带头结点第一天就该定下来的事链栈有一个绕不开的选择题要不要一个恒定的头结点。这个头结点不存有效数据只在初始化时申请销毁时释放。这个选择在第一天做之后所有代码都会被它影响越晚改代价越大。不带头结点的写法栈空的条件是top NULL入栈时要判断“当前是不是空栈”如果是空栈新节点的 next 必须是 NULL而且栈顶指针本身要更新如果不是空栈直接头插。这多出来的一个判断就是初学者最容易写漏的地方我见过无数份代码在不带头结点的版本里第一次入栈之后 next 指向了随机值。带头结点的写法栈空的条件是top-next NULL入栈永远是同一套动作不需要区分是不是第一次。代价是多一个节点的内存以及初始化时要多一次 malloc。在真实项目里一个节点几十字节换来的是消除一整类边界判断这笔买卖我认为非常划算。所以我下面的实现全部采用带头结点的写法如果你学校的教材要求不带头结点看完逻辑自己删掉头结点也不难只需记得补上那个“首次入栈”的分支。2. 结构设计链栈的骨架与关键取舍2.1 栈顶指针为什么必须钉在表头有人会问栈顶指针一定要放在表头吗能不能放在表尾再加一个尾指针技术上可以但你要付出额外的维护成本尾部指针在出栈时没法后退除非你改成双向链表。而改成双向链表之后每个节点多一个指针域内存翻倍代码也变复杂换来的收益却只是“让栈顶在尾部”这个没有任何实际价值的心理舒适感。还有一种写法是把栈顶指针和数据节点分开定义两个结构体一个表示节点一个表示栈栈结构里存一个指针指向头顶。这种封装在工程里很常见好处是可以在栈结构里塞上元素个数、元素大小之类的元信息做泛型栈的时候特别有用。但如果你是初学阶段我建议先不要封装就把top当作一个全局或者局部的头指针参数传把最裸的操作写透等你能闭着眼睛写出入栈出栈了再去做那层封装。无论哪种写法核心不变所有有效的栈操作都发生在表头栈顶指针永远指向表头那个位置。这是我写链栈时反复提醒自己的一句话因为一旦你在脑子里把它想成“指向最后一个元素”写出来的代码就会开始往尾部使力然后陷入遍历的泥潭。2.2 结构体定义与类型约定的实操细节数据结构课上的链栈元素类型往往是int这没什么问题但你要清楚这是一个教学简化。真实场景里的栈可能存的是字符、字符串指针、甚至是结构体。所以我写的时候习惯做一层类型别名把元素类型单独拎出来typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack;这里有两个细节值得说。第一StackNode和LinkStack是两个不同的东西前者是节点类型后者是指针类型。很多教材把它们混着写导致学生在sizeof(StackNode)和sizeof(LinkStack)之间来回糊涂。我的习惯是凡是需要申请内存的地方用StackNode凡是作为函数参数传递栈的地方用LinkStack一眼就能看出这一行是在操作节点还是在操作栈。第二next的类型必须写struct StackNode *不能图省事写成StackNode *。因为在结构体定义内部StackNode这个别名还没生效编译器不认识。这个错误新手特别容易犯报错信息往往是一长串 “unknown type name”看着吓人其实改两个字就解决了。另外提醒一句如果你后面想写泛型链栈元素类型就不要用int了改用void *存指针或者用unsigned char data[]这种柔性数组。但这属于进阶内容先把int版本写稳再说。2.3 容量、内存与分配策略的取舍链栈最大的卖点是“不用预设容量”但这不等于没有上限。上限就是当前进程还能申请到的堆内存大小。这个边界在实际运行里通常是几百兆甚至几个 G对绝大多数应用来说够用但你要清楚两件事。第一malloc是可能失败的。教科书代码经常直接写StackNode *s malloc(sizeof(StackNode));然后就用这是非常危险的习惯。在内存紧张、嵌入式环境、或者被限制资源的情况下返回 NULL 是常态。每次申请都必须判空失败时要有明确的返回值和错误处理。第二频繁的小块申请和释放会带来性能损耗和内存碎片。一个链栈如果被用作高频进出的缓冲区比如解析器里的临时栈那么每次入栈都 malloc、每次出栈都 free开销其实不小。这种场景下常见的优化是做一个节点池预先申请一大块节点数组用空闲链表管理入栈从池里取出栈还回池里。这个技巧我在写词法分析器的时候用过把入栈出栈的耗时压下来差不多一半。当然这是优化阶段的事先别急着上先把裸版本写对。对比项顺序栈链栈容量固定需扩容动态按需申请单次入栈最坏耗时可能触发 O(n) 扩容稳定 O(1)每元素额外开销几乎为零一个指针8 字节64 位下缓存友好度高内存连续低节点分散实现复杂度低中需管内存适合场景深度可预估、追求速度深度不可控、频繁增删这张表我建议你记在心里它决定了你后面做题和做项目时的选型直觉。缓存友好度这一项在教学中很少提但它是顺序栈在实测中往往比链栈快好几倍的根本原因——连续内存下 CPU 预取命中率高而链栈每跳一个节点都可能是一次缓存未命中。3. 从零实现一份可以直接跑的链栈代码3.1 初始化、判空与销毁初始化做两件事申请头结点把头结点的 next 置空把栈顶指针指过去。这里我用返回值的方式传递栈而不是用二级指针因为对初学者来说二级指针是个额外的认知负担int InitStack(LinkStack *S) { *S (StackNode *)malloc(sizeof(StackNode)); if (*S NULL) { return 0; } (*S)-next NULL; (*S)-data 0; return 1; }注意这里传的是LinkStack *S也就是指针的指针。为什么因为我要修改调用方的栈顶指针本身让它指向新申请的头结点。如果你只传LinkStack S函数里改的只是形参副本调用方那边还是原来的值返回后栈顶指针依然是野的。这是初学者在链式结构上最常见的错误之一和链表初始化时犯的是同一个错。判空就一行return S-next NULL;。前提是 S 本身非空。如果 S 可能是 NULL先判 S再判 next别偷懒。销毁是整个实现里最容易被忽略、又最容易出内存泄漏的地方。正确做法是从头结点开始逐个释放void DestroyStack(LinkStack *S) { StackNode *p *S; while (p ! NULL) { StackNode *q p-next; free(p); p q; } *S NULL; }这里的顺序有讲究必须先保存 next再 free。如果你先 free 再取 p-next那是在读已释放的内存属于未定义行为运气好程序不崩运气不好跑一天才炸排查难度极高。这个坑我自己踩过后面会专门讲。3.2 入栈与出栈的核心四行入栈就是头插int Push(LinkStack S, ElemType e) { StackNode *s (StackNode *)malloc(sizeof(StackNode)); if (s NULL) { return 0; } s-data e; s-next S-next; S-next s; return 1; }四行有效代码顺序不能乱先赋值数据再挂 next最后改栈顶。如果顺序反了先把S-next指向 s再执行s-next S-next你会发现 s-next 指向了自己形成自环之后出栈就会陷入死循环或者释放自己。这个错误我见过不止一次说实话挺隐蔽的因为编译完全通过只有运行时才暴露。出栈就是删头int Pop(LinkStack S, ElemType *e) { if (S-next NULL) { return 0; } StackNode *p S-next; *e p-data; S-next p-next; free(p); return 1; }同样四行。注意出栈必须先把元素值带出来再释放节点顺序颠倒就是读已释放内存。另外出栈函数通常用返回值区分成功失败用出参带回元素值这种“返回值报错、指针带数据”的约定在 C 里非常通用建议养成习惯。取栈顶不删节点写法最简int GetTop(LinkStack S, ElemType *e) { if (S-next NULL) { return 0; } *e S-next-data; return 1; }判空和取栈顶这两件事经常被合并成“先判空再取”但在链栈里判空是 O(1)取栈顶也是 O(1)分开写更清晰。别为了省一次函数调用把两个语义混在一起代码可读性比那点开销值钱得多。3.3 取栈顶元素与遍历打印链栈的遍历和单链表完全一样从头结点的下一个开始顺次往后走直到 NULL。但这里有个语义问题需要提醒链栈的遍历是“从栈顶到栈底”而不是从栈底到栈顶。因为表头就是栈顶你先打印出来的是最近压进去的元素。如果你需要按入栈顺序输出那就得借助另一个栈或者递归倒序这一点在调试的时候经常让人犯迷糊。写一个打印函数用来观察状态void PrintStack(LinkStack S) { StackNode *p S-next; printf(栈顶 - ); while (p ! NULL) { printf(%d , p-data); p p-next; } printf(- 栈底\n); }这个函数的输出我在调试时天天用因为链栈的指针错误特别隐蔽而打印出来的序列往往能一眼看出是头插顺序错了还是 next 挂错了。比如你压入 1、2、3期望看到“3 2 1”如果打印出“1 2 3”那说明你实际上是在表尾插的问题定位瞬间完成。3.4 完整代码与测试主函数把上面的片段拼起来再加一个测试用的主函数就是一份可以编译运行的完整实现#include stdio.h #include stdlib.h typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode, *LinkStack; int InitStack(LinkStack *S); int IsEmpty(LinkStack S); int Push(LinkStack S, ElemType e); int Pop(LinkStack S, ElemType *e); int GetTop(LinkStack S, ElemType *e); void DestroyStack(LinkStack *S); void PrintStack(LinkStack S); int main(void) { LinkStack S NULL; if (!InitStack(S)) { printf(init failed\n); return 1; } for (int i 1; i 5; i) { if (!Push(S, i * 10)) { printf(push %d failed\n, i * 10); } } PrintStack(S); ElemType top; if (GetTop(S, top)) { printf(top %d\n, top); } while (!IsEmpty(S)) { Pop(S, top); printf(pop %d, , top); } printf(\n); DestroyStack(S); printf(empty after destroy: %d\n, IsEmpty(S)); return 0; }预期输出是先把 50 40 30 20 10 打出来然后 top 是 50接着依次弹出 50 到 10最后确认销毁后为空。这个测试序列覆盖了入栈、取顶、出栈、销毁四个动作但还远远不够真正有价值的测试在下一节。3.5 边界测试用例设计我写链栈的时候测完主流程只算做了一半剩下的工作量全在边界上。下面这六个用例是我固定要跑的你可以直接抄用例操作序列预期结果检验点空栈出栈直接 Pop返回 0不出错空判断是否漏写空栈取顶直接 GetTop返回 0同上单元素进出Push(7) 后 Pop得到 7栈变空首尾节点的 next 处理连续压满再弹空Push 1000 次后 Pop 1000 次全部成功最终为空无泄漏、无越界重复判空弹空后连续判空一直返回真状态未残留销毁后再判空Destroy 后 IsEmpty返回真不崩溃指针已置 NULL第一条和第二条是最容易挂的因为很多人写 Pop 的时候直接从第一行取S-next-data压根没判空空栈一调就段错误。第三条例行测试看着简单但它能抓出“第一次入栈时 next 没置空”这类问题。第四条是压力测试重点不在结果而在用 valgrind 或者 ASan 跑一遍看看有没有泄漏。第六条最容易被忽略销毁函数如果只释放节点不把栈顶指针置 NULL那销毁之后调用方手里的指针就是野指针后续判空很可能读到随机值程序时崩时不崩。4. 边界测试与复杂度验证4.1 我常用的六个边界用例上面那张表列出来了这里补充一下每个用例背后的动机因为光知道跑什么不够得知道为什么跑。空栈出栈和空栈取顶本质是在检验你的防御性判断。这类错误在教学代码里出现率极高因为写的人脑子里默认“栈里一定有东西”。但真实系统里栈空是常态尤其是在循环里反复弹出直到空的写法一旦判空漏掉第一次调用的瞬间就崩。我见过一个解析器因为漏了这一个判断输入一个空表达式就整片崩溃。单元素进出检验的是“只有一个节点”这种特殊形态。在这种形态下头结点的 next 指向那个唯一节点那个节点的 next 是 NULL。出栈后头结点的 next 要回到 NULL。如果代码里错误地把S-next p-next写成了S-next p那出栈之后栈顶还指着已释放的旧节点下一次入栈就会在已释放内存上写数据。这类错误不看代码看不出但测试一跑就现原形。连续压满再弹空是在做大样本验证。我一般会压入十万个元素再弹出十万个跑完看两件事一是最终是否为空二是用valgrind --leak-checkfull看有没有泄漏。这个用例能抓出绝大多数内存管理问题包括忘记 free、重复 free、以及在错误的位置 free。销毁后判空则是在验证资源释放的完整性。销毁函数把栈顶指针置 NULL 这一步经常被当作可有可无的收尾其实它决定了调用方能否安全地复用这个变量。4.2 时间复杂度的实测数据理论上链栈的入栈、出栈、取顶、判空全都是一次指针操作加一次 malloc 或 free时间复杂度都是 O(1)。这个结论没有争议但“O(1)”只说明增长趋势不说明实际快慢。我在一台普通的开发机上做过对比测试压入弹出各一百万次顺序栈预先分配足够空间耗时大约是链栈的三分之一到四分之一。差距主要来自两个地方。第一是 malloc 和 free 本身的调用开销即使现代分配器做了优化每次调用依然要走一遍内部逻辑比单纯的数组下标自增要重。第二是内存局部性顺序栈的元素在内存里连续排布CPU 的缓存行能一次带进来一堆链栈的节点是散落在堆上的每访问一个节点都可能触发一次缓存未命中这个代价在数据量大时非常明显。这个测试结论不是让你别用链栈而是让你明白链栈的价值在于容量弹性和稳定 O(1)不在于绝对速度。如果你的栈深度可以预判并且对性能敏感顺序栈是更好的选择。如果深度完全不可控或者你要在链栈的基础上继续做链式扩展比如共享栈、多栈共存、把栈节点复用为其他结构链栈的优势就体现出来了。4.3 内存开销对比除了时间内存也得算。假设元素类型是 int占 4 字节指针占 8 字节64 位环境那么每个链栈节点实际占 16 字节其中有效载荷只有 4 字节超过七成是管理和对齐开销。如果栈里有十万元素链栈就是 1.6 MB而顺序栈只需要 0.4 MB。这个比例在元素类型变大时会改善。如果元素是 64 字节的结构体那么链栈每节点 72 字节有效载荷占比接近九成指针开销相对就不显眼了。所以选型的时候不能只看“链栈多一个指针”这句话得结合你的元素大小去算。元素越小链栈的相对开销越大元素越大链栈的额外成本就越可以忽略。还有一层隐形成本容易被漏掉动态分配器本身也要为每个内存块维护元数据通常是块头部的几个字节。也就是说你申请 16 字节实际占用的堆空间可能是 32 字节。这让链栈在元素很小的时候显得更加“奢侈”。如果真遇到这种场景节点池方案就非常值得考虑了——一次性申请大块内存自己做切分把分配器开销摊薄到接近零。5. 常见坑与排查实录5.1 高频错误速查表链栈的代码短但坑不少而且大多属于“编译能过、运行才炸”的类型。我把这些年见过和踩过的错误整理成一张表你写完代码对照着扫一遍能省掉大量调试时间现象最可能的原因修法入栈后打印只显示一个元素新节点的 next 没指向原栈顶检查是否是自环修正赋值顺序程序在出栈时崩溃栈空未判断就取 S-next-data首行加判空释放后程序偶发崩溃free 之后继续访问该节点先存 next 再 free第二次入栈数据错乱头结点未正确初始化next 是随机值初始化中显式置 NULL栈顶指针变了但调用方没变传参用了一级指针改为传指针的地址或用返回值内存使用量只涨不降出栈后忘了 free每次出栈都释放并置空临时指针销毁后判空仍返回非空销毁函数没把栈顶指针置 NULL结尾补一句置空压入一万个后异常退出没检查 malloc 返回值写入空指针每次申请后判空并返回错误这张表里最想强调的是第一行和第三行。第一行那个“自环”问题症状特别有迷惑性打印出来只有一个元素你会以为是入栈没成功但实际上是新节点的 next 指向了自己遍历时走到第一个就断了。第三行那个“先存后放”的规则我建议你把它当口诀背下来因为所有链式结构的批量释放都得遵守它。5.2 内存问题排查思路链栈的绝大多数崩溃都跟内存有关而内存问题最烦人的地方是它不稳定。同一份代码可能跑一次没事跑十次崩一次让你怀疑是玄学。我的排查顺序是这样的。第一步先把代码里所有 free 的地方都找出来逐个确认四件事free 的是不是 malloc 出来的地址、free 之后有没有再访问、有没有重复 free、free 之后指针有没有置空。这四问能覆盖八成问题。第二步跑一遍 ASan编译时加-fsanitizeaddress -g让它把越界和释放后使用的位置直接打出来。ASan 的报告虽然长但关键信息在最上面几行堆栈里会明确指出是哪一行代码访问了已释放内存。第三步如果 ASan 没报那就跑 valgrind 的泄漏检查看退出时还有多少块内存没释放它们的申请堆栈在哪。这里说一个我印象很深的案例。有一份链栈代码压入弹出跑几万次都没问题唯独在程序退出时偶尔段错误。查了半天发现是销毁函数里写了free(p); p p-next;先释放后取 next。多数时候那块内存还没被复用读出来的值恰好是对的所以不崩一旦分配器把这块内存还给了别人读到的就是垃圾值顺着垃圾指针 free 就炸了。这种问题靠肉眼看代码很难发现但只要 ASan 一跑位置立刻暴露。5.3 调试小技巧与实操心得第一个技巧写完 Init 之后立刻测一次 PrintStack。很多人习惯把整份代码写完再一起调结果出错时不知道是哪个函数的问题。我的做法是每写完一个函数就临时加两行测试确认行为正确再往下写。链栈一共才五六个函数逐个验证的代价很低收益是错误一旦出现你马上就知道是刚写的那几行有问题。第二个技巧在节点结构里临时加一个编号字段。调试期间每个新节点的编号自增打印的时候带上编号你就能看清楚到底哪个节点被重复入栈、哪个节点被提前释放。这个编号字段在正式代码里当然要去掉但在定位阶段它比任何断点都好使。第三个技巧不要用全局栈顶指针。初学者为了省事经常把LinkStack top写成全局变量然后所有函数直接访问。这样写确实少传参数但它让“这个函数会不会偷偷改栈顶”变得完全不可控而且没法同时存在两个栈。哪怕只写一个演示程序我也建议把栈顶当作参数传递多敲几个字换来的是逻辑清晰。第四个技巧养成出栈后把出参清零的习惯。Pop成功之后把传进来的临时变量重新赋一个哨兵值再继续用。这样如果后面某处忘了判断返回值就拿去用你会立刻看到一个明显的异常值而不是上一轮遗留的旧数据。这个习惯在处理循环弹出的时候特别有用。再补一个心得体会。链栈的代码量很小小到很多人写完就以为自己掌握了结果一上机就发现各种小毛病。我自己的经验是这个结构值得你至少完整默写三遍。第一遍照着书抄第二遍合上书默写第三遍在不看任何资料的情况下把六个函数全部写出来并且跑通边界测试。三遍之后你对指针赋值顺序的直觉就形成了再去看什么共享栈、链队列、双向链表都会觉得是一回事。这种“把一个小结构彻底吃透”的学习方式比囫囵吞枣地刷十个数据结构要有效得多。如果你后面要继续往下走链栈是一个非常合适的跳板。把它和顺序栈对照着实现一遍你会对“存储结构决定操作复杂度”这句话有切身体会再往后去写链队列你会发现两者的差别只在出队是从表头还是表尾进行继续走到树和图的深度优先遍历那个显式维护的栈其实和你今天写的这份代码是同一个东西只不过存的东西从整数变成了节点指针。真正把链栈写利索了后面这一串结构都能顺着这根线串起来。
