这次我们来看链栈的实现。对于刚接触数据结构的朋友来说栈Stack是一个必须掌握的基础概念而链栈则是其基于链表的实现方式。相比顺序栈链栈的动态内存管理特性让它无需预先指定大小理论上可以“无限”增长受限于内存但也带来了指针操作的复杂性。这篇文章的重点不是空谈理论而是让你能立刻动手在代码里跑通链栈的核心操作。我们会从结构体定义开始一步步实现初始化、入栈、出栈、判空并扩展到“共享栈”这个经典面试题。整个过程会提供完整的C语言代码你可以直接复制到IDE里编译运行观察每一步内存和指针的变化。如果你正在准备数据结构考试、面试刷题或者想彻底理解链表和栈的结合这篇文章可以直接收藏。我们会用最直白的方式把指针怎么指、节点怎么连、内存怎么分配讲清楚。1. 核心能力速览在深入代码之前我们先快速了解链栈和共享栈的核心特性和区别。能力项链栈 (Linked Stack)共享栈 (Shared Stack)存储结构基于单链表每个节点包含数据和指向下一节点的指针。基于一个数组或两块连续内存两个栈共享同一存储空间。栈顶位置栈顶指针top指向链表头节点。两个栈顶指针分别指向数组两端top1和top2。初始化创建空栈top指针置为NULL。分配固定大小数组top1 -1top2 数组长度。入栈 (Push)动态申请新节点插入链表头部更新top。判断栈未满后向各自栈顶方向移动指针并存入元素。出栈 (Pop)判断栈非空后保存栈顶数据top移向下一个节点释放原栈顶节点。判断各自栈非空后取出栈顶元素指针向栈底方向移动。栈空判断top NULL。top1 -1(栈1空)top2 数组长度(栈2空)。栈满判断理论上内存耗尽时满实践中常不判断或判断malloc失败。top1 1 top2时表示两个栈顶相遇空间已满。内存管理动态分配与释放灵活但易产生内存碎片。静态或一次性分配内存连续无碎片问题。优势容量灵活无需预先定义大小。空间利用率高适用于对两个栈有固定总容量预期的场景。典型应用通用栈实现函数调用栈某些系统深度优先搜索DFS。双向问题处理如符号匹配、双端队列的简化实现等。2. 适用场景与使用边界链栈和共享栈各有其用武之地选择哪种取决于你的具体需求。链栈适合的场景栈容量不确定或变化较大时例如处理一个未知深度的递归调用、解析一个嵌套层级不确定的文档如JSON/XML。对内存使用灵活性要求高时不希望一开始就分配一大块可能用不完的内存。作为学习数据结构的练习深刻理解动态内存管理和指针操作。共享栈适合的场景两个栈的增长方向相反且总空间需求相对固定时这是最经典的适用场景。例如在一个程序中一个栈用于保存临时变量另一个栈用于保存返回地址两者此消彼长。需要高效利用一块连续内存时在内存受限的嵌入式系统或某些算法竞赛题中使用共享栈可以避免分配两块独立内存可能造成的浪费。面试与笔试共享栈是考查对栈本质和数组操作理解程度的经典题目。使用边界与注意事项链栈每次操作涉及动态内存分配(malloc)/释放(free)性能有开销。需严防内存泄漏出栈时必须free和野指针初始化、置空。共享栈容量固定一旦写满无法动态扩展。需要仔细设计栈空、栈满的判断条件逻辑上比单个栈稍复杂。通用建议在明确知道最大数据量且追求性能时可考虑顺序栈或共享栈。在需要灵活性时选择链栈。无论哪种都必须确保在出栈、销毁栈时做好资源释放。3. 环境准备与前置条件为了运行本文的示例代码你需要准备一个C语言开发环境。这非常简单。操作系统Windows, macOS 或 Linux 均可。本文代码是标准C跨平台。编译器需要安装C语言编译器。Windows: 推荐安装MinGW-w64或使用Visual Studio(选择“使用C的桌面开发”工作负载它包含C编译器)。macOS: 安装Xcode Command Line Tools(终端执行xcode-select --install)。Linux: 使用包管理器安装gcc例如 Ubuntu/Debian:sudo apt install gcc。代码编辑器或IDE任选一个你顺手的。轻量级VS Code, Sublime Text, Notepad。集成环境(IDE)Visual Studio, CLion, Code::Blocks, Dev-C。基础知识需要对C语言的指针、结构体、动态内存分配(malloc,free)有基本了解。如果对这些概念模糊建议先简单回顾。验证环境是否就绪打开终端或命令提示符输入gcc --version或clang --version如果能显示版本号说明编译器已安装成功。4. 链栈的完整实现与操作我们首先实现一个完整的链栈。链栈的节点就是单链表的节点栈顶指针top始终指向链表的第一个节点头节点。4.1 结构定义与初始化链栈的核心是节点结构体和栈顶指针。#include stdio.h #include stdlib.h #include stdbool.h // 使用bool类型 // 定义链栈的节点 typedef struct StackNode { int data; // 假设存储整型数据可根据需要修改类型 struct StackNode* next; } StackNode; // 定义链栈本质上就是一个指针 typedef struct { StackNode* top; // 栈顶指针 } LinkedStack; // 初始化链栈 void InitStack(LinkedStack* S) { S-top NULL; // 空栈的栈顶指针为NULL printf(链栈初始化成功。\n); }代码解释StackNode表示栈的每个元素包含数据域data和指向下一个节点的指针next。LinkedStack目前我们只用一个top指针来代表整个栈。有些教材会把这个指针直接作为栈但这里封装成结构体更清晰。InitStack初始化操作非常简单就是将top指针设置为NULL表示一个空链表空栈。4.2 判断栈空链栈的判空条件极其简单。// 判断链栈是否为空 bool IsEmpty(LinkedStack* S) { return S-top NULL; // 栈顶为NULL即为空 }4.3 入栈操作入栈就是在链表头部插入一个新节点。// 入栈操作 bool Push(LinkedStack* S, int value) { // 1. 创建新节点 StackNode* newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败入栈失败\n); return false; // 可视为栈满的一种情况内存耗尽 } // 2. 填充新节点数据 newNode-data value; // 3. 将新节点插入链表头部 newNode-next S-top; // 新节点指向原栈顶 S-top newNode; // 栈顶指针更新为新节点 printf(元素 %d 入栈成功。\n, value); return true; }操作步骤与指针变化malloc申请一块StackNode大小的内存。为新节点的data赋值。关键两步newNode-next S-top;让新节点指向原来的栈顶节点。S-top newNode;让栈顶指针指向这个新节点。这就完成了在头部的插入。4.4 出栈操作出栈就是删除链表头节点并返回其数据。// 出栈操作 bool Pop(LinkedStack* S, int* value) { // 1. 判断栈是否为空 if (IsEmpty(S)) { printf(栈为空无法出栈\n); return false; } // 2. 保存待删除节点及其数据 StackNode* tempNode S-top; // tempNode指向栈顶节点 *value tempNode-data; // 通过指针参数返回栈顶数据 // 3. 更新栈顶指针 S-top S-top-next; // 栈顶指针指向原栈顶的下一个节点 // 4. 释放原栈顶节点内存 free(tempNode); tempNode NULL; // 良好习惯防止野指针 printf(元素 %d 出栈成功。\n, *value); return true; }操作步骤与内存管理判空。用临时指针tempNode保存当前栈顶节点地址同时取出其数据。将栈顶指针S-top指向下一个节点S-top-next。这是链表删除头节点的标准操作。至关重要使用free(tempNode)释放被移出栈的节点所占用的内存。忘记这一步会导致内存泄漏。4.5 获取栈顶元素与出栈类似但不删除节点。// 获取栈顶元素不出栈 bool GetTop(LinkedStack* S, int* value) { if (IsEmpty(S)) { printf(栈为空无栈顶元素\n); return false; } *value S-top-data; return true; }4.6 销毁栈由于链栈节点是动态申请的使用完毕后应销毁整个栈释放所有内存。// 销毁链栈释放所有节点内存 void DestroyStack(LinkedStack* S) { int tempData; while (!IsEmpty(S)) { // 循环出栈直到栈空 Pop(S, tempData); // Pop函数内部会free节点 } printf(链栈已销毁所有内存已释放。\n); }原理循环调用Pop操作Pop内部会free节点直到栈为空。此时S-top已为NULL。4.7 链栈功能测试编写一个main函数来测试上述所有操作。int main() { LinkedStack S; int value; // 1. 初始化 InitStack(S); // 2. 入栈测试 Push(S, 10); Push(S, 20); Push(S, 30); // 3. 获取栈顶 if (GetTop(S, value)) { printf(当前栈顶元素是%d\n, value); } // 4. 出栈测试 printf(开始出栈\n); while (!IsEmpty(S)) { Pop(S, value); printf( 出栈元素%d\n, value); } // 5. 尝试对空栈出栈 Pop(S, value); // 6. 销毁栈此例中栈已空销毁操作是安全的 DestroyStack(S); return 0; }编译与运行 将以上所有代码块按顺序保存到一个文件例如linked_stack.c。 在终端中进入文件所在目录执行编译和运行命令gcc linked_stack.c -o linked_stack ./linked_stack # Linux/macOS # 或 linked_stack.exe # Windows预期输出链栈初始化成功。 元素 10 入栈成功。 元素 20 入栈成功。 元素 30 入栈成功。 当前栈顶元素是30 开始出栈 元素 30 出栈成功。 出栈元素30 元素 20 出栈成功。 出栈元素20 元素 10 出栈成功。 出栈元素10 栈为空无法出栈 链栈已销毁所有内存已释放。通过这个测试你可以清晰地看到“后进先出”(LIFO)的顺序最后入栈的30最先出栈。5. 共享栈的完整实现与操作共享栈利用一个数组来同时存储两个栈一个栈底在数组开头向尾部增长栈1另一个栈底在数组末尾向头部增长栈2。这种设计能更有效地利用存储空间。5.1 结构定义与初始化#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 // 共享栈的最大容量 typedef struct { int data[MAX_SIZE]; // 共享的存储数组 int top1; // 栈1的栈顶指针初始为-1 int top2; // 栈2的栈顶指针初始为MAX_SIZE } SharedStack; // 初始化共享栈 void InitSharedStack(SharedStack* S) { S-top1 -1; // 栈1为空 S-top2 MAX_SIZE; // 栈2为空 printf(共享栈初始化成功总容量为%d。\n, MAX_SIZE); }关键点top1是栈1的栈顶指针从-1开始向MAX_SIZE-1方向增长加1。top2是栈2的栈顶指针从MAX_SIZE开始向0方向增长减1。栈空和栈满的判断都基于这两个指针的位置关系。5.2 判断栈空与栈满// 判断栈1是否为空 bool IsEmpty1(SharedStack* S) { return S-top1 -1; } // 判断栈2是否为空 bool IsEmpty2(SharedStack* S) { return S-top2 MAX_SIZE; } // 判断共享栈是否已满 (栈1和栈2的栈顶相邻) bool IsFull(SharedStack* S) { return S-top1 1 S-top2; }栈满条件解析top1 1 top2是核心。top1指向栈1的最后一个元素top11是栈1下一个可插入的位置。top2指向栈2的最后一个元素top2本身也是栈2下一个可插入的位置。当这两个位置重合时意味着数组空间已完全占用。5.3 入栈操作需要指定向哪个栈入栈。// 向栈1入栈 bool Push1(SharedStack* S, int value) { if (IsFull(S)) { printf(共享栈已满无法向栈1入栈\n); return false; } S-data[(S-top1)] value; // top1先加1再赋值 printf(向栈1入栈元素%d (top1%d)\n, value, S-top1); return true; } // 向栈2入栈 bool Push2(SharedStack* S, int value) { if (IsFull(S)) { printf(共享栈已满无法向栈2入栈\n); return false; } S-data[--(S-top2)] value; // top2先减1再赋值 printf(向栈2入栈元素%d (top2%d)\n, value, S-top2); return true; }注意指针移动方向栈1(S-top1)向数组下标增大的方向移动。栈2--(S-top2)向数组下标减小的方向移动。5.4 出栈操作同样需要指定从哪个栈出栈。// 从栈1出栈 bool Pop1(SharedStack* S, int* value) { if (IsEmpty1(S)) { printf(栈1为空无法出栈\n); return false; } *value S-data[(S-top1)--]; // 先取值top1再减1 printf(从栈1出栈元素%d (top1%d)\n, *value, S-top1); return true; } // 从栈2出栈 bool Pop2(SharedStack* S, int* value) { if (IsEmpty2(S)) { printf(栈2为空无法出栈\n); return false; } *value S-data[(S-top2)]; // 先取值top2再加1 printf(从栈2出栈元素%d (top2%d)\n, *value, S-top2); return true; }注意指针移动方向栈1(S-top1)--向数组下标减小的方向移动回退。栈2(S-top2)向数组下标增大的方向移动回退。5.5 共享栈功能测试编写测试代码观察两个栈如何共享空间。int main() { SharedStack S; int value; // 1. 初始化 InitSharedStack(S); // 2. 向栈1压入数据 printf(\n 操作栈1 \n); for (int i 1; i 3; i) { Push1(S, i * 10); // 入栈 10, 20, 30 } // 3. 向栈2压入数据 printf(\n 操作栈2 \n); for (int i 1; i 3; i) { Push2(S, i * 100); // 入栈 100, 200, 300 } // 4. 查看栈满情况此时应未满 printf(\n当前栈是否满 %s\n, IsFull(S) ? 是 : 否); // 5. 继续压栈直到满假设MAX_SIZE100空间很大我们模拟压到满 printf(\n 模拟压栈至满 \n); // 为了演示我们假设数组很小快速压满。这里我们用循环模拟。 // 注意实际MAX_SIZE100以下循环仅为逻辑演示不会真执行100次。 // 我们改为手动模拟几次关键操作。 printf(假设继续向栈1入栈40...\n); Push1(S, 40); // top1 - 3 printf(假设继续向栈2入栈400...\n); Push2(S, 400); // top2 - 96 (因为MAX_SIZE100, 初始top2100, 入栈3次后top297, 再入栈400后top296) // ... 如此反复直到 top11 top2 // 6. 出栈测试 printf(\n 出栈测试 \n); Pop1(S, value); Pop2(S, value); // 7. 栈空测试 printf(\n 清空栈1 \n); while (!IsEmpty1(S)) { Pop1(S, value); } printf(栈1是否空 %s\n, IsEmpty1(S) ? 是 : 否); printf(\n 清空栈2 \n); while (!IsEmpty2(S)) { Pop2(S, value); } printf(栈2是否空 %s\n, IsEmpty2(S) ? 是 : 否); return 0; }运行与观察 将共享栈的代码保存为shared_stack.c编译运行。观察控制台输出特别注意top1和top2值的变化。你会看到它们从两端向中间靠拢。如果继续入栈直到top11 top2时IsFull函数将返回true此时无法再入栈。6. 两种栈的对比与性能观察虽然不涉及GPU显存但我们可以从内存和CPU操作角度分析性能。链栈的资源占用与性能内存占用每个元素需要额外空间存储next指针通常4或8字节有内存开销。频繁的malloc/free可能导致内存碎片。时间性能入栈和出栈操作都是O(1)常数时间复杂度但malloc和free是相对昂贵的系统调用其实际耗时比单纯的指针赋值高。观察方法对于学习而言可以在代码中打印节点地址(printf(“%p”, newNode))观察每次入栈时新节点的内存地址是否连续理解动态分配的“非连续”特性。共享栈的资源占用与性能内存占用内存是预先分配的连续数组无额外指针开销空间利用率高当两栈大小之和恒定且反向变化时。时间性能入栈和出栈是纯粹的数组赋值和指针移动速度极快没有系统调用开销。观察方法打印top1和top2的值以及它们之和。当(top1 1) (MAX_SIZE - top2) MAX_SIZE时表示所有空间都被使用。当top1 1 top2时空间用尽。简单性能测试思路 你可以写一个循环进行大量如10万次的入栈出栈操作使用time.h库的clock()函数分别测量链栈和共享栈完成操作的时间直观感受系统调用带来的开销差异。7. 常见问题与排查方法在实现链栈和共享栈时新手常会遇到以下几个问题问题现象可能原因排查方式解决方案程序编译错误未定义标识符bool、true、false未包含stdbool.h头文件。检查代码开头#include部分。添加#include stdbool.h。链栈程序运行崩溃段错误1. 未初始化栈top是野指针。2. 出栈时未判空对NULL指针解引用。3. 访问了已释放的节点野指针。1. 检查InitStack是否调用。2. 在Pop和GetTop开始处添加判空。3. 检查free后是否误操作指针。1. 确保初始化。2. 所有操作前先判空。3.free后可将指针置NULL。链栈内存泄漏只进行了Pop操作但未在Pop函数内free节点。或者只free了节点未将栈顶指针置NULL虽不影响逻辑但是好习惯。使用Valgrind等内存检测工具运行程序。确保Pop和DestroyStack中正确调用free。共享栈入栈时数据覆盖入栈前未检查栈是否已满(IsFull)。在Push1和Push2函数开始处添加if (IsFull(S))判断。添加栈满判断满时拒绝入栈或扩容共享栈通常固定大小。共享栈的栈空判断错误混淆了栈1和栈2的判空条件。栈1空是top1 -1栈2空是top2 MAX_SIZE。仔细核对IsEmpty1和IsEmpty2的逻辑。牢记初始化值栈1空-1栈2空MAX_SIZE。共享栈的栈满判断错误错误地认为top1 top2时满。实际上应该是top1 1 top2表示两个栈的下一个可用位置重合。画图理解。初始化时top1-1,top2MAX_SIZE。各插入一个元素后top10,top2MAX_SIZE-1此时top111不等于top2未满。使用正确的判断条件if (S-top1 1 S-top2)。“烫烫烫”等乱码在Windows VC环境下未初始化的栈数组可能填充0xCC调试模式打印时显示乱码。确保数组或变量在使用前已被正确初始化或赋值。调用初始化函数或手动设置初始值。通用调试建议画图对于指针操作在纸上画出节点和指针的变化是理解链表和栈操作最有效的方法。打印调试在关键步骤如malloc后、free后、指针修改前后打印指针地址(%p)和关键变量值。分步测试不要写完所有代码再测试。写完初始化、入栈、打印就先测试。确保一步走稳了再实现下一步。使用调试器学习使用GDBLinux/macOS或Visual Studio DebuggerWindows进行单步调试观察变量值的变化。8. 最佳实践与使用建议掌握了基础实现后以下建议能帮助你写出更健壮、更通用的代码提高代码通用性使用typedef和宏// 将数据类型抽象出来方便修改 typedef int ElementType; // 在结构体和函数中使用ElementType typedef struct StackNode { ElementType data; struct StackNode* next; } StackNode;这样如果想将栈存储的数据类型从int改为char或float只需修改一处。将栈操作封装成接口头文件 创建linked_stack.h声明所有函数在linked_stack.c中实现。main.c包含头文件来使用。这是工程化编程的基础。为链栈添加“栈满”判断 虽然链栈理论上不满但malloc可能失败。可以将Push函数中的malloc失败视为“栈满”这是一种防御性编程。bool isStackFull(LinkedStack* S) { // 尝试分配一个临时节点来探测内存是否充足这是一种简单模拟并非绝对准确 StackNode* temp (StackNode*)malloc(sizeof(StackNode)); bool full (temp NULL); free(temp); // 立即释放 return full; } // 在Push中可以先调用isStackFull或者直接检查malloc返回值。共享栈的动态扩容 经典的共享栈是静态数组。你可以尝试挑战更复杂的版本当栈满时重新分配一个更大的数组将原有数据复制过去并更新top1和top2。这涉及到内存的重新分配(realloc)和数据的迁移。错误处理标准化 定义统一的错误码或使用枚举让函数返回值更有意义而不是简单的true/false。编写销毁函数 对于链栈必须有DestroyStack来避免内存泄漏。对于共享栈如果数组是动态分配的(malloc)也需要对应的销毁函数来free。测试用例覆盖边界测试对空栈出栈、对满栈入栈。交叉操作测试对共享栈交替向栈1和栈2入栈出栈。压力测试进行大量操作检查内存和性能。链栈和共享栈是理解数据结构“逻辑结构”与“物理存储”关系的绝佳例子。链栈体现了链式存储的灵活性共享栈体现了顺序存储的高效与空间利用智慧。把本文的代码自己敲一遍调试通过再尝试修改、扩展你就能牢牢掌握这两种重要的栈实现方式。下次面试官问你栈的实现你就能从顺序栈、链栈一直讲到共享栈清晰地道出它们的优劣与适用场景。