1. 链栈到底解决了顺序栈的哪些痛点很多人第一次学栈的时候教材上给的都是顺序栈——一个数组加一个栈顶指针top入栈就top出栈就top--。这个模型足够简单简单到让人误以为栈就应该是这个样子。但真正写过稍微像样一点的程序之后你会发现顺序栈有两个绕不开的硬伤。第一个硬伤是容量固定。数组声明的时候就得定死大小比如int data[100]那这个栈最多装100个元素。你可能会想那我开大一点不就行了开10000、开100000。问题是开小了不够用开大了浪费内存而且你永远无法预知实际运行中到底会压入多少元素。在一些嵌入式场景或者内存紧张的环境里这种赌一个上限的做法是很危险的。第二个硬伤更隐蔽顺序栈的扩容代价极高。有些实现会在栈满时用realloc动态扩容看起来解决了容量问题但每次扩容都要重新申请一块更大的连续内存然后把老数据整体搬过去。如果栈里存的是大结构体这个搬运成本相当可观。而且频繁扩容还会造成内存碎片。链栈就是为了绕开这两个问题而存在的。它用链式存储代替连续数组栈顶就是链表的头节点入栈就是在头部插入一个节点出栈就是删除头节点。因为链表节点是动态申请的所以理论上只要系统内存还够栈就不会满。同时每次入栈出栈只涉及一两个指针的改动不涉及任何数据搬移时间复杂度稳定在 O(1)。我个人的经验是当你需要的是一个大小不可预知、频繁增删、对单次操作耗时敏感的栈时链栈几乎是默认选择。典型场景包括表达式求值中的运算符栈、深度优先搜索的路径栈、函数调用模拟、括号匹配检测、撤销操作历史记录等等。这些场景的共同特点就是元素数量波动大你没法提前给出一个靠谱的上限。当然链栈也不是没有代价。每个节点除了存数据还要额外存一个指针空间开销比顺序栈大。而且动态申请节点涉及堆操作在极端高频的场景下malloc和free本身的开销可能比顺序栈的数组下标移动要大。所以选哪个本质上是在空间换灵活性和时间换确定性之间做权衡。理解了这一点你再看链栈的代码就不会觉得那些指针操作是为了复杂而复杂了。2. 链栈的节点设计与结构体定义2.1 为什么栈顶要放在链表头部而不是尾部这是链栈设计里第一个需要想清楚的问题。单链表我们通常有一个头指针如果栈顶放在链表尾部那么每次入栈都要从头遍历到尾时间复杂度直接退化成 O(n)。而如果把栈顶放在头部入栈就是在头指针后面插入一个新节点出栈就是删掉头指针后面的那个节点两者都是常数时间。所以链栈的标准做法是top指针直接指向栈顶节点也就是链表的第一个数据节点。注意这里说的是第一个数据节点不是头节点。头节点dummy head在链栈里其实不是必须的因为栈的所有操作都只在头部进行不存在在中间插入或者删除指定位置这种需要前驱节点的操作。不带头的写法更简洁也少一个节点的内存开销。但这里有个细节要注意当栈为空时top应该指向NULL。这一点和顺序栈不同顺序栈空的时候top通常等于 -1而链栈空的时候就是一个空指针。判空逻辑因此变成了top NULL非常直观。2.2 节点结构体的字段安排节点结构体本身很简单一个数据域加一个指针域typedef int ElemType; // 方便后续替换数据类型 typedef struct StackNode { ElemType data; // 数据域 struct StackNode *next; // 指针域指向下一个节点 } StackNode, *LinkStack;这里我用typedef把struct StackNode *定义成了LinkStack这样后面声明栈的时候直接写LinkStack s;就行语义上也更清晰——s就是一个链栈。关于ElemType用typedef单独定义这是一个很实用的习惯。你以后想把栈里存的数据从int换成char、float或者自定义结构体只需要改这一行不用去动所有函数的签名。我在实际项目里见过太多人把int写死在每个函数参数里后来要改类型的时候满屏找非常痛苦。提示如果你打算在栈里存结构体建议存指针而不是存结构体本身。因为结构体赋值涉及逐字节拷贝节点一多开销就上来了。存指针的话节点里只放一个地址拷贝成本固定。2.3 需不需要头节点一个容易纠结的问题教材上对链栈要不要带头节点有不同写法这里我说说我的判断。带头的写法是top永远指向一个不存数据的头节点真正的栈顶是top-next。不带头的写法是top直接指向栈顶数据节点空栈时top NULL。带头的优势在于入栈和出栈的代码可以统一处理不用单独判断空栈的情况。比如出栈时带头的话你只需要判断top-next NULL然后删top-next不带头的话你得先判断top NULL再删top本身逻辑上稍微多一层。不带头的优势在于省一个节点的内存而且代码更直观——top就是栈顶没有中间商。我个人的选择是不带头。原因很简单链栈的操作全部集中在头部不存在需要统一处理中间位置的场景头节点带来的代码简化非常有限反而多了一层间接性调试的时候容易绕晕。当然这只是个人偏好两种写法都能跑关键是你在一个项目里保持一致别一半函数带头一半不带头。3. 六个核心操作的完整实现与逐行拆解3.1 初始化为什么链栈的初始化比顺序栈还简单顺序栈初始化通常要做两件事给数组分配空间如果是动态的然后把top置为 -1。链栈初始化只需要一件事把top置为NULL。void InitStack(LinkStack *s) { *s NULL; }注意这里传的是LinkStack *s也就是指向指针的指针。为什么要这样因为我们要修改的是调用者那边的top指针本身而不是它指向的内容。如果你写成void InitStack(LinkStack s)那s只是实参的一个拷贝你在函数里把s置为NULL外面的top根本不受影响。这是 C 语言里指针传参的经典坑初学者十有八九会踩。调用方式LinkStack s; InitStack(s);初始化之后s就是NULL表示一个空栈。这里不需要malloc也不需要free因为还没有任何节点被创建。注意有些实现会把初始化写成返回一个LinkStack的函数比如LinkStack InitStack()里面return NULL;。这种写法也能用但一旦你后续要扩展初始化逻辑比如预分配一些节点返回值写法就不如指针传参灵活了。我建议统一用指针传参。3.2 判栈空一个if就够了吗判空的逻辑非常简单int StackEmpty(LinkStack s) { return s NULL; }返回 1 表示空返回 0 表示非空。这里传的是LinkStack s而不是指针的指针因为我们只是读取s的值不修改它。但这里有个值得聊的点判空到底应该返回int还是bool在 C99 之前C 语言没有原生bool类型所以教材上普遍用int0 表示假非 0 表示真。C99 引入了stdbool.h你可以用bool、true、false。我的建议是如果你的编译环境支持 C99 及以上用bool更清晰如果是要兼容老编译器或者嵌入式环境用int更保险。另外判空函数虽然简单但它是很多其他操作的前置检查。比如出栈和取栈顶元素之前都必须先判空否则就会对NULL指针解引用直接段错误。这个检查不能省哪怕你觉得我调用的时候肯定不为空——防御性编程的习惯就是从这种小地方养成的。3.3 入栈三行代码背后的指针顺序问题入栈的核心逻辑是申请一个新节点把数据放进去然后把这个新节点挂到栈顶前面最后更新top指针。int Push(LinkStack *s, ElemType e) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; // 内存分配失败 } newNode-data e; newNode-next *s; // 新节点的 next 指向原来的栈顶 *s newNode; // 更新栈顶指针 return 1; }这三行指针操作看起来简单但顺序绝对不能错。如果你先写*s newNode;再写newNode-next *s;那就变成了新节点的next指向自己形成一个自环整个栈就废了。正确的顺序是先接后断——先把新节点和原来的栈顶接上再移动栈顶指针。malloc的返回值检查也是必须的。虽然现代操作系统上malloc很少失败但在内存受限的环境里或者你一次性申请了超大块内存失败是完全可能的。如果不检查后面直接对NULL解引用程序当场崩溃而且崩溃位置可能离真正的问题很远调试起来很麻烦。关于sizeof(StackNode)还是sizeof(*newNode)两种写法等价但我更推荐后者。因为如果哪天你把newNode的类型改了sizeof(*newNode)会自动跟着变而sizeof(StackNode)需要你手动同步修改容易漏。3.4 出栈为什么必须用二级指针以及被删节点的内存怎么处理出栈的逻辑是先判空然后保存栈顶节点的数据把top移到下一个节点最后释放被删节点的内存。int Pop(LinkStack *s, ElemType *e) { if (*s NULL) { return 0; // 栈空出栈失败 } StackNode *temp *s; // 保存栈顶节点 *e temp-data; // 把数据带出去 *s temp-next; // 栈顶指针下移 free(temp); // 释放被删节点 return 1; }这里有几个关键点。第一temp这个临时指针不能省。如果你直接free(*s); *s (*s)-next;那free之后*s指向的内存已经无效了再去读(*s)-next就是访问已释放内存行为未定义。必须先保存next再free。第二数据是通过ElemType *e这个出参带出去的。为什么不让Pop直接返回数据因为返回值要用来表示成功或失败。如果栈空你得有个方式告诉调用者这次出栈没成功同时数据也没意义。用返回值表示状态、用出参带数据是 C 语言里处理可能失败的操作的标准套路。第三free(temp)之后temp本身这个指针变量还在栈上但它指向的内存已经还给系统了。这时候如果你不小心再写temp-data就是典型的 use-after-free可能读到垃圾数据也可能直接崩溃。养成习惯free之后如果还要用这个指针变量立刻置NULL。虽然在这个函数里temp马上就出作用域了但在更复杂的函数里这个习惯能救命。3.5 取栈顶元素和出栈的区别只差一个free取栈顶元素有些教材叫GetTop或Top的逻辑和出栈几乎一样唯一的区别是不删除节点int GetTop(LinkStack s, ElemType *e) { if (s NULL) { return 0; } *e s-data; return 1; }注意这里传的是LinkStack s而不是LinkStack *s因为我们不修改栈顶指针只是读取。这也是一个容易搞混的地方什么时候传一级指针什么时候传二级指针判断标准就是函数内部要不要修改指针本身的值。入栈和出栈要改top所以传二级取栈顶和判空不改top所以传一级。3.6 求栈长为什么链栈求长度是 O(n) 而顺序栈是 O(1)求栈长的实现很直接从头遍历到尾数节点个数int StackLength(LinkStack s) { int count 0; StackNode *p s; while (p ! NULL) { count; p p-next; } return count; }这里就体现出链式存储的一个劣势了顺序栈求长度直接top 1就完事O(1)链栈必须遍历O(n)。如果你的程序里频繁需要知道栈的长度链栈这个开销就不能忽略。解决办法有两个。一是在栈结构体里额外维护一个length字段每次入栈length出栈length--求长度直接返回这个字段。代价是每个操作多一次自增或自减但把求长度降到了 O(1)。二是如果只是偶尔求长度那就遍历没必要为了偶尔的操作增加维护成本。我个人的做法是如果这个栈会被频繁查询长度就加length字段如果只是调试时看看就遍历。不要无脑加字段因为多一个字段就多一个可能不一致的状态——万一你某次出栈忘了length--那长度就永远错了而且这种 bug 很难发现。4. 把六个操作串起来一个能直接跑的完整示例光看函数实现还不够得有一个main函数把它们串起来验证每个操作的行为是否符合预期。下面这个示例覆盖了初始化、判空、入栈、取栈顶、出栈、求栈长的完整流程#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; } int Push(LinkStack *s, ElemType e) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) return 0; newNode-data e; newNode-next *s; *s newNode; return 1; } int Pop(LinkStack *s, ElemType *e) { if (*s NULL) return 0; StackNode *temp *s; *e temp-data; *s temp-next; free(temp); return 1; } int GetTop(LinkStack s, ElemType *e) { if (s NULL) return 0; *e s-data; return 1; } int StackLength(LinkStack s) { int count 0; StackNode *p s; while (p ! NULL) { count; p p-next; } return count; } int main() { LinkStack s; InitStack(s); printf(初始化后是否为空: %d\n, StackEmpty(s)); for (int i 1; i 5; i) { Push(s, i * 10); } printf(入栈5个元素后栈长: %d\n, StackLength(s)); ElemType topVal; if (GetTop(s, topVal)) { printf(当前栈顶元素: %d\n, topVal); } ElemType popVal; while (Pop(s, popVal)) { printf(出栈: %d\n, popVal); } printf(全部出栈后是否为空: %d\n, StackEmpty(s)); return 0; }预期输出是初始化后是否为空: 1 入栈5个元素后栈长: 5 当前栈顶元素: 50 出栈: 50 出栈: 40 出栈: 30 出栈: 20 出栈: 10 全部出栈后是否为空: 1这个输出验证了几件事初始化后栈确实为空入栈顺序是 10、20、30、40、50栈顶是最后入的 50出栈顺序是 50、40、30、20、10符合后进先出全部出栈后又回到空状态。如果你跑出来的结果和上面不一致大概率是某个指针操作顺序写反了或者判空条件写错了。建议在Push和Pop里加几行printf打印当前top的地址和值观察指针的变化过程比干瞪眼找 bug 快得多。5. 链栈实操中最容易踩的五个坑5.1 二级指针传参漏写这是最高频的错误。Push(s, 10)写成了Push(s, 10)编译器可能只给个警告甚至不报错因为LinkStack和LinkStack *在某些情况下能隐式转换但运行时栈顶指针根本没被更新所有入栈操作都作用在一个临时拷贝上最后栈还是空的。这类 bug 的隐蔽性在于程序不崩溃只是行为不对如果你不仔细验证结果很容易漏过去。5.2free之后继续访问节点前面提过free(temp)之后temp指向的内存已经无效。但有些人为了省事会写成free(*s); *s (*s)-next;这就是典型的 use-after-free。正确的做法永远是先用临时指针保存要删的节点更新完top之后再free。5.3 忘记检查malloc返回值在 PC 上写作业可能永远遇不到malloc失败但在嵌入式或者长时间运行的服务里内存耗尽是有可能发生的。一旦malloc返回NULL而你没检查后面newNode-data e;就是空指针解引用程序直接挂掉。加一个if (newNode NULL) return 0;成本极低收益极高。5.4 出栈时数据没带出去有些实现只做了*s temp-next; free(temp);忘了*e temp-data;。这样出栈操作确实把节点删了但调用者拿不到被删的数据。如果你不需要数据那没问题但如果你需要就必须在free之前把data拷出来。顺序不能反free之后再读temp-data就是访问已释放内存。5.5 求栈长时修改了top求栈长需要遍历遍历就要用一个游标指针。如果你图省事直接用s本身去遍历比如while (s ! NULL) { s s-next; }那遍历完之后s就变成NULL了栈顶指针被破坏整个栈就丢了。必须用一个临时指针p来遍历保持s不动。6. 从链栈延伸到链式队列与双端栈链栈的这套思路——用链表头作为操作端、动态申请节点、二级指针传参——可以直接迁移到其他链式结构上。链式队列就是最直接的延伸。队列需要在一端入、另一端出所以需要两个指针front指向队头rear指向队尾。入队在rear后面接新节点并更新rear出队删front节点并更新front。你会发现链栈里先接后断的指针操作顺序、malloc检查、free前保存数据这些经验在链式队列里完全适用。双端栈是另一个有意思的变体。它用一块连续空间两端各作为一个栈的栈底两个栈顶相向增长。这种结构在顺序存储下能提高空间利用率但如果用链式实现就变成了两个独立的链栈反而失去了共享空间的意义。所以双端栈通常用顺序存储这也说明了一个道理链式和顺序不是谁替代谁而是各有各的适用场景。回到链栈本身如果你想把代码写得更工程化可以考虑几个方向。一是把LinkStack封装成一个结构体里面放top和length这样求长度就是 O(1)。二是加一个ClearStack函数一次性释放所有节点避免内存泄漏。三是把ElemType换成void *让栈能存任意类型的数据代价是调用者要自己管理内存。这些扩展都不难核心的指针操作逻辑和上面讲的完全一样。我在实际项目里用链栈最多的场景是表达式解析。解析中缀表达式转后缀表达式时需要一个运算符栈运算符的数量完全取决于输入表达式的长度事先无法预知而且解析过程中频繁入栈出栈。链栈在这个场景下表现很稳没有出现过容量问题。唯一需要注意的是解析结束后一定要把栈里剩余的节点全部free掉否则每解析一个表达式就泄漏一点内存跑久了就出问题了。