链栈与共享栈：C语言实现、核心原理与工程实践指南

1. 先搞清楚链栈和共享栈到底解决什么问题如果你刚开始学数据结构看到“链栈”和“共享栈”这两个词可能会觉得有点抽象。其实它们解决的都是“栈”这个基础数据结构在特定场景下的实现和优化问题。简单来说栈就是一种“后进先出”的容器想象一下叠盘子你只能从最上面拿或放。那么为什么要有链栈最常见的顺序栈用数组实现有个硬伤大小固定。你一开始声明了100个位置如果数据超过100个就“栈满”了得重新申请更大的空间很麻烦。链栈则用链表实现理论上可以“无限”增长只要内存够动态性更好特别适合你无法预估数据量上限的场景。共享栈又是什么它是一种对固定内存空间的极致利用技巧。想象一个数组两头各有一个栈顶一个从数组头开始增长一个从数组尾开始增长。这样两个栈可以共享同一块内存空间只有当两个栈顶“碰头”时才算真的满了。这在内存紧张或者需要同时管理两种特性相反的数据流时比如一个存临时数据一个存结果数据非常有用。所以这篇文章不是给你罗列概念而是带你亲手实现一遍。我会从最基础的链栈开始把初始化、入栈、出栈、判空、判满链栈的判满逻辑和顺序栈不同的每一步代码和原理都拆开讲清楚。然后我们再实现共享栈看看两个栈在同一个数组里怎么“跳舞”而不打架。最终目标是你不仅能看懂代码更能理解什么时候该用链栈什么时候该考虑共享栈以及在实际写代码时哪些边界条件最容易出错。2. 环境准备与代码框架搭建在动手写链栈和共享栈之前我们先统一开发环境。这里以C语言为例因为它最贴近数据结构的底层实现能让你看清内存和指针的运作。其他语言如C、Java的原理完全相通只是语法封装不同。你需要准备一个C语言编译器Windows上可以用MinGW或Visual Studio的MSVCLinux/macOS直接用系统自带的GCC。确保命令行能执行gcc --version。一个文本编辑器或IDEVS Code、CLion、Dev-C甚至记事本都可以。我习惯用VS Code写代码和调试比较方便。一个终端命令行窗口用来编译和运行你的程序。项目文件结构建议创建两个独立的.c文件来分别实现这样逻辑清晰。your_project_folder/ ├── linked_stack.c // 链栈的实现 ├── shared_stack.c // 共享栈的实现 └── (可选的) main.c // 用于测试的入口我们先从链栈开始。链栈的核心是节点每个节点包含数据域和指向下一个节点的指针。链栈节点定义// linked_stack.c #include stdio.h #include stdlib.h #include stdbool.h // 为了使用bool类型C99标准支持 // 定义链栈的节点 typedef struct StackNode { int data; // 数据域这里以int为例可以是任意类型 struct StackNode* next; // 指针域指向下一个节点 } StackNode; // 定义链栈通常只需要一个栈顶指针即可代表整个栈 typedef struct LinkedStack { StackNode* top; // 栈顶指针 int size; // 当前栈中元素个数可选但强烈建议加上方便判断 } LinkedStack;这里我定义了两个结构体。StackNode是链表的节点。LinkedStack代表整个栈它本质上就是封装了一个指向栈顶节点的指针。我额外加了一个size成员这不是必须的但有了它判断栈空、获取栈长度会非常方便避免了遍历整个栈的开销这是一种典型的“用空间换时间”的优化思路。3. 链栈的五大基础操作详解链栈的所有操作都围绕top指针进行。我们一个一个来实现并讨论每个操作的关键点和易错点。3.1 初始化 (InitStack)初始化就是创建一个空的链栈。此时栈里没有元素所以top指针应该指向NULLsize设为0。// 初始化链栈 bool InitLinkedStack(LinkedStack* S) { if (S NULL) { printf(错误栈指针为NULL。\n); return false; } S-top NULL; // 栈顶置空 S-size 0; // 大小归零 printf(链栈初始化成功。\n); return true; }为什么要有返回值使用bool类型需要#include stdbool.h可以明确告知调用者初始化是否成功。虽然这里失败概率低主要是传入指针为空但养成检查参数和返回状态的习惯对写出健壮的代码至关重要。3.2 判空 (IsEmpty)判断栈是否为空就看top指针是不是NULL。// 判断链栈是否为空 bool IsEmptyLinkedStack(LinkedStack* S) { if (S NULL) { printf(错误栈指针为NULL。\n); return true; // 通常将无效指针视为空避免后续操作崩溃 } return (S-top NULL); // 或者 return (S-size 0); }注意点这里同样做了空指针检查。在实际项目中这类防御性检查能帮你快速定位问题而不是遇到段错误Segmentation Fault再慢慢回溯。3.3 入栈 (Push)入栈就是在链表头部插入一个新节点。这是链栈比顺序栈入栈更“安全”的地方因为几乎不会失败除非内存耗尽。// 元素入栈 bool PushLinkedStack(LinkedStack* S, int elem) { if (S NULL) { printf(错误栈指针为NULL。\n); return false; } // 1. 创建新节点 StackNode* newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(错误内存分配失败无法入栈。\n); return false; // 内存不足入栈失败 } // 2. 填充新节点数据 newNode-data elem; // 3. 将新节点插入链表头部栈顶 newNode-next S-top; // 新节点的next指向原栈顶 S-top newNode; // 栈顶指针更新为新节点 // 4. 栈大小增加 S-size; printf(元素 %d 入栈成功。\n, elem); return true; }关键步骤解析malloc申请内存这是链式结构的核心每次入栈都动态申请一块内存。务必检查malloc返回值这是新手最容易忽略导致程序崩溃的地方。newNode-next S-top这是链表插入的核心逻辑。即使原栈为空S-top为NULL这个操作也是正确的它让新节点的next指向NULL。S-top newNode更新栈顶指针使其指向新的头节点。3.4 出栈 (Pop)出栈就是删除链表头节点并返回其数据。需要特别注意出栈前必须判断栈是否为空。// 元素出栈并通过指针参数返回出栈元素 bool PopLinkedStack(LinkedStack* S, int* elem) { if (S NULL || elem NULL) { printf(错误栈指针或元素指针为NULL。\n); return false; } // 1. 判断栈是否为空 if (IsEmptyLinkedStack(S)) { printf(错误栈为空无法出栈。\n); return false; } // 2. 获取栈顶节点及其数据 StackNode* topNode S-top; *elem topNode-data; // 将栈顶数据通过指针传回 // 3. 更新栈顶指针 S-top topNode-next; // 栈顶指针指向原栈顶的下一个节点 // 4. 释放原栈顶节点的内存 free(topNode); // 5. 栈大小减少 S-size--; printf(元素 %d 出栈成功。\n, *elem); return true; }关键步骤与易错点空栈检查这是必须的。对空栈执行出栈会导致访问非法内存S-top-data。返回值设计出栈函数通常需要返回两个信息操作是否成功、出栈的元素是什么。这里采用bool返回值表示成功与否通过一个int*指针参数elem来“带回”出栈的元素值。这是一种常见的C语言多值返回手法。内存释放free(topNode)至关重要。链式结构动态申请的内存在节点不再使用时必须手动释放否则会造成“内存泄漏”。这是链式结构与数组静态或栈上分配在管理上的最大不同。3.5 判满 (IsFull) 与获取栈顶元素 (GetTop)对于链栈“栈满”通常意味着系统内存耗尽无法再分配新节点。我们无法精确预判但可以在malloc失败时感知。因此一个简单的IsFull函数通常直接返回false或者更实际一点在Push操作里处理malloc失败的情况。// 链栈理论上不会满除非内存耗尽此函数通常返回false // 或者设计为尝试预分配一小块内存来探测但意义不大。 bool IsFullLinkedStack(LinkedStack* S) { // 简单实现总是返回false。真正的“满”在Push的malloc处判断。 return false; }获取栈顶元素也叫“Peek”或“Top”只读取数据不出栈。// 获取栈顶元素不出栈 bool GetTopLinkedStack(LinkedStack* S, int* elem) { if (S NULL || elem NULL) { printf(错误栈指针或元素指针为NULL。\n); return false; } if (IsEmptyLinkedStack(S)) { printf(错误栈为空无栈顶元素。\n); return false; } *elem S-top-data; return true; }3.6 链栈的测试与内存释放写完所有操作后一定要写一个main函数测试并且别忘了销毁栈释放所有节点内存。// 销毁链栈释放所有节点内存 void DestroyLinkedStack(LinkedStack* S) { if (S NULL) { return; } int temp; while (!IsEmptyLinkedStack(S)) { PopLinkedStack(S, temp); // 循环出栈直到栈空。Pop内部会free节点。 } // 此时 S-top 已经是 NULL, S-size 是 0 printf(链栈销毁成功所有内存已释放。\n); } // 测试函数 int main() { LinkedStack S; int value; // 1. 初始化 if (!InitLinkedStack(S)) { return -1; } // 2. 判空 printf(栈是否空 %s\n, IsEmptyLinkedStack(S) ? 是 : 否); // 3. 入栈 PushLinkedStack(S, 10); PushLinkedStack(S, 20); PushLinkedStack(S, 30); // 4. 获取栈顶 if (GetTopLinkedStack(S, value)) { printf(当前栈顶元素是%d\n, value); } // 5. 出栈 while (PopLinkedStack(S, value)) { printf(出栈元素%d\n, value); } // 6. 再次判空 printf(栈是否空 %s\n, IsEmptyLinkedStack(S) ? 是 : 否); // 7. 销毁 (虽然这里栈已空但养成好习惯) DestroyLinkedStack(S); return 0; }运行这个测试你会看到完整的操作流程。重点观察入栈、出栈的顺序以及销毁函数如何通过循环出栈来清理内存。4. 共享栈的设计与实现理解了链栈我们再看共享栈。共享栈是基于数组顺序存储实现的它在一个数组里容纳两个栈。核心设计用一个数组data[MAX_SIZE]存储元素。设定两个栈顶指针或下标top1指向栈1的栈顶元素初始为-1表示空栈。栈1从数组头部data[0]开始向尾部增长。top2指向栈2的栈顶元素初始为MAX_SIZE表示空栈。栈2从数组尾部data[MAX_SIZE-1]开始向头部增长。栈满的条件top1 1 top2。即两个栈顶指针再往前走一步就要相遇了。4.1 共享栈的结构定义与初始化// shared_stack.c #include stdio.h #include stdbool.h #define MAX_SIZE 100 // 共享栈的总容量 typedef struct SharedStack { int data[MAX_SIZE]; // 共享的存储数组 int top1; // 栈1的栈顶指针下标 int top2; // 栈2的栈顶指针下标 } SharedStack; // 初始化共享栈 bool InitSharedStack(SharedStack* S) { if (S NULL) { printf(错误栈指针为NULL。\n); return false; } S-top1 -1; // 栈1为空 S-top2 MAX_SIZE; // 栈2为空 printf(共享栈初始化成功。栈1从前往后栈2从后往前。\n); return true; }初始化时top1和top2分别指向数组的“两端之外”这是关键。4.2 共享栈的判空与判满判空需要区分是哪个栈。// 判断栈1是否为空 bool IsEmptyStack1(SharedStack* S) { return (S-top1 -1); } // 判断栈2是否为空 bool IsEmptyStack2(SharedStack* S) { return (S-top2 MAX_SIZE); } // 判断共享栈是否已满 bool IsFullSharedStack(SharedStack* S) { // 当两个栈顶指针相邻时表示栈满 return (S-top1 1 S-top2); }IsFullSharedStack的判断逻辑top1 1 top2是共享栈设计的精髓。它意味着数组中间没有任何空闲位置了。4.3 共享栈的入栈 (Push)入栈需要指定是向哪个栈添加元素。// 向栈1入栈 bool PushStack1(SharedStack* S, int elem) { if (S NULL) { return false; } if (IsFullSharedStack(S)) { printf(错误共享栈已满无法向栈1入栈。\n); return false; } // 栈1的栈顶指针先加1再赋值 S-top1; S-data[S-top1] elem; printf(元素 %d 入栈1成功。栈1顶指针%d\n, elem, S-top1); return true; } // 向栈2入栈 bool PushStack2(SharedStack* S, int elem) { if (S NULL) { return false; } if (IsFullSharedStack(S)) { printf(错误共享栈已满无法向栈2入栈。\n); return false; } // 栈2的栈顶指针先减1再赋值 S-top2--; S-data[S-top2] elem; printf(元素 %d 入栈2成功。栈2顶指针%d\n, elem, S-top2); return true; }注意两个栈的移动方向相反栈1 (top1)从-1开始加1再存数据。栈2 (top2)从MAX_SIZE开始减1再存数据。 这是实现“背靠背”增长的关键。4.4 共享栈的出栈 (Pop)出栈同样需要指定从哪个栈弹出。// 从栈1出栈 bool PopStack1(SharedStack* S, int* elem) { if (S NULL || elem NULL) { return false; } if (IsEmptyStack1(S)) { printf(错误栈1为空无法出栈。\n); return false; } *elem S-data[S-top1]; // 取栈顶元素 S-top1--; // 栈顶指针减1 printf(元素 %d 从栈1出栈成功。栈1顶指针%d\n, *elem, S-top1); return true; } // 从栈2出栈 bool PopStack2(SharedStack* S, int* elem) { if (S NULL || elem NULL) { return false; } if (IsEmptyStack2(S)) { printf(错误栈2为空无法出栈。\n); return false; } *elem S-data[S-top2]; // 取栈顶元素 S-top2; // 栈顶指针加1 printf(元素 %d 从栈2出栈成功。栈2顶指针%d\n, *elem, S-top2); return true; }注意出栈时指针移动方向与入栈时相反。栈1出栈先取data[top1]然后top1--。栈2出栈先取data[top2]然后top2。4.5 共享栈的测试int main() { SharedStack S; int val; InitSharedStack(S); // 测试栈1 printf(\n 测试栈1 \n); PushStack1(S, 1); PushStack1(S, 2); PushStack1(S, 3); PopStack1(S, val); printf(栈1出栈%d\n, val); // 测试栈2 printf(\n 测试栈2 \n); PushStack2(S, 101); PushStack2(S, 102); PopStack2(S, val); printf(栈2出栈%d\n, val); // 测试栈满 printf(\n 填满剩余空间 \n); // 根据当前top1和top2计算剩余空间并填满 // 这里省略具体循环代码逻辑是交替或连续向栈1和栈2压入数据直到IsFull返回true // 你会看到当两个栈顶指针相遇时会打印栈满错误。 printf(\n共享栈测试完成。\n); return 0; }运行这个测试观察控制台输出理解两个栈顶指针是如何相向移动的。你可以尝试修改MAX_SIZE为一个更小的数比如5然后快速压入数据更容易触发栈满条件。5. 链栈 vs 共享栈如何选择与实战要点实现完了两种栈我们来做个总结搞清楚它们的适用场景和你在实际编码中必须留意的点。5.1 核心区别与选择依据特性链栈 (Linked Stack)共享栈 (Shared Stack)存储结构链式存储节点指针顺序存储数组容量动态理论上只受内存限制固定编译时或初始化时确定 (MAX_SIZE)内存开销每个元素有额外指针开销8或4字节只有数据本身开销内存利用率高入/出栈时间复杂度O(1)O(1)访问效率需要间接寻址缓存不友好连续内存缓存友好访问速度快栈满判断malloc失败即为满罕见top1 1 top2适用场景数据量不可预知、频繁动态变化内存空间固定、需要高效利用、两个栈总量可预估选择建议当你无法预估数据量上限或者需要频繁、大量地插入删除且对内存碎片不敏感时用链栈。例如解析复杂嵌套语法如XML/JSON时的临时状态栈、函数调用栈的模拟某些语言实现、撤销操作链。当你内存空间非常紧张且固定并且恰好需要管理两个增长方向相反的数据集时用共享栈。经典例子是编译器或计算器中一个栈处理操作数一个栈处理运算符。5.2 链栈实战避坑指南内存泄漏是头号敌人每个malloc的节点最终都必须有对应的free。确保你的Pop和Destroy函数正确释放内存。可以使用valgrind(Linux) 或 CRT调试功能 (Windows) 来检测内存泄漏。空指针检查不能省任何对栈结构S或节点指针的访问前先判断是否为NULL。这能避免程序崩溃让错误更可读。size成员是好帮手虽然增加了一点空间开销但用size来判断空、获取长度时间复杂度是 O(1)。如果不用size判断栈空是 O(1)但获取长度就需要遍历整个栈是 O(n)。理解“栈满”链栈的“满”是系统层面的内存耗尽。在应用层我们通常不预先判断而是在Push时处理malloc返回的NULL。所以IsFull函数往往是个摆设。5.3 共享栈实战避坑指南MAX_SIZE的选择这是共享栈性能的关键。设太小容易栈满设太大浪费内存。需要根据业务数据量进行合理估算。栈满条件判断top1 1 top2这个条件要烂熟于心。它意味着两个栈之间没有空闲单元了。top1指向栈1最后一个元素top2指向栈2最后一个元素。指针移动方向这是最容易混淆的地方。务必画图理解栈1top1初始-1入栈先加再存(top1)出栈先取再减(top1--)。栈2top2初始MAX_SIZE入栈先减再存(--top2)出栈先取再加(top2)。 写代码时把图画在旁边对照着写。两个栈的平衡共享栈的内存利用率取决于两个栈的使用是否均衡。如果一个栈增长过快很快会导致整体“栈满”即使数组另一边还有大量空闲。这在设计使用共享栈的算法时需要考量。5.4 从“能跑”到“好用”的进阶思考当你基本操作都实现后可以思考以下问题来深化理解链栈的“遍历”虽然栈不强调遍历但有时需要打印所有元素调试时。你会怎么写注意遍历不能破坏栈结构所以你需要一个临时指针p S-top然后while(p) { print(p-data); p p-next; }。共享栈的动态扩容如果共享栈满了能否像动态数组那样扩容理论上可以但成本很高需要分配新数组拷贝数据并重新计算两个栈的位置这违背了共享栈固定内存、高效率的初衷。所以通常共享栈设计为固定大小。多栈共享两个栈可以共享那N个栈呢思路可以扩展比如将数组分成N个区间每个栈在自己的区间内增长但管理起来更复杂容易造成某个栈区满而其他栈区空的情况内存利用率可能反而不高。最后无论是链栈还是共享栈理解其指针或下标的移动规律和边界条件空、满是核心。我建议你不要只停留在看代码一定要在你自己电脑上敲一遍用调试器单步跟踪观察top指针和data数组的变化。数据结构的学习动手画图 调试跟踪比死记硬背代码有效十倍。