大家好我是CSDN的一名技术博主。最近在后台看到不少同学在复习数据结构时对链栈和共享栈的操作感到困惑尤其是在初始化、入栈、出栈这些基础操作上常常因为指针处理不当导致程序崩溃。本文将从零开始手把手带你用C语言实现链栈和共享栈不仅会给出完整的、可直接运行的代码还会深入讲解每一步的原理和容易踩的“坑”。无论你是正在准备期末考试的学生还是希望巩固基础的在职开发者这篇文章都能帮你把这块知识点彻底搞懂、会用。1. 栈与链栈核心概念扫盲在开始写代码之前我们必须先搞清楚几个核心概念。栈Stack是一种操作受限的线性表它只允许在一端称为栈顶Top进行插入和删除操作。这种“后进先出”LIFO, Last In First Out的特性使得栈在函数调用、表达式求值、括号匹配等场景中应用广泛。栈的实现主要有两种方式顺序栈和链栈。顺序栈使用数组实现。优点是访问速度快实现简单缺点是栈的大小固定容易造成空间浪费或栈溢出。链栈使用链表实现。优点是动态分配内存理论上只要内存足够就不会“栈满”缺点是每个节点需要额外的指针空间且访问速度略慢于顺序栈。链栈的本质就是一个操作受限的单链表。我们规定所有的插入入栈和删除出栈操作都在链表的头部进行。为什么是头部因为在单链表的头部进行插入和删除节点的时间复杂度是O(1)效率最高。如果把栈顶放在链表尾部那么每次入栈都需要遍历到尾部时间复杂度就变成了O(n)这是不可接受的。理解了这一点我们就能定义链栈的节点结构了。一个链栈节点至少包含两部分数据域data用来存储我们放入栈中的实际数据。指针域next用来指向下一个节点将各个节点串联起来。对于链栈本身我们只需要一个指向栈顶节点的指针通常命名为top即可。通过这个top指针我们可以访问栈顶元素并沿着next指针遍历整个栈虽然栈通常不提供遍历操作。一个空的链栈其top指针应该指向NULL。2. 环境准备与代码规范在开始实战之前我们先明确一下开发环境这对后续理解代码和排查错误至关重要。编程语言C语言。本文所有代码均使用标准C语法确保在主流编译器上均可编译运行。开发工具你可以使用任何你熟悉的IDE或编辑器例如 Visual Studio Code、Dev-C、Code::Blocks 或 CLion。在命令行下使用gcc或clang编译也是完全可行的。编译与运行我们将采用模块化编程将链栈和共享栈的实现分别放在独立的.c和.h文件中这样结构更清晰也便于复用。在开始编码前我们先约定一些重要的编程习惯和注意事项这些是写出健壮代码的基础内存管理C语言需要手动管理内存。每次malloc分配内存后一定要检查是否分配成功指针是否为NULL。使用完毕后必须用free释放防止内存泄漏。指针判空在对指针进行解引用操作如p-data之前务必先判断指针是否为NULL这是避免程序崩溃Segmentation Fault的关键。函数职责单一每个函数只完成一个明确的任务。例如Push函数只负责入栈Pop函数只负责出栈并返回数据。错误处理当操作无法完成时如对空栈执行出栈函数应通过返回值或输出参数明确地告知调用者而不是让程序默默出错。接下来我们就进入实战环节从链栈开始。3. 链栈的完整实现我们将按照“定义结构 - 初始化 - 基本操作判空、入栈、出栈、取栈顶- 销毁”的顺序一步步实现链栈。3.1 定义链栈结构首先我们定义链栈节点的结构体和链栈本身的结构。虽然理论上只需要一个top指针但这里我们用一个结构体LinkStack来包装它这样做的好处是未来如果需要增加一个记录栈中元素个数的count成员扩展起来会非常方便。// File: link_stack.h #ifndef LINK_STACK_H #define LINK_STACK_H #include stdio.h #include stdlib.h #include stdbool.h // 使用bool类型需要C99标准 // 定义栈中存储的数据类型这里以int为例可轻松改为其他类型 typedef int StackElemType; // 链栈节点结构 typedef struct StackNode { StackElemType data; // 数据域 struct StackNode *next; // 指针域指向下一个节点 } StackNode; // 链栈结构这里用结构体包装便于未来扩展如增加元素计数 typedef struct { StackNode *top; // 栈顶指针 // int count; // 可以添加一个计数器记录栈中元素个数 } LinkStack; // 函数声明 void InitStack(LinkStack *S); bool StackEmpty(LinkStack *S); bool Push(LinkStack *S, StackElemType e); bool Pop(LinkStack *S, StackElemType *e); bool GetTop(LinkStack *S, StackElemType *e); void DestroyStack(LinkStack *S); void PrintStack(LinkStack *S); // 辅助函数打印栈内容从栈顶到栈底 #endif3.2 初始化链栈初始化一个链栈非常简单就是将栈顶指针top设置为NULL表示这是一个空栈没有任何节点。// File: link_stack.c #include link_stack.h // 初始化链栈 void InitStack(LinkStack *S) { if (S NULL) { printf(Error: Stack pointer is NULL.\n); return; } S-top NULL; // 栈顶指针置空 printf(Info: LinkStack initialized successfully.\n); }关键点S-top NULL是链栈初始化的核心。一个指向NULL的top指针是判断栈为空的重要依据。3.3 判断栈空判断链栈是否为空只需要检查top指针是否为NULL。// 判断链栈是否为空 bool StackEmpty(LinkStack *S) { if (S NULL) { return true; // 如果栈结构指针为空也视为空栈或应报错 } return (S-top NULL); }3.4 入栈操作入栈Push操作就是在链表头部插入一个新节点。步骤是1. 创建新节点并存入数据2. 将新节点的next指向原栈顶3. 更新栈顶指针top指向新节点。// 入栈操作 bool Push(LinkStack *S, StackElemType e) { if (S NULL) { printf(Error: Stack pointer is NULL.\n); return false; } // 1. 创建新节点 StackNode *new_node (StackNode *)malloc(sizeof(StackNode)); if (new_node NULL) { printf(Error: Memory allocation failed for new node.\n); return false; // 内存分配失败 } // 2. 填充新节点数据 new_node-data e; // 3. 将新节点插入链表头部栈顶 new_node-next S-top; // 新节点指向原栈顶 S-top new_node; // 栈顶指针更新为新节点 printf(Info: Element %d pushed onto stack.\n, e); return true; }图解与思考这个过程类似于单链表的头插法。因为链栈没有“栈满”的概念除非系统内存耗尽所以Push操作通常总是成功的。代码中malloc失败是唯一的失败情况。3.5 出栈操作出栈Pop操作就是删除链表头部的节点栈顶节点并返回其数据。步骤是1. 检查栈是否为空2. 保存栈顶节点的数据和地址3. 更新栈顶指针指向下一个节点4. 释放原栈顶节点的内存。// 出栈操作 bool Pop(LinkStack *S, StackElemType *e) { if (S NULL || e NULL) { printf(Error: Invalid pointer.\n); return false; } // 1. 检查栈是否为空 if (StackEmpty(S)) { printf(Error: Cannot pop from an empty stack.\n); return false; } // 2. 保存栈顶节点的数据和地址 StackNode *temp S-top; // temp指向待删除的栈顶节点 *e temp-data; // 通过指针e返回栈顶元素的值 // 3. 更新栈顶指针 S-top temp-next; // 栈顶指针指向原栈顶的下一个节点 // 4. 释放原栈顶节点内存 free(temp); temp NULL; // 良好习惯防止野指针 printf(Info: Element %d popped from stack.\n, *e); return true; }关键点出栈前必须判断栈是否为空对空栈执行出栈是逻辑错误。另外free之后将临时指针temp置为NULL是一个好习惯可以避免后续误用。3.6 获取栈顶元素获取栈顶元素GetTop/Peek与出栈类似但它只“读取”而不“删除”栈顶节点。因此它不需要修改栈的结构也无需释放内存。// 获取栈顶元素不删除 bool GetTop(LinkStack *S, StackElemType *e) { if (S NULL || e NULL) { printf(Error: Invalid pointer.\n); return false; } if (StackEmpty(S)) { printf(Error: Stack is empty, no top element.\n); return false; } *e S-top-data; // 直接读取栈顶节点的数据 printf(Info: Top element is %d.\n, *e); return true; }3.7 销毁链栈由于链栈的节点内存是动态分配的当栈不再使用时我们必须遍历整个栈逐个释放所有节点的内存防止内存泄漏。// 销毁链栈 void DestroyStack(LinkStack *S) { if (S NULL) { return; } StackNode *p S-top; StackNode *temp; while (p ! NULL) { temp p; // temp指向当前待释放节点 p p-next; // p移动到下一个节点 free(temp); // 释放当前节点 } S-top NULL; // 最终将栈顶指针置空 printf(Info: LinkStack destroyed successfully.\n); }3.8 测试链栈最后我们编写一个main函数来测试上述所有操作。// File: main_link_stack.c #include link_stack.h int main() { LinkStack S; StackElemType e; printf( Testing LinkStack \n); // 1. 初始化 InitStack(S); // 2. 判断空栈 printf(Is stack empty? %s\n, StackEmpty(S) ? Yes : No); // 3. 入栈一系列元素 Push(S, 10); Push(S, 20); Push(S, 30); PrintStack(S); // 假设已实现打印栈内容 // 4. 获取栈顶元素 if (GetTop(S, e)) { printf(Top element is: %d\n, e); } // 5. 出栈 if (Pop(S, e)) { printf(Popped element: %d\n, e); } PrintStack(S); // 6. 继续出栈直到空 while (!StackEmpty(S)) { Pop(S, e); printf(Popped: %d\n, e); } // 7. 尝试对空栈出栈应报错 if (!Pop(S, e)) { printf(Correctly handled pop from empty stack.\n); } // 8. 销毁栈 DestroyStack(S); return 0; }你需要实现一个简单的PrintStack函数来可视化栈的内容。这个函数会从栈顶开始遍历到栈底。// 在 link_stack.c 中添加 void PrintStack(LinkStack *S) { if (S NULL) { printf(Stack is NULL.\n); return; } if (StackEmpty(S)) { printf(Stack is empty.\n); return; } printf(Stack (top - bottom): ); StackNode *p S-top; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }编译与运行 假设你的文件名为link_stack.h,link_stack.c,main_link_stack.c。 在命令行中使用 gcc 编译gcc -o link_stack_test main_link_stack.c link_stack.c ./link_stack_test预期你会看到一系列信息输出展示了栈的初始化、入栈、出栈、判空、取栈顶和销毁的完整过程。4. 共享栈的完整实现理解了链栈我们再来看看共享栈。共享栈是顺序栈的一种巧妙应用它利用一个数组的两端分别作为两个栈的栈底两个栈的栈顶向中间增长。这样可以更有效地利用数组空间只有整个数组空间被占满时才会发生“栈满”。核心思想一个数组data[MAXSIZE]下标0的一端作为栈1的栈底栈1的栈顶指针top1初始为-1向数组下标增大的方向增长。下标MAXSIZE-1的一端作为栈2的栈底栈2的栈顶指针top2初始为MAXSIZE向数组下标减小的方向增长。当top1 1 top2时表示栈满。4.1 定义共享栈结构// File: shared_stack.h #ifndef SHARED_STACK_H #define SHARED_STACK_H #include stdio.h #include stdlib.h #include stdbool.h #define MAXSIZE 100 // 共享栈的最大容量 typedef int SharedStackElemType; // 共享栈结构 typedef struct { SharedStackElemType data[MAXSIZE]; // 存储元素的数组 int top1; // 栈1的栈顶指针初始为-1 int top2; // 栈2的栈顶指针初始为MAXSIZE } SharedStack; // 函数声明 void InitSharedStack(SharedStack *S); bool Stack1Empty(SharedStack *S); bool Stack2Empty(SharedStack *S); bool StackFull(SharedStack *S); bool Push1(SharedStack *S, SharedStackElemType e); bool Push2(SharedStack *S, SharedStackElemType e); bool Pop1(SharedStack *S, SharedStackElemType *e); bool Pop2(SharedStack *S, SharedStackElemType *e); bool GetTop1(SharedStack *S, SharedStackElemType *e); bool GetTop2(SharedStack *S, SharedStackElemType *e); #endif4.2 初始化共享栈初始化就是将两个栈顶指针置于各自的起始位置。// File: shared_stack.c #include shared_stack.h // 初始化共享栈 void InitSharedStack(SharedStack *S) { if (S NULL) return; S-top1 -1; // 栈1空 S-top2 MAXSIZE; // 栈2空 printf(Info: SharedStack initialized. top1%d, top2%d\n, S-top1, S-top2); }4.3 判断栈空与栈满这是共享栈操作的基础。// 判断栈1是否为空 bool Stack1Empty(SharedStack *S) { return (S-top1 -1); } // 判断栈2是否为空 bool Stack2Empty(SharedStack *S) { return (S-top2 MAXSIZE); } // 判断共享栈是否已满 bool StackFull(SharedStack *S) { // 栈满的条件两个栈顶指针相邻 return (S-top1 1 S-top2); }4.4 入栈操作栈1和栈2入栈前需要判断栈是否已满。// 向栈1入栈 bool Push1(SharedStack *S, SharedStackElemType e) { if (StackFull(S)) { printf(Error: SharedStack is full. Cannot push %d to Stack1.\n, e); return false; } S-data[(S-top1)] e; // top1先加1再赋值 printf(Info: Element %d pushed to Stack1. top1%d\n, e, S-top1); return true; } // 向栈2入栈 bool Push2(SharedStack *S, SharedStackElemType e) { if (StackFull(S)) { printf(Error: SharedStack is full. Cannot push %d to Stack2.\n, e); return false; } S-data[--(S-top2)] e; // top2先减1再赋值 printf(Info: Element %d pushed to Stack2. top2%d\n, e, S-top2); return true; }注意栈1的top1是先增后赋值栈2的top2是--先减后赋值因为它们增长方向相反。4.5 出栈操作栈1和栈2出栈前需要判断对应的栈是否为空。// 从栈1出栈 bool Pop1(SharedStack *S, SharedStackElemType *e) { if (Stack1Empty(S)) { printf(Error: Stack1 is empty. Cannot pop.\n); return false; } *e S-data[(S-top1)--]; // 先取值top1再减1 printf(Info: Element %d popped from Stack1. top1%d\n, *e, S-top1); return true; } // 从栈2出栈 bool Pop2(SharedStack *S, SharedStackElemType *e) { if (Stack2Empty(S)) { printf(Error: Stack2 is empty. Cannot pop.\n); return false; } *e S-data[(S-top2)]; // 先取值top2再加1 printf(Info: Element %d popped from Stack2. top2%d\n, *e, S-top2); return true; }4.6 获取栈顶元素// 获取栈1栈顶元素 bool GetTop1(SharedStack *S, SharedStackElemType *e) { if (Stack1Empty(S)) { printf(Error: Stack1 is empty.\n); return false; } *e S-data[S-top1]; return true; } // 获取栈2栈顶元素 bool GetTop2(SharedStack *S, SharedStackElemType *e) { if (Stack2Empty(S)) { printf(Error: Stack2 is empty.\n); return false; } *e S-data[S-top2]; return true; }4.7 测试共享栈编写一个测试主函数来验证共享栈的功能。// File: main_shared_stack.c #include shared_stack.h int main() { SharedStack S; SharedStackElemType e; printf( Testing SharedStack \n); InitSharedStack(S); // 测试栈1 printf(\n--- Operating on Stack1 ---\n); Push1(S, 1); Push1(S, 2); Push1(S, 3); GetTop1(S, e); printf(Top of Stack1 is: %d\n, e); // 测试栈2 printf(\n--- Operating on Stack2 ---\n); Push2(S, 99); Push2(S, 98); Push2(S, 97); GetTop2(S, e); printf(Top of Stack2 is: %d\n, e); // 交叉操作 printf(\n--- Mixed Operations ---\n); Pop1(S, e); printf(Popped from Stack1: %d\n, e); Push2(S, 96); // 尝试填满栈 printf(\n--- Filling the stack ---\n); // 根据MAXSIZE100我们已经用了347个位置还可以继续压入元素直到栈满 // 这里用一个循环快速填充仅作演示实际需根据剩余空间计算 for(int i 0; i 90; i) { // 填充栈1 if(!Push1(S, i10)) break; } for(int i 0; i 90; i) { // 填充栈2 if(!Push2(S, 200-i)) break; } // 此时应触发栈满 printf(Trying to push to full stack...\n); if (!Push1(S, 999)) { printf(Correctly reported stack full.\n); } return 0; }5. 常见问题与排查思路在实际编写和调试链栈与共享栈代码时你可能会遇到以下典型问题问题现象可能原因排查思路与解决方案程序运行崩溃Segmentation Fault1. 未初始化栈指针就进行操作。2. 对NULL指针进行解引用如S-top当S为NULL时。3. 出栈时栈已空但仍尝试访问S-top-data。4.malloc失败后仍使用返回的NULL指针。1.务必在main函数中声明栈变量后立即调用初始化函数。2. 在所有函数入口处检查传入的指针参数是否为NULL。3. 在执行Pop、GetTop等操作前务必先调用StackEmpty判断。4. 检查malloc返回值如果为NULL应打印错误信息并安全返回。内存泄漏只malloc不free。链栈的节点在出栈或销毁时未释放内存。1. 确保Pop操作中在移除节点后调用free。2. 实现并调用DestroyStack函数在程序结束或栈不再使用时释放所有节点内存。3. 可以使用valgrind等工具检测内存泄漏。共享栈操作混乱1. 入栈/出栈时top1和top2的增减方向搞反。2. 栈满条件判断错误 (top11 top2)。3. 栈空条件判断错误 (top1 -1或top2 MAXSIZE)。1. 牢记栈1向下标增大方向增长 (top1)栈2向下标减小方向增长 (--top2)。2. 画图理解用纸笔画出一个数组标出top1和top2的初始位置和移动方向。3. 仔细核对StackFull、Stack1Empty、Stack2Empty函数的逻辑。编译错误未定义引用没有将所有的.c文件一起编译链接。使用gcc时确保在命令行中列出了所有需要的源文件gcc -o program main.c stack_impl.c逻辑错误操作结果不对1. 入栈出栈顺序不符合LIFO。2. 获取的栈顶元素不是最后入栈的。1. 单步调试。在IDE中设置断点观察每次Push和Pop后top指针和节点数据的变化。2. 增加PrintStack这类辅助函数在关键步骤后打印栈的完整状态便于肉眼检查。6. 最佳实践与工程建议掌握了基础操作后如何写出更健壮、更易维护的栈代码呢以下是一些进阶建议封装与抽象就像我们做的那样将栈的数据结构和操作封装在独立的.h和.c文件中。使用者只需要包含头文件并调用接口无需关心内部是实现为链栈还是共享栈。这符合软件工程的高内聚、低耦合原则。增强健壮性参数检查所有对外的接口函数都应首先检查传入的指针参数是否有效非NULL。返回值设计操作类函数如Push,Pop使用bool类型返回成功/失败并通过输出参数指针返回数据。这样调用者可以明确知道操作结果。资源管理对于链栈malloc和free必须成对出现。考虑在DestroyStack中增加日志记录释放了多少节点。考虑扩展性数据类型泛化我们的示例中StackElemType被定义为int。在实际项目中你可以很容易地将其改为typedef void* StackElemType来存储任意类型的指针或者使用宏、模板C来实现泛型栈。增加元信息在LinkStack结构体中增加一个int count成员用来实时记录栈中元素个数。这样StackEmpty和求栈长度的操作可以瞬间完成O(1)但需要在Push和Pop中维护这个计数器。共享栈的应用场景共享栈并非为了炫技它有实际用途。一个经典的场景是双向栈当一个问题需要从两个方向同时处理数据时例如快速排序的非递归实现中需要同时维护两个待排序区间栈使用共享栈可以节省内存。另一个场景是内存分配器从堆的两端分别分配内存给不同用途的对象。测试驱动在实现复杂数据结构时养成边写边测的习惯。为每个函数编写简单的测试用例特别是边界情况空栈时的操作、满栈对于共享栈时的操作、单元素栈的操作等。性能考量链栈每次Push和Pop都涉及动态内存分配/释放这在频繁操作时可能成为性能瓶颈。如果栈的大小相对稳定且可预估顺序栈或共享栈通常是更好的选择因为数组访问具有更好的局部性速度更快。共享栈访问是O(1)但空间是静态分配的。如果无法准确预估两个栈的总容量可能会浪费空间分配过大或限制使用分配过小。通过本文从概念到代码从基础操作到问题排查和最佳实践的完整梳理相信你已经对链栈和共享栈有了透彻的理解。数据结构的学习关键在于动手建议你抛开本文自己从头实现一遍并尝试用栈去解决一些经典问题例如括号匹配、表达式求值、非递归的深度优先搜索等这样才能真正内化知识在未来的项目和面试中游刃有余。 C语言实现链栈与共享栈：从原理到代码实战
大家好我是CSDN的一名技术博主。最近在后台看到不少同学在复习数据结构时对链栈和共享栈的操作感到困惑尤其是在初始化、入栈、出栈这些基础操作上常常因为指针处理不当导致程序崩溃。本文将从零开始手把手带你用C语言实现链栈和共享栈不仅会给出完整的、可直接运行的代码还会深入讲解每一步的原理和容易踩的“坑”。无论你是正在准备期末考试的学生还是希望巩固基础的在职开发者这篇文章都能帮你把这块知识点彻底搞懂、会用。1. 栈与链栈核心概念扫盲在开始写代码之前我们必须先搞清楚几个核心概念。栈Stack是一种操作受限的线性表它只允许在一端称为栈顶Top进行插入和删除操作。这种“后进先出”LIFO, Last In First Out的特性使得栈在函数调用、表达式求值、括号匹配等场景中应用广泛。栈的实现主要有两种方式顺序栈和链栈。顺序栈使用数组实现。优点是访问速度快实现简单缺点是栈的大小固定容易造成空间浪费或栈溢出。链栈使用链表实现。优点是动态分配内存理论上只要内存足够就不会“栈满”缺点是每个节点需要额外的指针空间且访问速度略慢于顺序栈。链栈的本质就是一个操作受限的单链表。我们规定所有的插入入栈和删除出栈操作都在链表的头部进行。为什么是头部因为在单链表的头部进行插入和删除节点的时间复杂度是O(1)效率最高。如果把栈顶放在链表尾部那么每次入栈都需要遍历到尾部时间复杂度就变成了O(n)这是不可接受的。理解了这一点我们就能定义链栈的节点结构了。一个链栈节点至少包含两部分数据域data用来存储我们放入栈中的实际数据。指针域next用来指向下一个节点将各个节点串联起来。对于链栈本身我们只需要一个指向栈顶节点的指针通常命名为top即可。通过这个top指针我们可以访问栈顶元素并沿着next指针遍历整个栈虽然栈通常不提供遍历操作。一个空的链栈其top指针应该指向NULL。2. 环境准备与代码规范在开始实战之前我们先明确一下开发环境这对后续理解代码和排查错误至关重要。编程语言C语言。本文所有代码均使用标准C语法确保在主流编译器上均可编译运行。开发工具你可以使用任何你熟悉的IDE或编辑器例如 Visual Studio Code、Dev-C、Code::Blocks 或 CLion。在命令行下使用gcc或clang编译也是完全可行的。编译与运行我们将采用模块化编程将链栈和共享栈的实现分别放在独立的.c和.h文件中这样结构更清晰也便于复用。在开始编码前我们先约定一些重要的编程习惯和注意事项这些是写出健壮代码的基础内存管理C语言需要手动管理内存。每次malloc分配内存后一定要检查是否分配成功指针是否为NULL。使用完毕后必须用free释放防止内存泄漏。指针判空在对指针进行解引用操作如p-data之前务必先判断指针是否为NULL这是避免程序崩溃Segmentation Fault的关键。函数职责单一每个函数只完成一个明确的任务。例如Push函数只负责入栈Pop函数只负责出栈并返回数据。错误处理当操作无法完成时如对空栈执行出栈函数应通过返回值或输出参数明确地告知调用者而不是让程序默默出错。接下来我们就进入实战环节从链栈开始。3. 链栈的完整实现我们将按照“定义结构 - 初始化 - 基本操作判空、入栈、出栈、取栈顶- 销毁”的顺序一步步实现链栈。3.1 定义链栈结构首先我们定义链栈节点的结构体和链栈本身的结构。虽然理论上只需要一个top指针但这里我们用一个结构体LinkStack来包装它这样做的好处是未来如果需要增加一个记录栈中元素个数的count成员扩展起来会非常方便。// File: link_stack.h #ifndef LINK_STACK_H #define LINK_STACK_H #include stdio.h #include stdlib.h #include stdbool.h // 使用bool类型需要C99标准 // 定义栈中存储的数据类型这里以int为例可轻松改为其他类型 typedef int StackElemType; // 链栈节点结构 typedef struct StackNode { StackElemType data; // 数据域 struct StackNode *next; // 指针域指向下一个节点 } StackNode; // 链栈结构这里用结构体包装便于未来扩展如增加元素计数 typedef struct { StackNode *top; // 栈顶指针 // int count; // 可以添加一个计数器记录栈中元素个数 } LinkStack; // 函数声明 void InitStack(LinkStack *S); bool StackEmpty(LinkStack *S); bool Push(LinkStack *S, StackElemType e); bool Pop(LinkStack *S, StackElemType *e); bool GetTop(LinkStack *S, StackElemType *e); void DestroyStack(LinkStack *S); void PrintStack(LinkStack *S); // 辅助函数打印栈内容从栈顶到栈底 #endif3.2 初始化链栈初始化一个链栈非常简单就是将栈顶指针top设置为NULL表示这是一个空栈没有任何节点。// File: link_stack.c #include link_stack.h // 初始化链栈 void InitStack(LinkStack *S) { if (S NULL) { printf(Error: Stack pointer is NULL.\n); return; } S-top NULL; // 栈顶指针置空 printf(Info: LinkStack initialized successfully.\n); }关键点S-top NULL是链栈初始化的核心。一个指向NULL的top指针是判断栈为空的重要依据。3.3 判断栈空判断链栈是否为空只需要检查top指针是否为NULL。// 判断链栈是否为空 bool StackEmpty(LinkStack *S) { if (S NULL) { return true; // 如果栈结构指针为空也视为空栈或应报错 } return (S-top NULL); }3.4 入栈操作入栈Push操作就是在链表头部插入一个新节点。步骤是1. 创建新节点并存入数据2. 将新节点的next指向原栈顶3. 更新栈顶指针top指向新节点。// 入栈操作 bool Push(LinkStack *S, StackElemType e) { if (S NULL) { printf(Error: Stack pointer is NULL.\n); return false; } // 1. 创建新节点 StackNode *new_node (StackNode *)malloc(sizeof(StackNode)); if (new_node NULL) { printf(Error: Memory allocation failed for new node.\n); return false; // 内存分配失败 } // 2. 填充新节点数据 new_node-data e; // 3. 将新节点插入链表头部栈顶 new_node-next S-top; // 新节点指向原栈顶 S-top new_node; // 栈顶指针更新为新节点 printf(Info: Element %d pushed onto stack.\n, e); return true; }图解与思考这个过程类似于单链表的头插法。因为链栈没有“栈满”的概念除非系统内存耗尽所以Push操作通常总是成功的。代码中malloc失败是唯一的失败情况。3.5 出栈操作出栈Pop操作就是删除链表头部的节点栈顶节点并返回其数据。步骤是1. 检查栈是否为空2. 保存栈顶节点的数据和地址3. 更新栈顶指针指向下一个节点4. 释放原栈顶节点的内存。// 出栈操作 bool Pop(LinkStack *S, StackElemType *e) { if (S NULL || e NULL) { printf(Error: Invalid pointer.\n); return false; } // 1. 检查栈是否为空 if (StackEmpty(S)) { printf(Error: Cannot pop from an empty stack.\n); return false; } // 2. 保存栈顶节点的数据和地址 StackNode *temp S-top; // temp指向待删除的栈顶节点 *e temp-data; // 通过指针e返回栈顶元素的值 // 3. 更新栈顶指针 S-top temp-next; // 栈顶指针指向原栈顶的下一个节点 // 4. 释放原栈顶节点内存 free(temp); temp NULL; // 良好习惯防止野指针 printf(Info: Element %d popped from stack.\n, *e); return true; }关键点出栈前必须判断栈是否为空对空栈执行出栈是逻辑错误。另外free之后将临时指针temp置为NULL是一个好习惯可以避免后续误用。3.6 获取栈顶元素获取栈顶元素GetTop/Peek与出栈类似但它只“读取”而不“删除”栈顶节点。因此它不需要修改栈的结构也无需释放内存。// 获取栈顶元素不删除 bool GetTop(LinkStack *S, StackElemType *e) { if (S NULL || e NULL) { printf(Error: Invalid pointer.\n); return false; } if (StackEmpty(S)) { printf(Error: Stack is empty, no top element.\n); return false; } *e S-top-data; // 直接读取栈顶节点的数据 printf(Info: Top element is %d.\n, *e); return true; }3.7 销毁链栈由于链栈的节点内存是动态分配的当栈不再使用时我们必须遍历整个栈逐个释放所有节点的内存防止内存泄漏。// 销毁链栈 void DestroyStack(LinkStack *S) { if (S NULL) { return; } StackNode *p S-top; StackNode *temp; while (p ! NULL) { temp p; // temp指向当前待释放节点 p p-next; // p移动到下一个节点 free(temp); // 释放当前节点 } S-top NULL; // 最终将栈顶指针置空 printf(Info: LinkStack destroyed successfully.\n); }3.8 测试链栈最后我们编写一个main函数来测试上述所有操作。// File: main_link_stack.c #include link_stack.h int main() { LinkStack S; StackElemType e; printf( Testing LinkStack \n); // 1. 初始化 InitStack(S); // 2. 判断空栈 printf(Is stack empty? %s\n, StackEmpty(S) ? Yes : No); // 3. 入栈一系列元素 Push(S, 10); Push(S, 20); Push(S, 30); PrintStack(S); // 假设已实现打印栈内容 // 4. 获取栈顶元素 if (GetTop(S, e)) { printf(Top element is: %d\n, e); } // 5. 出栈 if (Pop(S, e)) { printf(Popped element: %d\n, e); } PrintStack(S); // 6. 继续出栈直到空 while (!StackEmpty(S)) { Pop(S, e); printf(Popped: %d\n, e); } // 7. 尝试对空栈出栈应报错 if (!Pop(S, e)) { printf(Correctly handled pop from empty stack.\n); } // 8. 销毁栈 DestroyStack(S); return 0; }你需要实现一个简单的PrintStack函数来可视化栈的内容。这个函数会从栈顶开始遍历到栈底。// 在 link_stack.c 中添加 void PrintStack(LinkStack *S) { if (S NULL) { printf(Stack is NULL.\n); return; } if (StackEmpty(S)) { printf(Stack is empty.\n); return; } printf(Stack (top - bottom): ); StackNode *p S-top; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }编译与运行 假设你的文件名为link_stack.h,link_stack.c,main_link_stack.c。 在命令行中使用 gcc 编译gcc -o link_stack_test main_link_stack.c link_stack.c ./link_stack_test预期你会看到一系列信息输出展示了栈的初始化、入栈、出栈、判空、取栈顶和销毁的完整过程。4. 共享栈的完整实现理解了链栈我们再来看看共享栈。共享栈是顺序栈的一种巧妙应用它利用一个数组的两端分别作为两个栈的栈底两个栈的栈顶向中间增长。这样可以更有效地利用数组空间只有整个数组空间被占满时才会发生“栈满”。核心思想一个数组data[MAXSIZE]下标0的一端作为栈1的栈底栈1的栈顶指针top1初始为-1向数组下标增大的方向增长。下标MAXSIZE-1的一端作为栈2的栈底栈2的栈顶指针top2初始为MAXSIZE向数组下标减小的方向增长。当top1 1 top2时表示栈满。4.1 定义共享栈结构// File: shared_stack.h #ifndef SHARED_STACK_H #define SHARED_STACK_H #include stdio.h #include stdlib.h #include stdbool.h #define MAXSIZE 100 // 共享栈的最大容量 typedef int SharedStackElemType; // 共享栈结构 typedef struct { SharedStackElemType data[MAXSIZE]; // 存储元素的数组 int top1; // 栈1的栈顶指针初始为-1 int top2; // 栈2的栈顶指针初始为MAXSIZE } SharedStack; // 函数声明 void InitSharedStack(SharedStack *S); bool Stack1Empty(SharedStack *S); bool Stack2Empty(SharedStack *S); bool StackFull(SharedStack *S); bool Push1(SharedStack *S, SharedStackElemType e); bool Push2(SharedStack *S, SharedStackElemType e); bool Pop1(SharedStack *S, SharedStackElemType *e); bool Pop2(SharedStack *S, SharedStackElemType *e); bool GetTop1(SharedStack *S, SharedStackElemType *e); bool GetTop2(SharedStack *S, SharedStackElemType *e); #endif4.2 初始化共享栈初始化就是将两个栈顶指针置于各自的起始位置。// File: shared_stack.c #include shared_stack.h // 初始化共享栈 void InitSharedStack(SharedStack *S) { if (S NULL) return; S-top1 -1; // 栈1空 S-top2 MAXSIZE; // 栈2空 printf(Info: SharedStack initialized. top1%d, top2%d\n, S-top1, S-top2); }4.3 判断栈空与栈满这是共享栈操作的基础。// 判断栈1是否为空 bool Stack1Empty(SharedStack *S) { return (S-top1 -1); } // 判断栈2是否为空 bool Stack2Empty(SharedStack *S) { return (S-top2 MAXSIZE); } // 判断共享栈是否已满 bool StackFull(SharedStack *S) { // 栈满的条件两个栈顶指针相邻 return (S-top1 1 S-top2); }4.4 入栈操作栈1和栈2入栈前需要判断栈是否已满。// 向栈1入栈 bool Push1(SharedStack *S, SharedStackElemType e) { if (StackFull(S)) { printf(Error: SharedStack is full. Cannot push %d to Stack1.\n, e); return false; } S-data[(S-top1)] e; // top1先加1再赋值 printf(Info: Element %d pushed to Stack1. top1%d\n, e, S-top1); return true; } // 向栈2入栈 bool Push2(SharedStack *S, SharedStackElemType e) { if (StackFull(S)) { printf(Error: SharedStack is full. Cannot push %d to Stack2.\n, e); return false; } S-data[--(S-top2)] e; // top2先减1再赋值 printf(Info: Element %d pushed to Stack2. top2%d\n, e, S-top2); return true; }注意栈1的top1是先增后赋值栈2的top2是--先减后赋值因为它们增长方向相反。4.5 出栈操作栈1和栈2出栈前需要判断对应的栈是否为空。// 从栈1出栈 bool Pop1(SharedStack *S, SharedStackElemType *e) { if (Stack1Empty(S)) { printf(Error: Stack1 is empty. Cannot pop.\n); return false; } *e S-data[(S-top1)--]; // 先取值top1再减1 printf(Info: Element %d popped from Stack1. top1%d\n, *e, S-top1); return true; } // 从栈2出栈 bool Pop2(SharedStack *S, SharedStackElemType *e) { if (Stack2Empty(S)) { printf(Error: Stack2 is empty. Cannot pop.\n); return false; } *e S-data[(S-top2)]; // 先取值top2再加1 printf(Info: Element %d popped from Stack2. top2%d\n, *e, S-top2); return true; }4.6 获取栈顶元素// 获取栈1栈顶元素 bool GetTop1(SharedStack *S, SharedStackElemType *e) { if (Stack1Empty(S)) { printf(Error: Stack1 is empty.\n); return false; } *e S-data[S-top1]; return true; } // 获取栈2栈顶元素 bool GetTop2(SharedStack *S, SharedStackElemType *e) { if (Stack2Empty(S)) { printf(Error: Stack2 is empty.\n); return false; } *e S-data[S-top2]; return true; }4.7 测试共享栈编写一个测试主函数来验证共享栈的功能。// File: main_shared_stack.c #include shared_stack.h int main() { SharedStack S; SharedStackElemType e; printf( Testing SharedStack \n); InitSharedStack(S); // 测试栈1 printf(\n--- Operating on Stack1 ---\n); Push1(S, 1); Push1(S, 2); Push1(S, 3); GetTop1(S, e); printf(Top of Stack1 is: %d\n, e); // 测试栈2 printf(\n--- Operating on Stack2 ---\n); Push2(S, 99); Push2(S, 98); Push2(S, 97); GetTop2(S, e); printf(Top of Stack2 is: %d\n, e); // 交叉操作 printf(\n--- Mixed Operations ---\n); Pop1(S, e); printf(Popped from Stack1: %d\n, e); Push2(S, 96); // 尝试填满栈 printf(\n--- Filling the stack ---\n); // 根据MAXSIZE100我们已经用了347个位置还可以继续压入元素直到栈满 // 这里用一个循环快速填充仅作演示实际需根据剩余空间计算 for(int i 0; i 90; i) { // 填充栈1 if(!Push1(S, i10)) break; } for(int i 0; i 90; i) { // 填充栈2 if(!Push2(S, 200-i)) break; } // 此时应触发栈满 printf(Trying to push to full stack...\n); if (!Push1(S, 999)) { printf(Correctly reported stack full.\n); } return 0; }5. 常见问题与排查思路在实际编写和调试链栈与共享栈代码时你可能会遇到以下典型问题问题现象可能原因排查思路与解决方案程序运行崩溃Segmentation Fault1. 未初始化栈指针就进行操作。2. 对NULL指针进行解引用如S-top当S为NULL时。3. 出栈时栈已空但仍尝试访问S-top-data。4.malloc失败后仍使用返回的NULL指针。1.务必在main函数中声明栈变量后立即调用初始化函数。2. 在所有函数入口处检查传入的指针参数是否为NULL。3. 在执行Pop、GetTop等操作前务必先调用StackEmpty判断。4. 检查malloc返回值如果为NULL应打印错误信息并安全返回。内存泄漏只malloc不free。链栈的节点在出栈或销毁时未释放内存。1. 确保Pop操作中在移除节点后调用free。2. 实现并调用DestroyStack函数在程序结束或栈不再使用时释放所有节点内存。3. 可以使用valgrind等工具检测内存泄漏。共享栈操作混乱1. 入栈/出栈时top1和top2的增减方向搞反。2. 栈满条件判断错误 (top11 top2)。3. 栈空条件判断错误 (top1 -1或top2 MAXSIZE)。1. 牢记栈1向下标增大方向增长 (top1)栈2向下标减小方向增长 (--top2)。2. 画图理解用纸笔画出一个数组标出top1和top2的初始位置和移动方向。3. 仔细核对StackFull、Stack1Empty、Stack2Empty函数的逻辑。编译错误未定义引用没有将所有的.c文件一起编译链接。使用gcc时确保在命令行中列出了所有需要的源文件gcc -o program main.c stack_impl.c逻辑错误操作结果不对1. 入栈出栈顺序不符合LIFO。2. 获取的栈顶元素不是最后入栈的。1. 单步调试。在IDE中设置断点观察每次Push和Pop后top指针和节点数据的变化。2. 增加PrintStack这类辅助函数在关键步骤后打印栈的完整状态便于肉眼检查。6. 最佳实践与工程建议掌握了基础操作后如何写出更健壮、更易维护的栈代码呢以下是一些进阶建议封装与抽象就像我们做的那样将栈的数据结构和操作封装在独立的.h和.c文件中。使用者只需要包含头文件并调用接口无需关心内部是实现为链栈还是共享栈。这符合软件工程的高内聚、低耦合原则。增强健壮性参数检查所有对外的接口函数都应首先检查传入的指针参数是否有效非NULL。返回值设计操作类函数如Push,Pop使用bool类型返回成功/失败并通过输出参数指针返回数据。这样调用者可以明确知道操作结果。资源管理对于链栈malloc和free必须成对出现。考虑在DestroyStack中增加日志记录释放了多少节点。考虑扩展性数据类型泛化我们的示例中StackElemType被定义为int。在实际项目中你可以很容易地将其改为typedef void* StackElemType来存储任意类型的指针或者使用宏、模板C来实现泛型栈。增加元信息在LinkStack结构体中增加一个int count成员用来实时记录栈中元素个数。这样StackEmpty和求栈长度的操作可以瞬间完成O(1)但需要在Push和Pop中维护这个计数器。共享栈的应用场景共享栈并非为了炫技它有实际用途。一个经典的场景是双向栈当一个问题需要从两个方向同时处理数据时例如快速排序的非递归实现中需要同时维护两个待排序区间栈使用共享栈可以节省内存。另一个场景是内存分配器从堆的两端分别分配内存给不同用途的对象。测试驱动在实现复杂数据结构时养成边写边测的习惯。为每个函数编写简单的测试用例特别是边界情况空栈时的操作、满栈对于共享栈时的操作、单元素栈的操作等。性能考量链栈每次Push和Pop都涉及动态内存分配/释放这在频繁操作时可能成为性能瓶颈。如果栈的大小相对稳定且可预估顺序栈或共享栈通常是更好的选择因为数组访问具有更好的局部性速度更快。共享栈访问是O(1)但空间是静态分配的。如果无法准确预估两个栈的总容量可能会浪费空间分配过大或限制使用分配过小。通过本文从概念到代码从基础操作到问题排查和最佳实践的完整梳理相信你已经对链栈和共享栈有了透彻的理解。数据结构的学习关键在于动手建议你抛开本文自己从头实现一遍并尝试用栈去解决一些经典问题例如括号匹配、表达式求值、非递归的深度优先搜索等这样才能真正内化知识在未来的项目和面试中游刃有余。