尧图网站建设 
如果你正在学习数据结构特别是栈的实现可能会遇到一个关键选择用数组实现顺序栈还是用链表实现链栈很多教材和教程会告诉你顺序栈简单直观链栈动态灵活。但当你真正动手写代码时链栈的“灵活”背后隐藏着比顺序栈更多的细节和陷阱。为什么明明理解了栈的“后进先出”原理写链栈时还是会卡在指针操作上为什么初始化一个看似简单的链栈却要考虑头指针和栈顶指针的关系为什么共享栈听起来高级但实现时却容易混淆两个栈的指针操作这些问题恰恰是数据结构从理论到实践的关键门槛。本文将从零开始手把手带你实现链栈和共享栈。我们不只讲“是什么”更要讲清楚“为什么”和“怎么做”。你将看到完整的C语言代码理解每一步指针操作的意图并学会如何判断栈空、栈满对于链栈栈满的判断有其特殊性以及如何处理共享栈中两个栈的“相遇”问题。更重要的是我们会对比链栈和顺序栈的适用场景让你知道在什么情况下应该选择链栈避免盲目使用。读完本文你将能独立完成链栈的初始化、入栈、出栈、判空等核心操作并能理解共享栈的设计思想与实现。无论是应对课程实验、期末考试还是为后续学习更复杂的链表结构打下坚实基础这篇文章都将是一份实用的指南。1. 链栈 vs 顺序栈为什么需要链栈在开始写代码之前我们必须先回答一个根本问题既然数组实现的顺序栈已经足够好用为什么还要引入更复杂的链栈顺序栈的局限性在于“静态”。它依赖于一块预先分配的连续内存空间。这意味着空间固定创建栈时就必须指定最大容量。如果估计不足会发生“上溢”栈满如果估计过大又会浪费内存。扩容成本高虽然可以通过重新分配更大数组来实现动态扩容但这个过程涉及数据迁移时间复杂度为O(n)在需要高频入栈出栈的场景下性能影响显著。链栈的核心优势在于“动态”。它使用链表节点来存储数据每个节点在需要时才被创建。理论上的无限容量只要系统内存足够就可以一直入栈不考虑物理限制。这解决了顺序栈需要预估容量的问题。无需连续内存节点通过指针链接可以分散在内存的任何位置对内存碎片更友好。入栈出栈的原子性链栈的入栈和出栈操作本质上只是链表头部的插入和删除时间复杂度始终是O(1)且不涉及数据的批量移动。但是链栈的“动态”是有代价的额外的存储开销每个数据节点除了存储数据本身还需要至少一个指针在单链表实现中来指向下一个节点。存储密度低于顺序栈。访问的局部性差节点内存地址不连续CPU缓存命中率可能低于顺序栈在极端性能敏感场景下可能有细微差别。代码复杂度稍高需要手动管理节点的内存申请与释放对指针操作的理解要求更深。那么如何选择选择顺序栈当栈的最大容量可以提前确定且对性能有较高要求时。例如函数调用栈、表达式求值等。选择链栈当栈的大小变化范围很大无法预估上限或者内存碎片化需要避免时。它也常用于作为其他复杂链式结构如链式队列的组成部分来学习。理解了“为什么”我们才能更好地掌握“怎么做”。接下来我们从链栈最基础的结构定义开始。2. 链栈的核心结构定义与状态判断链栈通常采用单链表来实现并且将链表的头节点作为栈顶。这样设计的好处是入栈和出栈操作都只在链表头部进行时间复杂度为O(1)。如果栈顶在链表尾部入栈操作就需要遍历整个链表效率低下。2.1 链栈的节点与栈结构定义首先我们定义链栈的节点。每个节点需要包含两部分数据域和指针域。// 链栈节点定义 typedef struct StackNode { int data; // 数据域这里以int类型为例 struct StackNode *next; // 指针域指向下一个节点 } StackNode;接下来定义链栈本身。我们只需要一个指针来指向栈顶节点即可。这个指针通常被命名为top。// 链栈结构定义 typedef struct LinkStack { StackNode *top; // 栈顶指针 int count; // 栈中元素个数可选方便判断 } LinkStack;这里引入了一个count成员来记录栈中当前元素的数量。这是一个非常实用的设计它使得判断栈空和获取栈长度的时间复杂度降为O(1)。如果不维护count判断栈空只需要看top是否为NULL但获取栈长度就需要遍历整个链表时间复杂度为O(n)。2.2 链栈的“栈满”状态这是一个初学者容易困惑的点。对于顺序栈栈满意味着数组空间已耗尽。但对于链栈呢从理论上讲只要操作系统还能分配内存链栈就可以一直创建新节点因此链栈通常被认为是不会“栈满”的。这也是链栈相比顺序栈的一大优势。然而在编程实践中当我们调用malloc申请新节点内存时如果系统内存不足malloc会返回NULL。这种情况下我们可以认为链栈“栈满”了。因此链栈的“栈满”判断实际上是对内存申请成功与否的判断。2.3 链栈的“栈空”状态链栈的栈空判断非常简单栈顶指针top是否为NULL。如果top NULL则表示链栈为空没有任何元素。// 判断链栈是否为空 int IsEmptyLinkStack(LinkStack *S) { // 如果栈顶指针为空或者元素个数为0则栈为空 return (S-top NULL) || (S-count 0); }有了这些基础概念我们就可以开始实现链栈的各项操作了。初始化是第一步也是确保后续操作正确性的关键。3. 链栈的初始化从无到有的正确起点初始化一个链栈本质上是创建一个“空栈”。空栈意味着栈顶指针不指向任何有效的节点。3.1 初始化步骤与代码实现正确的初始化流程如下为链栈结构体LinkStack动态申请内存。将栈顶指针top设置为NULL表示栈为空。将元素计数器count设置为 0。// 链栈的初始化 LinkStack* InitLinkStack() { // 1. 为链栈结构体申请内存 LinkStack *S (LinkStack*)malloc(sizeof(LinkStack)); if (S NULL) { printf(内存分配失败\n); return NULL; } // 2. 初始化栈顶指针和元素个数 S-top NULL; // 空栈栈顶指针置空 S-count 0; // 元素个数为0 printf(链栈初始化成功。\n); return S; // 返回初始化好的栈指针 }关键点解析为什么使用动态内存分配这使得栈的生命周期可以灵活控制可以在函数中创建并返回给调用者符合通用库函数的设计。错误处理对malloc的返回值进行了检查这是良好的编程习惯防止后续操作空指针导致程序崩溃。top初始化为NULL这是判断栈空的唯一依据至关重要。一个常见的错误是忘记将top初始化为NULL如果它是一个野指针后续判断栈空或进行指针操作将导致未定义行为。初始化完成后我们得到一个可以使用的空链栈。接下来最核心的两个操作入栈和出栈。4. 链栈的核心操作入栈与出栈详解入栈Push和出栈Pop是栈结构的灵魂。在链栈中这两个操作对应着链表头部的插入和删除。4.1 入栈Push操作入栈操作的步骤可以类比为“在链表头部插入一个新节点”创建新节点为新的栈元素动态申请一个节点内存。填充数据将数据存入新节点的数据域。连接新节点将新节点的next指针指向当前栈顶节点即原链表头。更新栈顶将链栈的top指针指向这个新节点。更新计数栈中元素个数count加1。// 链栈的入栈操作 int PushLinkStack(LinkStack *S, int e) { // 1. 参数检查 if (S NULL) { printf(栈指针无效\n); return 0; // 操作失败 } // 2. 创建新节点 (此处隐含了“栈满”判断内存是否申请成功) StackNode *newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败入栈操作终止。\n); return 0; // 操作失败链栈“栈满” } // 3. 填充新节点数据 newNode-data e; // 4. 将新节点插入链表头部 newNode-next S-top; // 新节点指向原栈顶 // 5. 更新栈顶指针 S-top newNode; // 6. 更新元素计数 S-count; printf(元素 %d 入栈成功。当前栈大小%d\n, e, S-count); return 1; // 操作成功 }关键点解析“栈满”判断体现在malloc申请节点内存是否成功。失败则返回0。插入顺序必须先让newNode-next S-top再更新S-top newNode。顺序反了会导致链表断裂。时间复杂度O(1)。无论栈中有多少元素入栈操作只涉及常数次指针赋值和内存申请。4.2 出栈Pop操作出栈操作是入栈的逆过程对应“删除链表头节点”检查栈空如果栈为空则无法出栈。备份栈顶用一个临时指针p指向当前栈顶节点以便后续释放内存和返回数据。更新栈顶将栈顶指针top指向原栈顶节点的下一个节点S-top S-top-next。取出数据从临时指针p指向的节点中取出数据保存到输出参数中。释放内存释放临时指针p所指向的节点内存防止内存泄漏。更新计数栈中元素个数count减1。// 链栈的出栈操作 int PopLinkStack(LinkStack *S, int *e) { // 1. 参数检查 if (S NULL || e NULL) { printf(参数无效\n); return 0; } // 2. 检查栈空 if (IsEmptyLinkStack(S)) { printf(栈为空无法执行出栈操作。\n); return 0; } // 3. 备份栈顶节点指针 StackNode *p S-top; // 4. 取出栈顶数据 *e p-data; // 5. 更新栈顶指针 S-top p-next; // 6. 释放原栈顶节点内存 free(p); // 7. 更新元素计数 S-count--; printf(元素 %d 出栈成功。当前栈大小%d\n, *e, S-count); return 1; // 操作成功 }关键点解析栈空检查这是出栈操作的第一道安全门必不可少。内存管理free(p)是链式结构区别于顺序栈的关键。顺序栈出栈只需移动指针链栈必须手动释放内存否则会造成内存泄漏。数据返回通过指针参数e返回被删除的元素值这是获取出栈元素的常用方式。更新栈顶S-top p-next;这行代码即使p-next为NULL即出栈后栈变空也是正确的此时S-top被置为NULL符合空栈定义。时间复杂度O(1)。4.3 获取栈顶元素Peek这是一个只读操作不改变栈的状态。它对于检查栈顶内容非常有用。// 获取栈顶元素不删除 int GetTopLinkStack(LinkStack *S, int *e) { if (S NULL || e NULL) { return 0; } if (IsEmptyLinkStack(S)) { printf(栈为空无栈顶元素。\n); return 0; } *e S-top-data; // 直接读取栈顶节点的数据 return 1; }至此链栈的基本操作已经齐备。我们可以编写一个完整的测试程序来验证它们。5. 链栈的完整测试程序与运行结果理论需要实践来验证。下面是一个完整的C程序它演示了链栈从初始化、入栈、出栈到销毁的完整生命周期。#include stdio.h #include stdlib.h // 此处插入之前定义的 StackNode, LinkStack, // 以及 InitLinkStack, PushLinkStack, PopLinkStack, // GetTopLinkStack, IsEmptyLinkStack 等所有函数定义 // 打印链栈中的所有元素从栈顶到栈底 void PrintLinkStack(LinkStack *S) { if (S NULL || IsEmptyLinkStack(S)) { printf(栈为空或无效。\n); return; } printf(当前栈内容栈顶-栈底: ); StackNode *p S-top; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 销毁链栈释放所有内存 void DestroyLinkStack(LinkStack *S) { if (S NULL) { return; } int temp; // 循环出栈直到栈空释放所有节点内存 while (!IsEmptyLinkStack(S)) { PopLinkStack(S, temp); // Pop操作内部会free节点 } // 最后释放栈结构体本身 free(S); printf(链栈已销毁所有内存已释放。\n); } int main() { printf( 链栈操作测试 \n); // 1. 初始化链栈 LinkStack *myStack InitLinkStack(); if (myStack NULL) { return -1; // 初始化失败退出 } // 2. 测试入栈操作 printf(\n--- 测试入栈 ---\n); for (int i 1; i 5; i) { PushLinkStack(myStack, i * 10); // 入栈 10, 20, 30, 40, 50 } PrintLinkStack(myStack); // 3. 测试获取栈顶元素 printf(\n--- 测试获取栈顶 ---\n); int topElem; if (GetTopLinkStack(myStack, topElem)) { printf(栈顶元素是%d\n, topElem); } PrintLinkStack(myStack); // 栈应无变化 // 4. 测试出栈操作 printf(\n--- 测试出栈 ---\n); int poppedElem; if (PopLinkStack(myStack, poppedElem)) { printf(出栈元素%d\n, poppedElem); } PrintLinkStack(myStack); // 5. 测试栈空判断 printf(\n--- 测试栈空判断 ---\n); printf(栈是否为空 %s\n, IsEmptyLinkStack(myStack) ? 是 : 否); // 6. 连续出栈直到栈空 printf(\n--- 连续出栈直到栈空 ---\n); while (!IsEmptyLinkStack(myStack)) { PopLinkStack(myStack, poppedElem); printf(出栈%d, , poppedElem); } printf(\n); printf(栈是否为空 %s\n, IsEmptyLinkStack(myStack) ? 是 : 否); // 7. 再次尝试出栈应失败 printf(\n--- 尝试对空栈出栈 ---\n); if (!PopLinkStack(myStack, poppedElem)) { printf(预期中的出栈失败栈已空。\n); } // 8. 销毁链栈 printf(\n--- 销毁链栈 ---\n); DestroyLinkStack(myStack); myStack NULL; // 避免悬空指针 printf(\n 测试结束 \n); return 0; }预期运行结果 链栈操作测试 链栈初始化成功。 --- 测试入栈 --- 元素 10 入栈成功。当前栈大小1 元素 20 入栈成功。当前栈大小2 元素 30 入栈成功。当前栈大小3 元素 40 入栈成功。当前栈大小4 元素 50 入栈成功。当前栈大小5 当前栈内容栈顶-栈底: 50 40 30 20 10 --- 测试获取栈顶 --- 栈顶元素是50 当前栈内容栈顶-栈底: 50 40 30 20 10 --- 测试出栈 --- 元素 50 出栈成功。当前栈大小4 出栈元素50 当前栈内容栈顶-栈底: 40 30 20 10 --- 测试栈空判断 --- 栈是否为空 否 --- 连续出栈直到栈空 --- 元素 40 出栈成功。当前栈大小3 出栈40, 元素 30 出栈成功。当前栈大小2 出栈30, 元素 20 出栈成功。当前栈大小1 出栈20, 元素 10 出栈成功。当前栈大小0 出栈10, 栈是否为空 是 --- 尝试对空栈出栈 --- 栈为空无法执行出栈操作。 预期中的出栈失败栈已空。 --- 销毁链栈 --- 栈为空无法执行出栈操作。 链栈已销毁所有内存已释放。 测试结束 通过这个测试你可以清晰地看到链栈“后进先出”的特性50最后入栈最先出栈以及所有基本操作的正确性。接下来我们探讨一个更高级的话题共享栈。6. 共享栈一种高效利用连续内存的设计共享栈是两个栈共享同一块连续内存空间的数据结构。通常一个栈的栈底在数组的起始位置另一个栈的栈底在数组的末尾两个栈的栈顶向中间增长。这种设计在内存使用上非常高效尤其适用于两个栈的空间需求存在此消彼长关系的场景。共享栈解决了什么问题假设你需要同时使用两个栈但无法准确预测各自需要多少空间。如果为每个栈单独分配一个固定大小的数组可能会出现一个栈已满而另一个栈还很空的情况造成内存浪费。共享栈将两个栈放在一个数组里让它们动态地共享整个空间提高了内存利用率。6.1 共享栈的结构定义与初始化我们使用一个数组和两个栈顶指针来实现共享栈。// 共享栈的最大容量 #define SHARED_STACK_MAX_SIZE 100 // 共享栈结构定义 typedef struct SharedStack { int data[SHARED_STACK_MAX_SIZE]; // 共享的存储数组 int top1; // 栈1的栈顶指针初始为-1 int top2; // 栈2的栈顶指针初始为SHARED_STACK_MAX_SIZE } SharedStack;关键设计top1指向栈1的栈顶元素。栈1从数组头部下标0开始增长。初始时栈空top1 -1。top2指向栈2的栈顶元素。栈2从数组尾部下标MAX_SIZE-1开始向头部增长。初始时栈空top2 MAX_SIZE。栈满条件两个栈的栈顶指针相遇即top1 1 top2。这意味着数组空间已被完全占用。初始化函数如下// 共享栈的初始化 void InitSharedStack(SharedStack *S) { if (S NULL) return; S-top1 -1; // 栈1为空 S-top2 SHARED_STACK_MAX_SIZE; // 栈2为空 printf(共享栈初始化成功。栈1顶指针%d, 栈2顶指针%d\n, S-top1, S-top2); }7. 共享栈的核心操作双栈的入栈与出栈共享栈的操作需要指定是对哪个栈进行操作栈1或栈2。我们用一个参数stackNumber(通常取1或2) 来区分。7.1 共享栈的入栈Push操作入栈前必须判断栈是否已满。// 共享栈的入栈操作 int PushSharedStack(SharedStack *S, int stackNumber, int e) { if (S NULL) { printf(栈指针无效\n); return 0; } // 1. 判断栈满 if (S-top1 1 S-top2) { printf(共享栈已满无法入栈。\n); return 0; } // 2. 根据栈编号执行入栈 if (stackNumber 1) { // 栈1栈顶指针先加1再存入数据 S-top1; S-data[S-top1] e; printf(元素 %d 入栈1成功。栈1顶指针%d\n, e, S-top1); } else if (stackNumber 2) { // 栈2栈顶指针先减1再存入数据 S-top2--; S-data[S-top2] e; printf(元素 %d 入栈2成功。栈2顶指针%d\n, e, S-top2); } else { printf(栈编号错误请输入1或2。\n); return 0; } return 1; }关键点解析栈满判断if (S-top1 1 S-top2)。这是共享栈的核心逻辑表示两个栈的栈顶即将相遇没有空闲单元。指针移动方向栈1的top1向数组尾部增长栈2的top2向数组头部增长--。操作隔离两个栈的操作完全独立只是共享存储空间。7.2 共享栈的出栈Pop操作出栈前必须判断目标栈是否为空。// 共享栈的出栈操作 int PopSharedStack(SharedStack *S, int stackNumber, int *e) { if (S NULL || e NULL) { printf(参数无效\n); return 0; } if (stackNumber 1) { // 1. 判断栈1是否为空 if (S-top1 -1) { printf(栈1为空无法出栈。\n); return 0; } // 2. 取出栈顶数据 *e S-data[S-top1]; // 3. 栈顶指针减1 S-top1--; printf(元素 %d 从栈1出栈成功。栈1顶指针%d\n, *e, S-top1); } else if (stackNumber 2) { // 1. 判断栈2是否为空 if (S-top2 SHARED_STACK_MAX_SIZE) { printf(栈2为空无法出栈。\n); return 0; } // 2. 取出栈顶数据 *e S-data[S-top2]; // 3. 栈顶指针加1 S-top2; printf(元素 %d 从栈2出栈成功。栈2顶指针%d\n, *e, S-top2); } else { printf(栈编号错误请输入1或2。\n); return 0; } return 1; }关键点解析栈空判断栈1空的条件是top1 -1栈2空的条件是top2 MAX_SIZE。指针移动出栈后栈1的top1减1栈2的top2加1释放该存储单元。与链栈的区别共享栈的出栈不需要释放内存只是移动指针因为内存是预先分配的数组。7.3 共享栈的判空与栈满函数// 判断共享栈中的某个栈是否为空 int IsEmptySharedStack(SharedStack *S, int stackNumber) { if (S NULL) return 1; if (stackNumber 1) { return (S-top1 -1); } else if (stackNumber 2) { return (S-top2 SHARED_STACK_MAX_SIZE); } return 1; // 参数错误视为空 } // 判断共享栈是否已满 int IsFullSharedStack(SharedStack *S) { if (S NULL) return 0; return (S-top1 1 S-top2); }8. 共享栈的完整测试程序下面是一个测试共享栈所有功能的完整程序。#include stdio.h #include stdlib.h #define SHARED_STACK_MAX_SIZE 10 // 为了便于观察这里使用小容量 // 此处插入之前定义的 SharedStack 结构体 // 以及 InitSharedStack, PushSharedStack, PopSharedStack, // IsEmptySharedStack, IsFullSharedStack 等函数定义 // 打印共享栈的整个数组状态便于观察 void PrintSharedStack(SharedStack *S) { if (S NULL) return; printf(\n共享栈数组状态 [0~%d]:\n, SHARED_STACK_MAX_SIZE - 1); printf(索引: ); for (int i 0; i SHARED_STACK_MAX_SIZE; i) { printf(%3d , i); } printf(\n数据: ); for (int i 0; i SHARED_STACK_MAX_SIZE; i) { // 标记栈1和栈2的当前范围 if (i S-top1) { printf( S1 ); // 栈1区域 } else if (i S-top2) { printf( S2 ); // 栈2区域 } else { printf( -- ); // 空闲区域 } } printf(\n); printf(栈1顶指针 top1 %d, 栈2顶指针 top2 %d\n, S-top1, S-top2); printf(栈1是否空: %s, 栈2是否空: %s, 共享栈是否满: %s\n, IsEmptySharedStack(S, 1) ? 是 : 否, IsEmptySharedStack(S, 2) ? 是 : 否, IsFullSharedStack(S) ? 是 : 否); } int main() { printf( 共享栈操作测试 (最大容量: %d) \n, SHARED_STACK_MAX_SIZE); SharedStack S; InitSharedStack(S); PrintSharedStack(S); int elem; printf(\n--- 测试向栈1入栈3个元素 ---\n); for (int i 1; i 3; i) { PushSharedStack(S, 1, i * 100); // 入栈 100, 200, 300 } PrintSharedStack(S); printf(\n--- 测试向栈2入栈4个元素 ---\n); for (int i 1; i 4; i) { PushSharedStack(S, 2, i * 10); // 入栈 10, 20, 30, 40 } PrintSharedStack(S); printf(\n--- 测试从栈1出栈1个元素 ---\n); PopSharedStack(S, 1, elem); printf(出栈元素: %d\n, elem); PrintSharedStack(S); printf(\n--- 测试填满共享栈 ---\n); // 此时已用空间栈1有2个(100,200)栈2有4个(10,20,30,40)共6个。 // 剩余空间10 - 6 4个。 printf(尝试向栈1再入栈4个元素 (500,600,700,800)...\n); for (int i 5; i 8; i) { if (!PushSharedStack(S, 1, i * 100)) { break; // 如果栈满停止 } } PrintSharedStack(S); printf(\n--- 测试栈满后尝试入栈 ---\n); if (!PushSharedStack(S, 2, 99)) { printf(预期中的入栈失败共享栈已满。\n); } printf(\n--- 测试清空栈2 ---\n); while (!IsEmptySharedStack(S, 2)) { PopSharedStack(S, 2, elem); printf(从栈2出栈: %d, , elem); } printf(\n); PrintSharedStack(S); printf(\n--- 测试栈2空后尝试出栈 ---\n); if (!PopSharedStack(S, 2, elem)) { printf(预期中的出栈失败栈2已空。\n); } printf(\n 测试结束 \n); return 0; }预期运行结果片段 共享栈操作测试 (最大容量: 10) 共享栈初始化成功。栈1顶指针-1, 栈2顶指针10 共享栈数组状态 [0~9]: 索引: 0 1 2 3 4 5 6 7 8 9 数据: -- -- -- -- -- -- -- -- -- -- 栈1顶指针 top1 -1, 栈2顶指针 top2 10 栈1是否空: 是, 栈2是否空: 是, 共享栈是否满: 否 --- 测试向栈1入栈3个元素 --- 元素 100 入栈1成功。栈1顶指针0 ... 共享栈数组状态 [0~9]: 索引: 0 1 2 3 4 5 6 7 8 9 数据: S1 S1 S1 -- -- -- -- -- -- -- 栈1顶指针 top1 2, 栈2顶指针 top2 10 ... --- 测试填满共享栈 --- 尝试向栈1再入栈4个元素 (500,600,700,800)... 元素 500 入栈1成功。栈1顶指针3 ... 元素 800 入栈1成功。栈1顶指针6 共享栈数组状态 [0~9]: 索引: 0 1 2 3 4 5 6 7 8 9 数据: S1 S1 S1 S1 S1 S1 S1 S2 S2 S2 栈1顶指针 top1 6, 栈2顶指针 top2 7 栈1是否空: 否, 栈2是否空: 否, 共享栈是否满: 是通过这个测试你可以直观地看到两个栈的栈顶指针如何从两端向中间移动并最终相遇top16,top27满足top11 top2标志着共享栈已满。9. 常见问题与排查思路在实际实现链栈和共享栈时你可能会遇到以下问题问题现象可能原因排查方式解决方案链栈入栈失败程序崩溃1. 未检查malloc返回值。2. 栈指针S未初始化或为NULL。1. 检查入栈函数开头对S的判空。2. 检查malloc后是否判断了newNode NULL。1. 确保栈已正确初始化。2. 在malloc后添加内存分配失败的判断和处理。链栈出栈后访问数据出错1. 出栈时未先检查栈空。2. 出栈后使用了已释放节点的数据指针。1. 在Pop函数开始检查IsEmpty。2. 确保在free(p)之前已将数据保存或返回。1. 严格遵守“先判空再操作”的原则。2. 数据保存到临时变量或输出参数后再释放节点。链栈内存泄漏只进行了Pop操作但未在销毁栈时释放所有节点。检查销毁函数是否循环Pop直到栈空或遍历链表逐个free。实现DestroyLinkStack函数确保释放所有节点内存和栈结构体内存。共享栈判断栈满逻辑错误栈满条件写错例如写成top1 top2。画图分析当两个栈顶指针相邻时即top11 top2时栈满。top1 top2意味着已经重叠可能已发生数据覆盖。将栈满条件修正为if (S-top1 1 S-top2)。共享栈入栈到错误的栈混淆了栈1和栈2的指针移动方向。画图记忆栈1 (top1) 从-1开始向数组尾部增长 ()。栈2 (top2) 从MAX_SIZE开始向数组头部增长 (--)。为栈1和栈2分别编写独立的入栈出栈代码块并添加清晰的注释。打印链栈时顺序错误遍历链表时从栈顶到栈底的顺序理解反了。链栈的栈顶是链表头。打印时从头节点 (S-top) 开始通过next指针遍历到NULL顺序就是“栈顶-栈底”。确认遍历起点是S-top循环条件是p ! NULL步进是p p-next。10. 最佳实践与工程建议掌握了基本操作后将这些知识应用到实际项目或进一步学习时请记住以下建议封装与模块化将栈的结构定义和所有操作函数放在独立的头文件.h和源文件.c中。这提高了代码的复用性和可维护性。例如创建link_stack.h和link_stack.c。增强健壮性参数校验所有公开的函数入口都应进行参数有效性检查如指针非空。错误码定义定义一套清晰的错误码枚举类型让函数调用者能准确知道失败原因如STACK_EMPTY,STACK_FULL,MEMORY_ALLOC_FAIL等而不是简单地返回0/1。资源管理对于链栈确保malloc和free成对出现。考虑在初始化失败或操作中途失败时进行已分配资源的清理。考虑泛型编程本文示例使用int类型数据。在实际库中可以考虑使用void*指针来存储任意类型的数据或者利用C的模板、Java的泛型来实现通用栈。性能与权衡链栈优势在于动态扩容但每个节点有额外指针开销且内存分配/释放频繁可能影响性能。在需要频繁变长且对内存使用不苛刻的场景下使用。顺序栈/共享栈优势在于内存连续访问效率高无内存碎片但容量固定。在容量可预估、追求性能的场景下使用。共享栈是顺序栈的变体在需要两个栈且总空间固定的场景下内存利用率最高。测试驱动像本文一样为你的栈实现编写全面的测试用例覆盖正常操作、边界条件空栈、满栈和错误情况无效参数。这能极大减少隐藏的Bug。链栈和共享栈是理解栈这种数据结构及其不同实现方式的绝佳范例。链栈教你如何用动态内存管理来构建灵活的数据结构而共享栈则展示了如何通过巧妙的指针设计来高效利用静态内存。理解它们不仅是为了通过考试更是为了培养解决实际内存管理问题的思维能力。当你下次需要实现一个缓冲区、管理一个任务列表或者设计一个需要双向增长的数据区域时这次学习的经验就会派上用场。建议你将本文的代码亲手敲一遍并尝试修改测试用例观察不同的行为这是巩固理解的最佳途径。 从零实现链栈与共享栈：C语言详解与工程实践
如果你正在学习数据结构特别是栈的实现可能会遇到一个关键选择用数组实现顺序栈还是用链表实现链栈很多教材和教程会告诉你顺序栈简单直观链栈动态灵活。但当你真正动手写代码时链栈的“灵活”背后隐藏着比顺序栈更多的细节和陷阱。为什么明明理解了栈的“后进先出”原理写链栈时还是会卡在指针操作上为什么初始化一个看似简单的链栈却要考虑头指针和栈顶指针的关系为什么共享栈听起来高级但实现时却容易混淆两个栈的指针操作这些问题恰恰是数据结构从理论到实践的关键门槛。本文将从零开始手把手带你实现链栈和共享栈。我们不只讲“是什么”更要讲清楚“为什么”和“怎么做”。你将看到完整的C语言代码理解每一步指针操作的意图并学会如何判断栈空、栈满对于链栈栈满的判断有其特殊性以及如何处理共享栈中两个栈的“相遇”问题。更重要的是我们会对比链栈和顺序栈的适用场景让你知道在什么情况下应该选择链栈避免盲目使用。读完本文你将能独立完成链栈的初始化、入栈、出栈、判空等核心操作并能理解共享栈的设计思想与实现。无论是应对课程实验、期末考试还是为后续学习更复杂的链表结构打下坚实基础这篇文章都将是一份实用的指南。1. 链栈 vs 顺序栈为什么需要链栈在开始写代码之前我们必须先回答一个根本问题既然数组实现的顺序栈已经足够好用为什么还要引入更复杂的链栈顺序栈的局限性在于“静态”。它依赖于一块预先分配的连续内存空间。这意味着空间固定创建栈时就必须指定最大容量。如果估计不足会发生“上溢”栈满如果估计过大又会浪费内存。扩容成本高虽然可以通过重新分配更大数组来实现动态扩容但这个过程涉及数据迁移时间复杂度为O(n)在需要高频入栈出栈的场景下性能影响显著。链栈的核心优势在于“动态”。它使用链表节点来存储数据每个节点在需要时才被创建。理论上的无限容量只要系统内存足够就可以一直入栈不考虑物理限制。这解决了顺序栈需要预估容量的问题。无需连续内存节点通过指针链接可以分散在内存的任何位置对内存碎片更友好。入栈出栈的原子性链栈的入栈和出栈操作本质上只是链表头部的插入和删除时间复杂度始终是O(1)且不涉及数据的批量移动。但是链栈的“动态”是有代价的额外的存储开销每个数据节点除了存储数据本身还需要至少一个指针在单链表实现中来指向下一个节点。存储密度低于顺序栈。访问的局部性差节点内存地址不连续CPU缓存命中率可能低于顺序栈在极端性能敏感场景下可能有细微差别。代码复杂度稍高需要手动管理节点的内存申请与释放对指针操作的理解要求更深。那么如何选择选择顺序栈当栈的最大容量可以提前确定且对性能有较高要求时。例如函数调用栈、表达式求值等。选择链栈当栈的大小变化范围很大无法预估上限或者内存碎片化需要避免时。它也常用于作为其他复杂链式结构如链式队列的组成部分来学习。理解了“为什么”我们才能更好地掌握“怎么做”。接下来我们从链栈最基础的结构定义开始。2. 链栈的核心结构定义与状态判断链栈通常采用单链表来实现并且将链表的头节点作为栈顶。这样设计的好处是入栈和出栈操作都只在链表头部进行时间复杂度为O(1)。如果栈顶在链表尾部入栈操作就需要遍历整个链表效率低下。2.1 链栈的节点与栈结构定义首先我们定义链栈的节点。每个节点需要包含两部分数据域和指针域。// 链栈节点定义 typedef struct StackNode { int data; // 数据域这里以int类型为例 struct StackNode *next; // 指针域指向下一个节点 } StackNode;接下来定义链栈本身。我们只需要一个指针来指向栈顶节点即可。这个指针通常被命名为top。// 链栈结构定义 typedef struct LinkStack { StackNode *top; // 栈顶指针 int count; // 栈中元素个数可选方便判断 } LinkStack;这里引入了一个count成员来记录栈中当前元素的数量。这是一个非常实用的设计它使得判断栈空和获取栈长度的时间复杂度降为O(1)。如果不维护count判断栈空只需要看top是否为NULL但获取栈长度就需要遍历整个链表时间复杂度为O(n)。2.2 链栈的“栈满”状态这是一个初学者容易困惑的点。对于顺序栈栈满意味着数组空间已耗尽。但对于链栈呢从理论上讲只要操作系统还能分配内存链栈就可以一直创建新节点因此链栈通常被认为是不会“栈满”的。这也是链栈相比顺序栈的一大优势。然而在编程实践中当我们调用malloc申请新节点内存时如果系统内存不足malloc会返回NULL。这种情况下我们可以认为链栈“栈满”了。因此链栈的“栈满”判断实际上是对内存申请成功与否的判断。2.3 链栈的“栈空”状态链栈的栈空判断非常简单栈顶指针top是否为NULL。如果top NULL则表示链栈为空没有任何元素。// 判断链栈是否为空 int IsEmptyLinkStack(LinkStack *S) { // 如果栈顶指针为空或者元素个数为0则栈为空 return (S-top NULL) || (S-count 0); }有了这些基础概念我们就可以开始实现链栈的各项操作了。初始化是第一步也是确保后续操作正确性的关键。3. 链栈的初始化从无到有的正确起点初始化一个链栈本质上是创建一个“空栈”。空栈意味着栈顶指针不指向任何有效的节点。3.1 初始化步骤与代码实现正确的初始化流程如下为链栈结构体LinkStack动态申请内存。将栈顶指针top设置为NULL表示栈为空。将元素计数器count设置为 0。// 链栈的初始化 LinkStack* InitLinkStack() { // 1. 为链栈结构体申请内存 LinkStack *S (LinkStack*)malloc(sizeof(LinkStack)); if (S NULL) { printf(内存分配失败\n); return NULL; } // 2. 初始化栈顶指针和元素个数 S-top NULL; // 空栈栈顶指针置空 S-count 0; // 元素个数为0 printf(链栈初始化成功。\n); return S; // 返回初始化好的栈指针 }关键点解析为什么使用动态内存分配这使得栈的生命周期可以灵活控制可以在函数中创建并返回给调用者符合通用库函数的设计。错误处理对malloc的返回值进行了检查这是良好的编程习惯防止后续操作空指针导致程序崩溃。top初始化为NULL这是判断栈空的唯一依据至关重要。一个常见的错误是忘记将top初始化为NULL如果它是一个野指针后续判断栈空或进行指针操作将导致未定义行为。初始化完成后我们得到一个可以使用的空链栈。接下来最核心的两个操作入栈和出栈。4. 链栈的核心操作入栈与出栈详解入栈Push和出栈Pop是栈结构的灵魂。在链栈中这两个操作对应着链表头部的插入和删除。4.1 入栈Push操作入栈操作的步骤可以类比为“在链表头部插入一个新节点”创建新节点为新的栈元素动态申请一个节点内存。填充数据将数据存入新节点的数据域。连接新节点将新节点的next指针指向当前栈顶节点即原链表头。更新栈顶将链栈的top指针指向这个新节点。更新计数栈中元素个数count加1。// 链栈的入栈操作 int PushLinkStack(LinkStack *S, int e) { // 1. 参数检查 if (S NULL) { printf(栈指针无效\n); return 0; // 操作失败 } // 2. 创建新节点 (此处隐含了“栈满”判断内存是否申请成功) StackNode *newNode (StackNode*)malloc(sizeof(StackNode)); if (newNode NULL) { printf(内存分配失败入栈操作终止。\n); return 0; // 操作失败链栈“栈满” } // 3. 填充新节点数据 newNode-data e; // 4. 将新节点插入链表头部 newNode-next S-top; // 新节点指向原栈顶 // 5. 更新栈顶指针 S-top newNode; // 6. 更新元素计数 S-count; printf(元素 %d 入栈成功。当前栈大小%d\n, e, S-count); return 1; // 操作成功 }关键点解析“栈满”判断体现在malloc申请节点内存是否成功。失败则返回0。插入顺序必须先让newNode-next S-top再更新S-top newNode。顺序反了会导致链表断裂。时间复杂度O(1)。无论栈中有多少元素入栈操作只涉及常数次指针赋值和内存申请。4.2 出栈Pop操作出栈操作是入栈的逆过程对应“删除链表头节点”检查栈空如果栈为空则无法出栈。备份栈顶用一个临时指针p指向当前栈顶节点以便后续释放内存和返回数据。更新栈顶将栈顶指针top指向原栈顶节点的下一个节点S-top S-top-next。取出数据从临时指针p指向的节点中取出数据保存到输出参数中。释放内存释放临时指针p所指向的节点内存防止内存泄漏。更新计数栈中元素个数count减1。// 链栈的出栈操作 int PopLinkStack(LinkStack *S, int *e) { // 1. 参数检查 if (S NULL || e NULL) { printf(参数无效\n); return 0; } // 2. 检查栈空 if (IsEmptyLinkStack(S)) { printf(栈为空无法执行出栈操作。\n); return 0; } // 3. 备份栈顶节点指针 StackNode *p S-top; // 4. 取出栈顶数据 *e p-data; // 5. 更新栈顶指针 S-top p-next; // 6. 释放原栈顶节点内存 free(p); // 7. 更新元素计数 S-count--; printf(元素 %d 出栈成功。当前栈大小%d\n, *e, S-count); return 1; // 操作成功 }关键点解析栈空检查这是出栈操作的第一道安全门必不可少。内存管理free(p)是链式结构区别于顺序栈的关键。顺序栈出栈只需移动指针链栈必须手动释放内存否则会造成内存泄漏。数据返回通过指针参数e返回被删除的元素值这是获取出栈元素的常用方式。更新栈顶S-top p-next;这行代码即使p-next为NULL即出栈后栈变空也是正确的此时S-top被置为NULL符合空栈定义。时间复杂度O(1)。4.3 获取栈顶元素Peek这是一个只读操作不改变栈的状态。它对于检查栈顶内容非常有用。// 获取栈顶元素不删除 int GetTopLinkStack(LinkStack *S, int *e) { if (S NULL || e NULL) { return 0; } if (IsEmptyLinkStack(S)) { printf(栈为空无栈顶元素。\n); return 0; } *e S-top-data; // 直接读取栈顶节点的数据 return 1; }至此链栈的基本操作已经齐备。我们可以编写一个完整的测试程序来验证它们。5. 链栈的完整测试程序与运行结果理论需要实践来验证。下面是一个完整的C程序它演示了链栈从初始化、入栈、出栈到销毁的完整生命周期。#include stdio.h #include stdlib.h // 此处插入之前定义的 StackNode, LinkStack, // 以及 InitLinkStack, PushLinkStack, PopLinkStack, // GetTopLinkStack, IsEmptyLinkStack 等所有函数定义 // 打印链栈中的所有元素从栈顶到栈底 void PrintLinkStack(LinkStack *S) { if (S NULL || IsEmptyLinkStack(S)) { printf(栈为空或无效。\n); return; } printf(当前栈内容栈顶-栈底: ); StackNode *p S-top; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); } // 销毁链栈释放所有内存 void DestroyLinkStack(LinkStack *S) { if (S NULL) { return; } int temp; // 循环出栈直到栈空释放所有节点内存 while (!IsEmptyLinkStack(S)) { PopLinkStack(S, temp); // Pop操作内部会free节点 } // 最后释放栈结构体本身 free(S); printf(链栈已销毁所有内存已释放。\n); } int main() { printf( 链栈操作测试 \n); // 1. 初始化链栈 LinkStack *myStack InitLinkStack(); if (myStack NULL) { return -1; // 初始化失败退出 } // 2. 测试入栈操作 printf(\n--- 测试入栈 ---\n); for (int i 1; i 5; i) { PushLinkStack(myStack, i * 10); // 入栈 10, 20, 30, 40, 50 } PrintLinkStack(myStack); // 3. 测试获取栈顶元素 printf(\n--- 测试获取栈顶 ---\n); int topElem; if (GetTopLinkStack(myStack, topElem)) { printf(栈顶元素是%d\n, topElem); } PrintLinkStack(myStack); // 栈应无变化 // 4. 测试出栈操作 printf(\n--- 测试出栈 ---\n); int poppedElem; if (PopLinkStack(myStack, poppedElem)) { printf(出栈元素%d\n, poppedElem); } PrintLinkStack(myStack); // 5. 测试栈空判断 printf(\n--- 测试栈空判断 ---\n); printf(栈是否为空 %s\n, IsEmptyLinkStack(myStack) ? 是 : 否); // 6. 连续出栈直到栈空 printf(\n--- 连续出栈直到栈空 ---\n); while (!IsEmptyLinkStack(myStack)) { PopLinkStack(myStack, poppedElem); printf(出栈%d, , poppedElem); } printf(\n); printf(栈是否为空 %s\n, IsEmptyLinkStack(myStack) ? 是 : 否); // 7. 再次尝试出栈应失败 printf(\n--- 尝试对空栈出栈 ---\n); if (!PopLinkStack(myStack, poppedElem)) { printf(预期中的出栈失败栈已空。\n); } // 8. 销毁链栈 printf(\n--- 销毁链栈 ---\n); DestroyLinkStack(myStack); myStack NULL; // 避免悬空指针 printf(\n 测试结束 \n); return 0; }预期运行结果 链栈操作测试 链栈初始化成功。 --- 测试入栈 --- 元素 10 入栈成功。当前栈大小1 元素 20 入栈成功。当前栈大小2 元素 30 入栈成功。当前栈大小3 元素 40 入栈成功。当前栈大小4 元素 50 入栈成功。当前栈大小5 当前栈内容栈顶-栈底: 50 40 30 20 10 --- 测试获取栈顶 --- 栈顶元素是50 当前栈内容栈顶-栈底: 50 40 30 20 10 --- 测试出栈 --- 元素 50 出栈成功。当前栈大小4 出栈元素50 当前栈内容栈顶-栈底: 40 30 20 10 --- 测试栈空判断 --- 栈是否为空 否 --- 连续出栈直到栈空 --- 元素 40 出栈成功。当前栈大小3 出栈40, 元素 30 出栈成功。当前栈大小2 出栈30, 元素 20 出栈成功。当前栈大小1 出栈20, 元素 10 出栈成功。当前栈大小0 出栈10, 栈是否为空 是 --- 尝试对空栈出栈 --- 栈为空无法执行出栈操作。 预期中的出栈失败栈已空。 --- 销毁链栈 --- 栈为空无法执行出栈操作。 链栈已销毁所有内存已释放。 测试结束 通过这个测试你可以清晰地看到链栈“后进先出”的特性50最后入栈最先出栈以及所有基本操作的正确性。接下来我们探讨一个更高级的话题共享栈。6. 共享栈一种高效利用连续内存的设计共享栈是两个栈共享同一块连续内存空间的数据结构。通常一个栈的栈底在数组的起始位置另一个栈的栈底在数组的末尾两个栈的栈顶向中间增长。这种设计在内存使用上非常高效尤其适用于两个栈的空间需求存在此消彼长关系的场景。共享栈解决了什么问题假设你需要同时使用两个栈但无法准确预测各自需要多少空间。如果为每个栈单独分配一个固定大小的数组可能会出现一个栈已满而另一个栈还很空的情况造成内存浪费。共享栈将两个栈放在一个数组里让它们动态地共享整个空间提高了内存利用率。6.1 共享栈的结构定义与初始化我们使用一个数组和两个栈顶指针来实现共享栈。// 共享栈的最大容量 #define SHARED_STACK_MAX_SIZE 100 // 共享栈结构定义 typedef struct SharedStack { int data[SHARED_STACK_MAX_SIZE]; // 共享的存储数组 int top1; // 栈1的栈顶指针初始为-1 int top2; // 栈2的栈顶指针初始为SHARED_STACK_MAX_SIZE } SharedStack;关键设计top1指向栈1的栈顶元素。栈1从数组头部下标0开始增长。初始时栈空top1 -1。top2指向栈2的栈顶元素。栈2从数组尾部下标MAX_SIZE-1开始向头部增长。初始时栈空top2 MAX_SIZE。栈满条件两个栈的栈顶指针相遇即top1 1 top2。这意味着数组空间已被完全占用。初始化函数如下// 共享栈的初始化 void InitSharedStack(SharedStack *S) { if (S NULL) return; S-top1 -1; // 栈1为空 S-top2 SHARED_STACK_MAX_SIZE; // 栈2为空 printf(共享栈初始化成功。栈1顶指针%d, 栈2顶指针%d\n, S-top1, S-top2); }7. 共享栈的核心操作双栈的入栈与出栈共享栈的操作需要指定是对哪个栈进行操作栈1或栈2。我们用一个参数stackNumber(通常取1或2) 来区分。7.1 共享栈的入栈Push操作入栈前必须判断栈是否已满。// 共享栈的入栈操作 int PushSharedStack(SharedStack *S, int stackNumber, int e) { if (S NULL) { printf(栈指针无效\n); return 0; } // 1. 判断栈满 if (S-top1 1 S-top2) { printf(共享栈已满无法入栈。\n); return 0; } // 2. 根据栈编号执行入栈 if (stackNumber 1) { // 栈1栈顶指针先加1再存入数据 S-top1; S-data[S-top1] e; printf(元素 %d 入栈1成功。栈1顶指针%d\n, e, S-top1); } else if (stackNumber 2) { // 栈2栈顶指针先减1再存入数据 S-top2--; S-data[S-top2] e; printf(元素 %d 入栈2成功。栈2顶指针%d\n, e, S-top2); } else { printf(栈编号错误请输入1或2。\n); return 0; } return 1; }关键点解析栈满判断if (S-top1 1 S-top2)。这是共享栈的核心逻辑表示两个栈的栈顶即将相遇没有空闲单元。指针移动方向栈1的top1向数组尾部增长栈2的top2向数组头部增长--。操作隔离两个栈的操作完全独立只是共享存储空间。7.2 共享栈的出栈Pop操作出栈前必须判断目标栈是否为空。// 共享栈的出栈操作 int PopSharedStack(SharedStack *S, int stackNumber, int *e) { if (S NULL || e NULL) { printf(参数无效\n); return 0; } if (stackNumber 1) { // 1. 判断栈1是否为空 if (S-top1 -1) { printf(栈1为空无法出栈。\n); return 0; } // 2. 取出栈顶数据 *e S-data[S-top1]; // 3. 栈顶指针减1 S-top1--; printf(元素 %d 从栈1出栈成功。栈1顶指针%d\n, *e, S-top1); } else if (stackNumber 2) { // 1. 判断栈2是否为空 if (S-top2 SHARED_STACK_MAX_SIZE) { printf(栈2为空无法出栈。\n); return 0; } // 2. 取出栈顶数据 *e S-data[S-top2]; // 3. 栈顶指针加1 S-top2; printf(元素 %d 从栈2出栈成功。栈2顶指针%d\n, *e, S-top2); } else { printf(栈编号错误请输入1或2。\n); return 0; } return 1; }关键点解析栈空判断栈1空的条件是top1 -1栈2空的条件是top2 MAX_SIZE。指针移动出栈后栈1的top1减1栈2的top2加1释放该存储单元。与链栈的区别共享栈的出栈不需要释放内存只是移动指针因为内存是预先分配的数组。7.3 共享栈的判空与栈满函数// 判断共享栈中的某个栈是否为空 int IsEmptySharedStack(SharedStack *S, int stackNumber) { if (S NULL) return 1; if (stackNumber 1) { return (S-top1 -1); } else if (stackNumber 2) { return (S-top2 SHARED_STACK_MAX_SIZE); } return 1; // 参数错误视为空 } // 判断共享栈是否已满 int IsFullSharedStack(SharedStack *S) { if (S NULL) return 0; return (S-top1 1 S-top2); }8. 共享栈的完整测试程序下面是一个测试共享栈所有功能的完整程序。#include stdio.h #include stdlib.h #define SHARED_STACK_MAX_SIZE 10 // 为了便于观察这里使用小容量 // 此处插入之前定义的 SharedStack 结构体 // 以及 InitSharedStack, PushSharedStack, PopSharedStack, // IsEmptySharedStack, IsFullSharedStack 等函数定义 // 打印共享栈的整个数组状态便于观察 void PrintSharedStack(SharedStack *S) { if (S NULL) return; printf(\n共享栈数组状态 [0~%d]:\n, SHARED_STACK_MAX_SIZE - 1); printf(索引: ); for (int i 0; i SHARED_STACK_MAX_SIZE; i) { printf(%3d , i); } printf(\n数据: ); for (int i 0; i SHARED_STACK_MAX_SIZE; i) { // 标记栈1和栈2的当前范围 if (i S-top1) { printf( S1 ); // 栈1区域 } else if (i S-top2) { printf( S2 ); // 栈2区域 } else { printf( -- ); // 空闲区域 } } printf(\n); printf(栈1顶指针 top1 %d, 栈2顶指针 top2 %d\n, S-top1, S-top2); printf(栈1是否空: %s, 栈2是否空: %s, 共享栈是否满: %s\n, IsEmptySharedStack(S, 1) ? 是 : 否, IsEmptySharedStack(S, 2) ? 是 : 否, IsFullSharedStack(S) ? 是 : 否); } int main() { printf( 共享栈操作测试 (最大容量: %d) \n, SHARED_STACK_MAX_SIZE); SharedStack S; InitSharedStack(S); PrintSharedStack(S); int elem; printf(\n--- 测试向栈1入栈3个元素 ---\n); for (int i 1; i 3; i) { PushSharedStack(S, 1, i * 100); // 入栈 100, 200, 300 } PrintSharedStack(S); printf(\n--- 测试向栈2入栈4个元素 ---\n); for (int i 1; i 4; i) { PushSharedStack(S, 2, i * 10); // 入栈 10, 20, 30, 40 } PrintSharedStack(S); printf(\n--- 测试从栈1出栈1个元素 ---\n); PopSharedStack(S, 1, elem); printf(出栈元素: %d\n, elem); PrintSharedStack(S); printf(\n--- 测试填满共享栈 ---\n); // 此时已用空间栈1有2个(100,200)栈2有4个(10,20,30,40)共6个。 // 剩余空间10 - 6 4个。 printf(尝试向栈1再入栈4个元素 (500,600,700,800)...\n); for (int i 5; i 8; i) { if (!PushSharedStack(S, 1, i * 100)) { break; // 如果栈满停止 } } PrintSharedStack(S); printf(\n--- 测试栈满后尝试入栈 ---\n); if (!PushSharedStack(S, 2, 99)) { printf(预期中的入栈失败共享栈已满。\n); } printf(\n--- 测试清空栈2 ---\n); while (!IsEmptySharedStack(S, 2)) { PopSharedStack(S, 2, elem); printf(从栈2出栈: %d, , elem); } printf(\n); PrintSharedStack(S); printf(\n--- 测试栈2空后尝试出栈 ---\n); if (!PopSharedStack(S, 2, elem)) { printf(预期中的出栈失败栈2已空。\n); } printf(\n 测试结束 \n); return 0; }预期运行结果片段 共享栈操作测试 (最大容量: 10) 共享栈初始化成功。栈1顶指针-1, 栈2顶指针10 共享栈数组状态 [0~9]: 索引: 0 1 2 3 4 5 6 7 8 9 数据: -- -- -- -- -- -- -- -- -- -- 栈1顶指针 top1 -1, 栈2顶指针 top2 10 栈1是否空: 是, 栈2是否空: 是, 共享栈是否满: 否 --- 测试向栈1入栈3个元素 --- 元素 100 入栈1成功。栈1顶指针0 ... 共享栈数组状态 [0~9]: 索引: 0 1 2 3 4 5 6 7 8 9 数据: S1 S1 S1 -- -- -- -- -- -- -- 栈1顶指针 top1 2, 栈2顶指针 top2 10 ... --- 测试填满共享栈 --- 尝试向栈1再入栈4个元素 (500,600,700,800)... 元素 500 入栈1成功。栈1顶指针3 ... 元素 800 入栈1成功。栈1顶指针6 共享栈数组状态 [0~9]: 索引: 0 1 2 3 4 5 6 7 8 9 数据: S1 S1 S1 S1 S1 S1 S1 S2 S2 S2 栈1顶指针 top1 6, 栈2顶指针 top2 7 栈1是否空: 否, 栈2是否空: 否, 共享栈是否满: 是通过这个测试你可以直观地看到两个栈的栈顶指针如何从两端向中间移动并最终相遇top16,top27满足top11 top2标志着共享栈已满。9. 常见问题与排查思路在实际实现链栈和共享栈时你可能会遇到以下问题问题现象可能原因排查方式解决方案链栈入栈失败程序崩溃1. 未检查malloc返回值。2. 栈指针S未初始化或为NULL。1. 检查入栈函数开头对S的判空。2. 检查malloc后是否判断了newNode NULL。1. 确保栈已正确初始化。2. 在malloc后添加内存分配失败的判断和处理。链栈出栈后访问数据出错1. 出栈时未先检查栈空。2. 出栈后使用了已释放节点的数据指针。1. 在Pop函数开始检查IsEmpty。2. 确保在free(p)之前已将数据保存或返回。1. 严格遵守“先判空再操作”的原则。2. 数据保存到临时变量或输出参数后再释放节点。链栈内存泄漏只进行了Pop操作但未在销毁栈时释放所有节点。检查销毁函数是否循环Pop直到栈空或遍历链表逐个free。实现DestroyLinkStack函数确保释放所有节点内存和栈结构体内存。共享栈判断栈满逻辑错误栈满条件写错例如写成top1 top2。画图分析当两个栈顶指针相邻时即top11 top2时栈满。top1 top2意味着已经重叠可能已发生数据覆盖。将栈满条件修正为if (S-top1 1 S-top2)。共享栈入栈到错误的栈混淆了栈1和栈2的指针移动方向。画图记忆栈1 (top1) 从-1开始向数组尾部增长 ()。栈2 (top2) 从MAX_SIZE开始向数组头部增长 (--)。为栈1和栈2分别编写独立的入栈出栈代码块并添加清晰的注释。打印链栈时顺序错误遍历链表时从栈顶到栈底的顺序理解反了。链栈的栈顶是链表头。打印时从头节点 (S-top) 开始通过next指针遍历到NULL顺序就是“栈顶-栈底”。确认遍历起点是S-top循环条件是p ! NULL步进是p p-next。10. 最佳实践与工程建议掌握了基本操作后将这些知识应用到实际项目或进一步学习时请记住以下建议封装与模块化将栈的结构定义和所有操作函数放在独立的头文件.h和源文件.c中。这提高了代码的复用性和可维护性。例如创建link_stack.h和link_stack.c。增强健壮性参数校验所有公开的函数入口都应进行参数有效性检查如指针非空。错误码定义定义一套清晰的错误码枚举类型让函数调用者能准确知道失败原因如STACK_EMPTY,STACK_FULL,MEMORY_ALLOC_FAIL等而不是简单地返回0/1。资源管理对于链栈确保malloc和free成对出现。考虑在初始化失败或操作中途失败时进行已分配资源的清理。考虑泛型编程本文示例使用int类型数据。在实际库中可以考虑使用void*指针来存储任意类型的数据或者利用C的模板、Java的泛型来实现通用栈。性能与权衡链栈优势在于动态扩容但每个节点有额外指针开销且内存分配/释放频繁可能影响性能。在需要频繁变长且对内存使用不苛刻的场景下使用。顺序栈/共享栈优势在于内存连续访问效率高无内存碎片但容量固定。在容量可预估、追求性能的场景下使用。共享栈是顺序栈的变体在需要两个栈且总空间固定的场景下内存利用率最高。测试驱动像本文一样为你的栈实现编写全面的测试用例覆盖正常操作、边界条件空栈、满栈和错误情况无效参数。这能极大减少隐藏的Bug。链栈和共享栈是理解栈这种数据结构及其不同实现方式的绝佳范例。链栈教你如何用动态内存管理来构建灵活的数据结构而共享栈则展示了如何通过巧妙的指针设计来高效利用静态内存。理解它们不仅是为了通过考试更是为了培养解决实际内存管理问题的思维能力。当你下次需要实现一个缓冲区、管理一个任务列表或者设计一个需要双向增长的数据区域时这次学习的经验就会派上用场。建议你将本文的代码亲手敲一遍并尝试修改测试用例观察不同的行为这是巩固理解的最佳途径。