引言在上一篇文章中我们详细讲解了顺序栈的实现。顺序栈使用连续内存存储元素操作简单高效但存在两个固有限制容量需要预先分配和扩容时存在内存复制开销。链栈Linked Stack彻底解决了这些问题。它使用链表节点动态存储元素无需预分配空间没有容量上限每个元素独立分配和释放是真正意义上的无限栈。第一部分链栈的设计原理一、核心数据结构链栈由两个结构体组成// 1. 节点结构体 typedef struct Stacknode { ElemType data; // 数据域 struct Stacknode* next; // 指针域指向下一个节点 } Stacknode, *PStacknode; // 2. 栈管理结构体 typedef struct LinkStack { PStacknode top; // 栈顶指针指向最上方的节点 size_t cursize; // 当前元素个数 } LinkStack, *PLinkStack;二、设计思想对比项目顺序栈链栈存储方式连续数组离散节点栈顶位置top指向数组中的位置top指向最上方的节点栈底位置base指向数组起始隐含为top沿next走到底判空base toptop NULL容量固定需扩容无限制内存足够即可元素个数top - basecursize成员节点关系下标连续指针链接三、链栈的链接方向链栈的链接方向是从栈顶指向栈底与队列相反关键选择链栈的top永远指向最新插入的节点这样入栈和出栈都只需要操作头部节点时间复杂度 O(1)。第二部分初始化与销毁一、初始化void InitLinkStack(PLinkStack ps) { assert(ps ! NULL); ps-cursize 0; ps-top NULL; // 空栈没有节点 }初始化与顺序栈对比// 顺序栈初始化 — 需要 malloc 数组空间 void InitStack(SeqStack* ps) { ElemType* p (ElemType*)malloc(sizeof(ElemType) * STACKINITSIZE); ps-base p; ps-top p; ps-stacksize STACKINITSIZE; } // 链栈初始化 — 不需要任何分配效率更高 void InitLinkStack(PLinkStack ps) { ps-top NULL; ps-cursize 0; }二、销毁void Destroy(PLinkStack ps) { assert(ps ! NULL); while (ps-top ! NULL) { PStacknode p ps-top; // 保存当前节点 ps-top p-next; // top 后移 free(p); // 释放节点 p NULL; ps-cursize--; } // 最终top NULL, cursize 0 }销毁过程图解三、清空 vs 销毁// 清空逐个释放节点 void Clear(PLinkStack ps) { assert(ps ! NULL); while (ps-top ! NULL) { PStacknode p ps-top; ps-top p-next; free(p); } ps-cursize 0; } // 销毁和清空逻辑一样因为没有额外的管理结构需要释放 void Destroy(PLinkStack ps) { Clear(ps); // 或者直接写清空的逻辑 }注意代码中Clear函数存在 bug下面会详细分析。第三部分核心操作实现一、Push 入栈核心bool Push(PLinkStack ps, ElemType val) { assert(ps ! NULL); // 1. 创建新节点 PStacknode p (PStacknode)malloc(sizeof(Stacknode)); if (p NULL) return false; // 内存不足 p-data val; // 2. 新节点插入到 top 前面即成为新的栈顶 p-next ps-top; // 新节点的 next 指向原栈顶 ps-top p; // top 指向新节点 // 3. 计数增加 ps-cursize; return true; }入栈过程图解关键理解链栈的入栈操作本质上就是单链表的头插法。二、Pop 出栈并获取栈顶元素bool Pop(PLinkStack ps, ElemType* pval) { assert(ps ! NULL); if (Isempty(ps)) return false; // 1. 保存栈顶节点 PStacknode p ps-top; // 2. 获取数据 *pval p-data; // 3. top 后移 ps-top p-next; // 4. 释放节点 free(p); p NULL; // 5. 计数减少 ps-cursize--; return true; }出栈过程图解与顺序栈的关键区别操作顺序栈链栈出栈逻辑top指针前移不释放内存释放节点内存已出栈元素仍在数组中但逻辑上不可见被free回收获取栈顶直接读取内存通过top-data获取三、GetTop 获取栈顶元素bool GetTop(PLinkStack ps, ElemType* pval) { assert(ps ! NULL); if (Isempty(ps)) return false; *pval ps-top-data; // 直接读取不修改 top return true; }注意代码中该函数被错误命名为Getsize与获取元素个数的函数重名这是一个需要修正的 bug。四、判空bool Isempty(const PLinkStack ps) { assert(ps ! NULL); return ps-top NULL; } // 或者用 cursize 判断 bool Isempty2(const PLinkStack ps) { assert(ps ! NULL); return ps-cursize 0; }链栈的判空逻辑非常简洁top NULL即空。五、获取元素个数size_t Getsize(const PLinkStack ps) { assert(ps ! NULL); return ps-cursize; }因为有cursize成员维护计数获取大小只需 O(1) 时间不需要遍历链表。第四部分遍历与打印void Print(const PLinkStack ps) { assert(ps ! NULL); // 从栈顶向下遍历 for (PStacknode p ps-top; p ! NULL; p p-next) { printf(%c , p-data); } printf(\n); }遍历方向打印输出从栈顶到栈底 top │ ▼ ┌───┐ ┌───┐ ┌───┐ ┌───┐ │ D │──→│ C │──→│ B │──→│ A │──→ NULL └───┘ └───┘ └───┘ └───┘ ↓ ↓ ↓ ↓ 先打印 再打印 再打印 最后打印 输出D C B A第五部分代码审查与 Bug 分析学习这个的时候我就搞出一堆错误。Bug 1Clear 函数逻辑错误// ❌ 原始代码有 bug void Clear(PLinkStack ps) { assert(ps ! NULL); while (ps-top ! NULL) { PStacknode p ps-top-next; // 保存第二个节点 ps-top p-next; // 跳过第二个节点直接指向第三个 free(ps-top); // 企图释放 top逻辑混乱 ps-top p; // top 又指回第二个节点 } ps-cursize 0; }问题分析p ps-top-next保存了第二个节点ps-top p-next跳过了第一个和第二个节点free(ps-top)释放了第三个节点但此时 top 可能为 NULL第一个节点根本没有被释放造成内存泄漏正确实现// ✓ 正确的清空逻辑 void Clear(PLinkStack ps) { assert(ps ! NULL); while (ps-top ! NULL) { PStacknode p ps-top; // 保存当前要释放的节点 ps-top p-next; // top 后移 free(p); // 释放节点 } ps-cursize 0; }Bug 2函数命名冲突// ❌ 两个函数都叫 Getsize size_t Getsize(const PLinkStack ps); // 获取元素个数 bool Getsize(PLinkStack ps, ElemType* pval); // 应该是 GetTop // ✓ 正确的命名 size_t Getsize(const PLinkStack ps); // 获取元素个数 bool GetTop(PLinkStack ps, ElemType* pval); // 获取栈顶元素Bug 3Pop 函数缺少 pval 的 NULL 检查// ❌ 原始代码 bool Pop(const PLinkStack ps, ElemType* pval) { // 没有检查 pval 是否为 NULL *pval p-data; // 如果 pval NULL 会崩溃 } // ✓ 修正版本 bool Pop(PLinkStack ps, ElemType* pval) { assert(ps ! NULL); assert(pval ! NULL); // 添加 pval 检查 if (Isempty(ps)) return false; // ... }注意Pop函数不应该用const修饰ps因为Pop会修改栈状态释放节点、修改top和cursize。代码修正总结问题原始代码修正方案Clear 逻辑错误复杂且跳过了首节点逐个释放逻辑与 Destroy 相同Getsize 命名冲突两个函数同名GetTop 获取栈顶Getsize 获取大小Pop 缺少断言未检查 pval添加assert(pval ! NULL)Pop 的 const 修饰不恰当移除constPrint 的 const 修饰无建议添加const第六部分链栈 vs 顺序栈对比一、性能对比操作顺序栈链栈入栈O(1)O(1) malloc出栈O(1)O(1) free获取栈顶O(1)O(1)获取大小O(1)O(1)判空O(1)O(1)遍历O(n) 连续访问O(n) 指针跳转内存占用预分配可能浪费每个节点多一个指针二、特点对比特点顺序栈链栈内存连续性连续分散缓存友好性✅ 好❌ 差容量限制有需扩容无动态增长需要扩容操作天然支持内存利用率扩容后可能浪费按需分配无浪费实现复杂度简单稍复杂指针开销无每节点 4/8 字节三、选择建议第七部分完整代码示例修正后的链栈实现// linklist.h #pragma once #include assert.h #include stdio.h #include stdlib.h #include stdbool.h typedef char ElemType; typedef struct Stacknode { ElemType data; struct Stacknode* next; } Stacknode, *PStacknode; typedef struct LinkStack { PStacknode top; size_t cursize; } LinkStack, *PLinkStack; // 函数声明 void InitLinkStack(PLinkStack ps); size_t Getsize(const PLinkStack ps); bool Isempty(const PLinkStack ps); bool Push(PLinkStack ps, ElemType val); void Print(const PLinkStack ps); bool Pop(PLinkStack ps, ElemType* pval); bool GetTop(const PLinkStack ps, ElemType* pval); void Clear(PLinkStack ps); void Destroy(PLinkStack ps);// linklist.c #include linklist.h void InitLinkStack(PLinkStack ps) { assert(ps ! NULL); ps-cursize 0; ps-top NULL; } size_t Getsize(const PLinkStack ps) { assert(ps ! NULL); return ps-cursize; } bool Isempty(const PLinkStack ps) { assert(ps ! NULL); return ps-top NULL; } bool Push(PLinkStack ps, ElemType val) { assert(ps ! NULL); PStacknode p (PStacknode)malloc(sizeof(Stacknode)); if (p NULL) return false; p-data val; p-next ps-top; ps-top p; ps-cursize; return true; } void Print(const PLinkStack ps) { assert(ps ! NULL); for (PStacknode p ps-top; p ! NULL; p p-next) printf(%c , p-data); printf(\n); } bool Pop(PLinkStack ps, ElemType* pval) { assert(ps ! NULL); assert(pval ! NULL); if (Isempty(ps)) return false; PStacknode p ps-top; *pval p-data; ps-top p-next; free(p); ps-cursize--; return true; } bool GetTop(const PLinkStack ps, ElemType* pval) { assert(ps ! NULL); assert(pval ! NULL); if (Isempty(ps)) return false; *pval ps-top-data; return true; } void Clear(PLinkStack ps) { assert(ps ! NULL); while (ps-top ! NULL) { PStacknode p ps-top; ps-top p-next; free(p); } ps-cursize 0; } void Destroy(PLinkStack ps) { Clear(ps); }总结一、链栈的核心原理链栈 单链表的头插头删变体入栈 → 头插法出栈 → 头删法栈顶 → 链表头判空 → 判断头指针是否为 NULL二、操作复杂度速查操作时间复杂度关键步骤PushO(1)头插新节点PopO(1)删除头节点GetTopO(1)读取头节点数据GetsizeO(1)返回 cursizeIsemptyO(1)判断 top 是否为 NULLClear/DestroyO(n)逐个释放节点三、链栈的优缺点总结优点缺点✅ 无容量限制❌ 每节点有指针开销✅ 按需分配无浪费❌ 内存不连续缓存不友好✅ 无需扩容操作❌ 频繁 malloc/free 有开销✅ 每个节点独立释放❌ 无法随机访问四、一句话记忆链栈是把单链表的头当作栈顶入栈就是头插Push出栈就是头删Pop通过top指针始终指向最新插入的节点来保证 O(1) 的时间复杂度。