★ FEATURED ARTICLE 1. 为什么我要重新把顺序栈和链栈翻出来讲一遍栈这个数据结构几乎是所有计算机专业学生接触到的第一个“真正的”数据结构。数组和链表好歹还能在现实生活里找到直接对应物比如一排储物柜或者一列火车车厢但栈这个东西第一次听老师讲“后进先出”的时候很多人脑子里其实是没有画面的。我当年也是这样直到自己用C语言把顺序栈和链栈各写了一遍又拿它们去解决了一些实际问题才真正理解为什么这个看起来简单到不行的结构能在编译器、操作系统、表达式求值这些领域里扮演核心角色。这篇文章主要面向三类人第一类是在校学生正在学数据结构与算法需要把顺序栈和链栈的代码真正跑通、理解透第二类是需要快速复习C语言手写数据结构的老手可能工作中突然要用到需要一份可以直接参考的实现第三类是对底层实现有兴趣的开发者想搞清楚顺序存储和链式存储在栈这个场景下到底有什么本质区别。我会从设计思路、核心操作、完整实现、常见问题四个维度展开把顺序栈和链栈的每一行关键代码都讲清楚同时补充大量实际编码中才会遇到的细节和坑。先给一个最直观的类比。栈就像一摞盘子你只能从最上面拿盘子也只能把新盘子放到最上面。你不能从中间抽一个盘子出来也不能从底部塞一个进去。这个限制看起来很不方便但正是这种限制让栈在很多场景下变得极其高效和可靠。函数调用就是最典型的例子每次调用一个新函数系统就把当前函数的上下文压入调用栈函数返回时再弹出恢复到调用前的状态。没有栈递归根本没法实现表达式求值也会变得异常复杂。顺序栈和链栈的区别本质上就是数组和链表的区别在栈这个特定结构上的体现。顺序栈用一段连续的内存空间存储元素靠一个栈顶指针来标记当前栈顶位置链栈用一组不连续的节点每个节点包含数据和指向下一个节点的指针栈顶就是链表的头节点。两者在时间复杂度上都是O(1)的入栈和出栈但在空间管理、扩容策略、内存碎片、缓存友好性等方面差异巨大。选哪个取决于你的具体场景。我见过太多人学完栈之后只知道“后进先出”四个字真让他写一个带扩容的顺序栈或者一个不带头节点的链栈就卡壳了。所以这篇文章不会只讲概念我会把完整的C语言代码贴出来逐段解释并且告诉你哪些地方容易写错、哪些地方面试官特别喜欢问、哪些地方在实际项目中会踩坑。2. 顺序栈的设计思路与核心操作拆解2.1 顺序栈的结构体定义与初始化策略顺序栈的结构体定义看起来简单但里面有几个关键决策点。最基础的版本长这样#define MAXSIZE 100 typedef int ElemType; typedef struct { ElemType data[MAXSIZE]; int top; } SqStack;这里top指向栈顶元素的下标初始化为-1表示空栈。为什么是-1而不是0因为如果top0表示空栈那么入栈时就要先加再存出栈时就要先取再减逻辑上容易搞混。用-1作为空栈标记入栈就是data[top]x出栈就是xdata[top--]非常对称不容易出错。但固定大小的数组在实际使用中限制太大。你没法预知用户会压入多少个元素设大了浪费内存设小了不够用。所以更实用的做法是动态分配typedef struct { ElemType *data; int top; int capacity; } SqStack; void InitStack(SqStack *s, int initCapacity) { s-data (ElemType *)malloc(sizeof(ElemType) * initCapacity); if (s-data NULL) { exit(OVERFLOW); } s-top -1; s-capacity initCapacity; }这里capacity记录了当前分配的容量top仍然是栈顶下标。初始容量设多少我的经验是如果你大概知道数据规模就设一个略大于预估值的数如果完全不知道设16或者32比较合适太小了会频繁扩容太大了浪费内存。扩容策略后面会详细讲。还有一个细节top用int还是size_tint可以表示-1方便表示空栈。size_t是无符号的没法表示-1所以如果你用size_t就需要额外的标志位或者用top0表示空栈但逻辑会变扭。我建议用int除非你的栈元素数量真的可能超过INT_MAX那种情况极其罕见。2.2 入栈操作的边界条件与扩容机制入栈的核心逻辑就两步检查是否栈满如果满了就扩容或者报错然后把新元素放到栈顶并更新top。固定大小的版本很简单int Push(SqStack *s, ElemType x) { if (s-top MAXSIZE - 1) { return 0; // 栈满 } s-data[(s-top)] x; return 1; }动态版本就需要处理扩容int Push(SqStack *s, ElemType x) { if (s-top s-capacity - 1) { int newCapacity s-capacity * 2; ElemType *newData (ElemType *)realloc(s-data, sizeof(ElemType) * newCapacity); if (newData NULL) { return 0; } s-data newData; s-capacity newCapacity; } s-data[(s-top)] x; return 1; }扩容倍数为什么选2这是一个摊销分析的问题。如果每次扩容只增加固定大小比如每次加1那么连续压入n个元素的总时间复杂度是O(n²)因为每次扩容都要复制所有已有元素。如果每次扩容乘以一个常数因子kk1那么总时间复杂度是O(n)因为复制操作的次数是等比数列求和。k选2是工程上的折中k太大浪费内存k太小复制次数多。有些实现用1.5比如某些标准库的vector实现理由是1.5可以更好地复用之前释放的内存块。但在栈这个场景下2就够用了。注意realloc之后一定要用临时指针接收返回值直接s-data realloc(s-data, ...)是经典错误。如果realloc失败返回NULL原来的s-data就丢了造成内存泄漏。2.3 出栈与取栈顶元素的区别与实现出栈和取栈顶元素经常被混淆。出栈是删除栈顶元素并返回它栈的大小减一取栈顶元素只是查看栈顶元素的值栈的大小不变。两者的前提条件都是栈非空。int Pop(SqStack *s, ElemType *x) { if (s-top -1) { return 0; // 栈空 } *x s-data[(s-top)--]; return 1; } int GetTop(SqStack *s, ElemType *x) { if (s-top -1) { return 0; } *x s-data[s-top]; return 1; }这里用返回值表示操作是否成功用指针参数带回数据。这是C语言里常见的错误处理模式。你也可以用断言assert但在生产代码里断言会被禁用所以还是显式返回状态更可靠。有一个容易忽略的点出栈之后原来的栈顶位置的数据还在内存里只是top减一了。如果栈里存的是指针或者有敏感数据最好在出栈时把那个位置清零防止悬空指针或者信息泄露。比如*x s-data[s-top]; s-data[s-top] 0; // 清除数据 s-top--;对于基本数据类型无所谓但对于指针类型这个习惯能帮你避免很多调试噩梦。2.4 判空、判满与销毁操作的完整实现判空就是top -1判满就是top capacity - 1。销毁操作要释放动态分配的内存void DestroyStack(SqStack *s) { if (s-data ! NULL) { free(s-data); s-data NULL; } s-top -1; s-capacity 0; }这里把data置为NULL、top置为-1、capacity置为0是为了防止销毁后误用。有些实现只free不置空如果后面不小心又调用了Push就会访问已释放的内存行为不可预测。还有一个操作是清空栈只重置top不释放内存void ClearStack(SqStack *s) { s-top -1; }清空和销毁的区别要搞清楚清空之后栈还可以继续用销毁之后栈就不能用了除非重新初始化。3. 链栈的实现细节与操作要点3.1 链栈的节点设计与栈顶指针管理链栈的节点和单链表节点一模一样typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int size; } LinkStack;这里我用了带头节点的设计还是不带两种都可以。不带带头节点的版本top直接指向栈顶元素节点空栈时top NULL。带头节点的版本top指向一个虚拟头节点空栈时top-next NULL。我倾向于不带带头节点因为栈的操作只在栈顶进行不需要头节点来简化插入删除。不带头的版本更直观void InitStack(LinkStack *s) { s-top NULL; s-size 0; }size字段不是必须的但加上它可以O(1)获取栈大小不用遍历。如果你不需要频繁获取大小可以省掉这个字段。链栈的入栈就是头插法int Push(LinkStack *s, ElemType x) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; } newNode-data x; newNode-next s-top; s-top newNode; s-size; return 1; }出栈就是删除头节点int Pop(LinkStack *s, ElemType *x) { if (s-top NULL) { return 0; } StackNode *temp s-top; *x temp-data; s-top temp-next; free(temp); s-size--; return 1; }注意出栈时先用temp保存栈顶节点更新top之后再free(temp)。顺序不能反否则就访问了已释放的内存。3.2 链栈入栈出栈的指针操作陷阱链栈的指针操作有几个经典陷阱。第一个是入栈时忘记把新节点的next指向原来的栈顶。如果你写成newNode-data x; s-top newNode; // 错误newNode-next还是野指针这样新节点的next是未初始化的下次出栈时s-top temp-next就会跳到一个随机地址程序崩溃。正确的顺序是先连后断先把新节点接到原来的栈顶上再更新栈顶指针。第二个陷阱是出栈时free之后没有把top指向下一个节点。如果你写成free(s-top); s-top s-top-next; // 错误访问已释放的内存free之后s-top指向的内存已经无效再访问s-top-next就是未定义行为。必须先保存next再free。第三个陷阱是空栈时出栈没有检查。如果s-top NULLtemp s-top得到NULL*x temp-data就是空指针解引用直接段错误。所以出栈前必须判空。提示链栈的每个节点都是malloc出来的如果你频繁入栈出栈内存分配和释放的开销会比较大。在性能敏感的场景下可以考虑用内存池或者对象池来复用节点。3.3 链栈的销毁与遍历操作链栈的销毁需要遍历所有节点并逐个释放void DestroyStack(LinkStack *s) { StackNode *p s-top; while (p ! NULL) { StackNode *temp p; p p-next; free(temp); } s-top NULL; s-size 0; }这里用p遍历temp保存当前节点先移动p再free(temp)。顺序同样不能反。链栈的遍历是从栈顶到栈底和入栈顺序相反void PrintStack(LinkStack *s) { StackNode *p s-top; while (p ! NULL) { printf(%d , p-data); p p-next; } printf(\n); }遍历操作不会改变栈的结构但会暴露栈的内部顺序。如果你不想让外部知道栈的内部结构就不要提供遍历接口只提供入栈、出栈、取栈顶、判空这几个基本操作。3.4 顺序栈与链栈的对比选型对比维度顺序栈链栈存储方式连续内存离散节点入栈时间复杂度O(1)摊销O(1)出栈时间复杂度O(1)O(1)空间开销可能预留多余空间每个节点多一个指针开销扩容需要realloc和复制不需要动态分配节点缓存友好性好连续内存差节点分散内存碎片少多实现复杂度中等中等适用场景元素数量可预估、追求性能元素数量变化大、频繁增删顺序栈的缓存友好性是一个经常被忽略但非常重要的优势。现代CPU的缓存行通常是64字节顺序栈的连续内存意味着入栈出栈时CPU可以预取相邻数据命中率高。链栈的节点分散在堆的各个角落每次访问都可能缓存未命中性能差距在数据量大时非常明显。但链栈也不是没有优势。顺序栈扩容时需要复制所有元素如果栈里存的是大对象复制开销很大。链栈不需要复制只是分配一个新节点。另外顺序栈需要一段连续的内存如果内存碎片化严重可能分配不到足够大的连续空间链栈没有这个限制。我的建议是如果你能预估栈的最大深度并且这个深度不会太大比如几千到几万用顺序栈。如果栈的深度可能非常大比如几十万上百万或者元素本身很大用链栈。如果对性能有极致要求顺序栈通常是更好的选择。4. 完整可运行的C语言实现与测试4.1 顺序栈的完整代码与编译运行把前面的片段整合成一个完整的顺序栈实现#include stdio.h #include stdlib.h #define INIT_CAPACITY 16 typedef int ElemType; typedef struct { ElemType *data; int top; int capacity; } SqStack; void InitStack(SqStack *s) { s-data (ElemType *)malloc(sizeof(ElemType) * INIT_CAPACITY); if (s-data NULL) { fprintf(stderr, 内存分配失败\n); exit(EXIT_FAILURE); } s-top -1; s-capacity INIT_CAPACITY; } int IsEmpty(SqStack *s) { return s-top -1; } int Push(SqStack *s, ElemType x) { if (s-top s-capacity - 1) { int newCapacity s-capacity * 2; ElemType *newData (ElemType *)realloc(s-data, sizeof(ElemType) * newCapacity); if (newData NULL) { return 0; } s-data newData; s-capacity newCapacity; } s-data[(s-top)] x; return 1; } int Pop(SqStack *s, ElemType *x) { if (IsEmpty(s)) { return 0; } *x s-data[(s-top)--]; return 1; } int GetTop(SqStack *s, ElemType *x) { if (IsEmpty(s)) { return 0; } *x s-data[s-top]; return 1; } void DestroyStack(SqStack *s) { free(s-data); s-data NULL; s-top -1; s-capacity 0; } int main() { SqStack s; InitStack(s); for (int i 1; i 20; i) { Push(s, i * 10); } ElemType val; GetTop(s, val); printf(栈顶元素: %d\n, val); printf(出栈顺序: ); while (Pop(s, val)) { printf(%d , val); } printf(\n); DestroyStack(s); return 0; }编译命令gcc -o sqstack sqstack.c -Wall -Wextra -g-Wall -Wextra打开所有警告-g保留调试信息。我强烈建议每次写C代码都加上这些选项很多潜在问题编译器都能帮你发现。运行结果应该是先打印栈顶元素200然后从200倒序打印到10。4.2 链栈的完整代码与测试用例链栈的完整实现#include stdio.h #include stdlib.h typedef int ElemType; typedef struct StackNode { ElemType data; struct StackNode *next; } StackNode; typedef struct { StackNode *top; int size; } LinkStack; void InitStack(LinkStack *s) { s-top NULL; s-size 0; } int IsEmpty(LinkStack *s) { return s-top NULL; } int Push(LinkStack *s, ElemType x) { StackNode *newNode (StackNode *)malloc(sizeof(StackNode)); if (newNode NULL) { return 0; } newNode-data x; newNode-next s-top; s-top newNode; s-size; return 1; } int Pop(LinkStack *s, ElemType *x) { if (IsEmpty(s)) { return 0; } StackNode *temp s-top; *x temp-data; s-top temp-next; free(temp); s-size--; return 1; } int GetTop(LinkStack *s, ElemType *x) { if (IsEmpty(s)) { return 0; } *x s-top-data; return 1; } void DestroyStack(LinkStack *s) { StackNode *p s-top; while (p ! NULL) { StackNode *temp p; p p-next; free(temp); } s-top NULL; s-size 0; } int main() { LinkStack s; InitStack(s); for (int i 1; i 10; i) { Push(s, i); } printf(栈大小: %d\n, s.size); ElemType val; GetTop(s, val); printf(栈顶元素: %d\n, val); printf(出栈顺序: ); while (Pop(s, val)) { printf(%d , val); } printf(\n); DestroyStack(s); return 0; }测试用例应该覆盖空栈出栈、空栈取栈顶、连续入栈出栈、大量数据入栈出栈、入栈后销毁再初始化。我通常会写一个简单的测试函数void TestLinkStack() { LinkStack s; InitStack(s); // 空栈操作 ElemType val; if (Pop(s, val) ! 0) { printf(错误空栈出栈应该失败\n); } if (GetTop(s, val) ! 0) { printf(错误空栈取栈顶应该失败\n); } // 单元素 Push(s, 42); GetTop(s, val); if (val ! 42) { printf(错误栈顶应该是42\n); } // 大量元素 for (int i 0; i 10000; i) { Push(s, i); } if (s.size ! 10001) { printf(错误栈大小应该是10001\n); } DestroyStack(s); printf(所有测试通过\n); }4.3 用栈解决实际问题括号匹配与表达式求值栈最经典的应用就是括号匹配。给定一个只包含(、)、[、]、{、}的字符串判断括号是否合法匹配。思路很简单遇到左括号就入栈遇到右括号就看栈顶是否是对应的左括号如果是就出栈否则不匹配。最后栈为空说明匹配。int IsBalanced(const char *str) { SqStack s; InitStack(s); for (int i 0; str[i] ! \0; i) { char c str[i]; if (c ( || c [ || c {) { Push(s, c); } else if (c ) || c ] || c }) { if (IsEmpty(s)) { DestroyStack(s); return 0; } char top; Pop(s, top); if ((c ) top ! () || (c ] top ! [) || (c } top ! {)) { DestroyStack(s); return 0; } } } int result IsEmpty(s); DestroyStack(s); return result; }另一个经典应用是后缀表达式求值。后缀表达式也叫逆波兰表达式运算符在操作数后面比如3 4 表示34。求值过程遇到数字就入栈遇到运算符就弹出两个操作数计算后再入栈。最后栈里剩下的就是结果。int EvalRPN(const char **tokens, int count) { SqStack s; InitStack(s); for (int i 0; i count; i) { const char *token tokens[i]; if (token[0] 0 token[0] 9) { Push(s, atoi(token)); } else { int b, a; Pop(s, b); Pop(s, a); int result; switch (token[0]) { case : result a b; break; case -: result a - b; break; case *: result a * b; break; case /: result a / b; break; default: result 0; } Push(s, result); } } int result; Pop(s, result); DestroyStack(s); return result; }这两个例子展示了栈的核心价值当你需要“记住”之前的某些状态并且这些状态的访问顺序是后进先出时栈就是最自然的选择。5. 常见问题与排查技巧实录5.1 顺序栈的典型Bug与修复方法问题一扩容后指针失效。如果你在别的地方保存了data数组的指针扩容后realloc可能返回新的地址原来的指针就悬空了。解决办法是不要保存data的内部指针所有访问都通过栈结构体。问题二top类型不匹配。如果top用unsigned inttop -1永远为假空栈判断失效。用int最稳妥。问题三忘记初始化。InitStack之前就调用Pushdata是野指针直接崩溃。解决办法是在InitStack里把data置为NULL在Push里检查data是否为NULL。问题四内存泄漏。只free了栈结构体本身没有free里面的data数组。如果栈结构体是动态分配的需要先DestroyStack再free结构体。5.2 链栈的常见错误与调试技巧错误一入栈顺序反了。先s-top newNode再newNode-next s-top结果newNode-next指向自己形成自环。正确顺序是先newNode-next s-top再s-top newNode。错误二出栈时free顺序错了。先free(s-top)再s-top s-top-next访问已释放内存。正确顺序是先保存next再free。错误三忘记更新size。入栈出栈时size没有同步增减导致size和实际节点数不一致。解决办法是把size的更新放在入栈出栈函数的最后确保每次操作都更新。错误四销毁时只释放了栈顶节点。只free(s-top)后面的节点全部泄漏。必须遍历释放。调试链栈问题时我常用的方法是画图。把每个节点的地址、data、next都画出来然后模拟入栈出栈过程一步一步跟踪指针变化。纸上画一遍比在脑子里想十遍都管用。5.3 内存管理与性能优化的实操心得顺序栈的扩容策略除了乘2还可以考虑乘1.5。乘1.5的好处是内存复用率更高因为释放的旧块大小是capacity新块大小是1.5*capacity旧块可以被后续的分配复用。乘2的话旧块大小是capacity新块是2*capacity旧块太小没法复用。但在栈这个场景下扩容次数本来就不多乘2和乘1.5的差异可以忽略。链栈的性能优化主要是减少malloc和free的次数。一个简单的做法是维护一个空闲节点链表出栈时不free节点而是把节点放到空闲链表里入栈时先从空闲链表取取不到再malloc。这样可以显著减少内存分配开销代价是需要额外的空闲链表管理代码。还有一个技巧是预分配一批节点。如果你知道栈的最大深度可以一次性malloc一个节点数组然后用数组元素作为节点用下标代替指针。这样既保留了链式结构的灵活性又避免了频繁的内存分配。不过这种实现比较复杂一般场景用不上。提示在嵌入式或者资源受限的环境下顺序栈通常是更好的选择因为它没有动态内存分配的开销所有内存都是静态分配的行为可预测。链栈在那种环境下反而容易因为内存碎片导致问题。5.4 面试中高频出现的栈相关追问面试官问栈的时候通常不会只让你写一个入栈出栈就完事。常见的追问包括两个栈如何共享一个数组答案是用两个栈顶指针从数组两端向中间生长栈满条件是top1 1 top2。如何实现一个O(1)获取最小值的栈答案是用一个辅助栈同步记录当前最小值入栈时如果新元素小于等于辅助栈顶就同时入辅助栈出栈时如果出栈元素等于辅助栈顶就同时出辅助栈。如何用两个栈实现一个队列答案是一个输入栈一个输出栈入队时压入输入栈出队时如果输出栈为空就把输入栈全部弹出压入输出栈然后从输出栈弹出。栈和递归的关系是什么答案是递归本质上就是函数调用栈的压栈和出栈任何递归都可以用显式栈改写为迭代。这些问题背后的核心都是对栈的“后进先出”特性的灵活运用。你把顺序栈和链栈的基本操作写熟了这些扩展问题自然就有思路了。5.5 常见问题速查表问题现象可能原因排查方法修复方式程序崩溃在Pushdata未初始化检查InitStack是否调用先InitStack再Push出栈数据错乱top更新顺序错误打印top和data确保先存后移或先移后存内存泄漏只free结构体未free datavalgrind检测DestroyStack中free data链栈死循环next指向自己打印节点地址调整入栈指针顺序扩容后数据丢失realloc返回值未接收检查realloc调用用临时指针接收空栈出栈段错误未判空加打印或断点Pop前先IsEmptysize与实际不符忘记更新size打印size和遍历计数入栈出栈同步更新栈顶元素错误GetTop和Pop混淆检查调用的是哪个明确语义GetTop不改变栈这张表里的问题我几乎每一个都踩过尤其是链栈的指针顺序问题当年调试了整整一个下午才发现是两行代码写反了。所以你现在如果遇到类似问题不要慌先画图再打印最后单步调试没有解决不了的Bug。6. 我个人的一些编码习惯和体会写了这么多年的C语言数据结构我养成了几个习惯。第一个是每个数据结构都配一个测试文件测试用例覆盖空结构、单元素、大量元素、边界条件这四种情况。第二个是每次malloc之后立刻检查返回值虽然大多数时候不会失败但一旦失败就是崩溃早检查早发现。第三个是free之后立刻把指针置为NULL防止悬空指针。第四个是尽量用assert在开发阶段捕获逻辑错误发布时用#define NDEBUG禁用。顺序栈和链栈的代码都不长加起来也就两三百行但里面涉及的指针操作、内存管理、边界条件处理几乎涵盖了C语言里最容易出错的所有方面。你把这两个结构写熟、调通、理解透再去看更复杂的数据结构比如树、图、哈希表会发现很多思路是相通的。最后分享一个我常用的调试技巧在栈的实现里加一个CheckStack函数遍历整个栈检查top和size是否一致、节点是否成环、数据是否在合理范围内。每次入栈出栈后调用一次虽然会降低性能但在开发阶段能帮你快速定位问题。发布时把这个函数去掉或者用宏控制即可。这个内容后续还可以这样扩展把顺序栈和链栈封装成统一的接口用函数指针实现多态或者实现一个线程安全的栈用互斥锁保护入栈出栈操作或者把栈应用到更复杂的场景比如深度优先搜索的非递归实现、浏览器的前进后退功能、编辑器的撤销重做功能。每一个方向都值得单独写一篇。
阅读完成 · 觉得有帮助？
