栈stack是数据结构里最基础也最容易用错的一种线性结构。今天我不绕弯子直接用C语言把顺序栈和链式栈从结构体定义到入栈出栈、从边界条件到项目选型完整地聊一遍。这篇文章适合正在学《数据结构》的本科生、准备考研笔试的同学以及写C代码多年但一直没把栈的细节吃透的朋友。我会把每个关键操作背后的“为什么”讲清楚也会把我在调试中踩过的坑直接摊开给你看。1. 栈的核心原理只有一端能动的数据结构1.1 后进先出到底在说什么栈的英文是stack直译过来是“堆叠”。想象你在食堂叠盘子新洗好的盘子永远放在最上面用盘子的时候也是从最上面拿。这个“只能从顶部放入、只能从顶部取出”的规则就是栈的全部灵魂。栈顶top是唯一能操作的入口栈底bottom固定不动中间的元素看不见也不能碰。很多新手一开始会纠结为什么栈不设计成能像数组一样任意访问某个位置因为它的设计目标恰恰是“限制访问”。在算法和系统底层里我们经常需要暂存一批状态但必须以“后来居上”的顺序恢复它们。函数调用就是这样A调用BB调用CC返回后回到BB返回后回到A永远是最晚调用的函数先返回。操作系统里的函数调用栈、浏览器里的后退按钮、编辑器里的撤销操作全都是同一个思想。1.2 栈的抽象数据类型用C语言写栈之前先把接口定清楚。栈至少需要这几个操作初始化一个空栈、压入一个元素push、弹出一个元素pop、读取栈顶元素但不弹出top/peek、判断栈是否为空isEmpty。顺序栈还需要判断栈是否已满isFull因为数组容量有限。从ADT抽象数据类型的角度看我们只关心这些操作的行为不关心底层用数组还是链表。但C语言没有类所以只能靠结构体加函数来模拟。这一点和C/Java的class不一样但它能让你更清楚地看到数据到底存在哪里指针到底怎么变化。2. 顺序栈用数组模拟一个“竖着的”存储区2.1 结构体设计与初始化顺序栈的物理底子就是一段连续内存用数组保存数据再用一个整型变量top记录栈顶元素在数组中的下标。常见定义#define MaxSize 100 typedef struct { int data[MaxSize]; int top; } SqStack;这里有个关键约定我把top初始化为-1表示栈为空。为什么不是0因为数组下标从0开始如果top0就代表栈顶在第0号位置这时栈里其实已经有一个元素了。初始时数组里没有任何有效数据所以top-1最合理。当入栈第一个元素时先执行top使它变成0然后data[0]ele正好落在数组第一个位置。初始化函数长这样void InitStack(SqStack *S) { S-top -1; }注意参数是结构体指针。如果写成void InitStack(SqStack S)那么在函数里修改的只是形参的副本外边的栈还是老样子。这是C语言新手最容易栽的第一个跟头后面第5章我还会专门展开。2.2 入栈和出栈的代码细节入栈操作逻辑上就两步先检查栈满然后top加一把新元素放进top指向的格子。我见过有人写成先赋值再top那会把新元素写到当前top的下一格而栈顶指针还停在旧位置逻辑就乱了。正确顺序是先移动指针再写数据。int Push(SqStack *S, int e) { if (S-top MaxSize - 1) { return 0; // 栈满入栈失败 } S-top; S-data[S-top] e; return 1; }出栈是入栈的逆过程。返回栈顶元素的值然后top减一。但要注意先取得data[top]再top--顺序不能反。另外出栈并不会真的把旧数据擦掉它只是让top往下移动以后入栈时新数据会覆盖旧值。这种“逻辑删除”在很多标准库里普遍存在不必担心。int Pop(SqStack *S, int *e) { if (S-top -1) { return 0; // 栈空 } *e S-data[S-top]; S-top--; return 1; }为什么出栈函数的参数多了一个int *e因为C语言函数只能返回一个值。如果Pop直接返回栈顶元素那当栈空时返回什么返回0会让人分不清是“栈空”还是“栈顶元素本身就是0”。所以我把“操作是否成功”作为返回值把实际弹出的元素通过指针参数带出来。这是C语言里一种约定俗成的错误处理风格。取栈顶元素和出栈的唯一区别就是top不动int GetTop(SqStack *S, int *e) { if (S-top -1) { return 0; } *e S-data[S-top]; return 1; }2.3 共享栈和动态扩容的进阶思路顺序栈最别扭的地方是容量写死。一种常用的优化是“共享栈”用一个数组两个栈分别从数组两端往中间生长。栈A的top从-1开始往右栈B的top从MaxSize开始往左。判满条件是topB - topA 1。这种设计能在内存受限的场景里有效利用空间因为两个栈可以互相借用对方空闲的区域。另一种方案是动态扩容。定义结构体时把data声明成指针初始化时分配sizeof(int) * 初始容量入栈时发现满了就realloc到两倍容量。但要注意realloc可能搬动内存所以数组地址会变任何保存过旧指针的变量都要小心更新。考虑到栈这个结构本身常用于快速增删扩容过于频繁会拖慢性能实际项目里我更建议预估好最大深度直接分配足够空间。3. 链式栈不需要担心容量但要注意别丢指针3.1 节点设计与头插法链式栈把栈元素存在一个个节点里节点之间用指针连接。节点结构和单链表节点完全一样typedef struct StackNode { int data; struct StackNode *next; } StackNode;栈顶指针就是一个StackNode *类型的变量。入栈就是把这个新节点插入到链表头部出栈就是摘除头部节点。为什么一定要用头插法而不是尾插法因为栈的操作只发生在顶端头部就是顶端头插和删头都是O(1)时间。如果用尾插你需要遍历到链表末尾才能插入或者单独维护一个尾指针不但麻烦而且出栈时想删除尾节点单链表根本无法找到前驱还得用双向链表白白增加复杂度。3.2 链式栈的入栈、出栈与销毁先定义一个栈的“壳”结构方便统一管理typedef struct { StackNode *top; // 栈顶指针 int size; // 元素个数方便判空 } LinkStack;初始化时把top置为NULLsize置0。链式栈没有“满”的概念只要还能malloc出新节点就能继续入栈。入栈函数int LinkStack_Push(LinkStack *S, int e) { StackNode *node (StackNode *)malloc(sizeof(StackNode)); if (!node) { return 0; // 分配内存失败 } node-data e; node-next S-top; // 新节点指向原栈顶 S-top node; // 新节点成为栈顶 S-size; return 1; }注意这里两条指针操作的顺序先让新节点的next指到旧栈顶再把top指向新节点。如果先把top改成node你就把旧栈顶地址弄丢了后面链表就断了。这个顺序和单链表头插法完全一致上过链表课的应该很熟。出栈函数核心就是保存旧栈顶节点地址让top指向它的next然后释放旧节点。很多人漏了先保存next这一步int LinkStack_Pop(LinkStack *S, int *e) { if (LinkStack_IsEmpty(S)) { return 0; } StackNode *del S-top; *e del-data; S-top del-next; free(del); S-size--; return 1; }销毁链式栈比出栈要更彻底必须循环释放每个节点。正确写法是每释放一个节点前先保存下一个节点的地址void LinkStack_Destroy(LinkStack *S) { StackNode *p S-top; while (p) { StackNode *next p-next; free(p); p next; } S-top NULL; S-size 0; }我见过不少同学在销毁函数里只free了一次然后直接把top设NULL结果链上剩下的几十个节点全部泄漏。要知道你申请的每一块内存都要还给操作系统不还就是内存泄漏。在嵌入式平台这种泄漏跑一会儿系统就崩了。链式栈判空很简单int LinkStack_IsEmpty(LinkStack *S) { return (S-top NULL) || (S-size 0); }两种判断都可以但最好保持一致。size是冗余信息它的作用是让判空、求元素个数操作不用遍历链表代价只是入栈出栈时多维护一个整型变量很划算。4. 顺序栈和链式栈的选型没有绝对的好坏4.1 时间和空间的定量对比很多教材喜欢用一张表总结两种栈的优缺点但我觉得不够透彻。这里我根据自己的使用经验把对比维度拆得更细对比维度顺序栈链式栈入栈/出栈时间复杂度O(1)且常数极小就是数组赋值和指针加减O(1)但要malloc/free节点常数更大随机访问能力支持可以直接用下标访问data[i]去查中间元素不支持必须从头遍历空间预分配一次性分配MaxSize不管用多少都占着按需分配但每个节点多耗一个指针字段扩容机制预先分配满了要realloc或者不可扩天然无限只要内存够缓存友好性数据集中在一段连续内存CPU缓存命中率高节点零散分布容易缓存未命中内存碎片不产生动态碎片若一次性分配频繁malloc/free会碎片化栈满判断需要isFull只要malloc成功就不满删除/销毁不需要逐个释放数组内存统一释放必须遍历释放所有节点4.2 实际项目里我怎么选选顺序栈还是链式栈不是看谁“高级”而是看你的约束。如果最大元素数量可以提前估计而且操作非常频繁比如在RTOS里给任务栈分配空间那就用顺序栈。任务栈的本质就是一块静态数组考的就是栈顶指针移动连malloc都不想用因为嵌入式环境不允许裸机代码动态分配内存或者说动态分配本身就是禁忌。顺序栈的另一个好处是你可以通过数组下标看到栈底附近的数据这在调试时很有用。如果数据量波动很大比如写一个解析器要处理嵌套层数不确定的表达式那链式栈更安心。它不会因为容量预估不足而报“栈溢出”。每次入栈都临时malloc一个节点虽然多了指针开销和内存分配时间但换来的是“永远不会栈满”的保证。另外当栈里存的是比较大的结构体时链式栈尤其合适入栈时只复制节点指针不复制整个大结构避免数组元素的整体拷贝。用C标准库的人可能已经想过能不能直接用qsort那种回调函数把这套栈做成通用任意类型当然可以。把data从int改成void *或者用柔性数组成员data[]。但那样代码会复杂不少而且容易踩兼容性坑。我的建议是学习阶段老老实实写int版本把逻辑跑通项目里如果实在需要通用栈再考虑宏封装或者void *。别一上来就追求完美栈的核心是逻辑不是花哨。5. C语言实现栈时最常踩的坑5.1 函数形参传值问题这是我在帮人调错时看到过最多的问题。比如有人写void InitStack(SqStack S) { S.top -1; }然后在主函数里InitStack(st);之后判断st.top -1发现是乱值。原因很简单C语言函数的参数是值传递形参S是实参st的拷贝函数里改的是拷贝实参纹丝不动。想要修改外部变量必须传地址。所以要么传指针InitStack(st)然后把参数声明为SqStack *S要么直接返回值比如SqStack InitStack(void)返回一个初始化好的结构体。两种方案都可行但传指针更符合栈操作要有“副作用”的直觉。记住一句话只要你要改变栈里内部的状态参数就该带星号。入栈出栈同理。写void Push(SqStack S, int e)的人他的top永远加不上。遇到这种问题先看函数原型指针写对问题通常立刻消失。5.2 top边界条件的记忆方法顺序栈的边界条件就四个空栈时top-1满栈时topMaxSize-1入栈先top再赋值出栈先取值再top--。这四条看着简单但很多人考试或写代码时就是理不清。我给一个记忆锚点把top想象成一把尺子上的游标尺子从左往右从0到MaxSize-1。游标在-1的位置时尺子上没有任何读数游标越往右元素越多游标到最右端就满了。入栈就是“先把游标往右推一格再把货物放上去”出栈就是“先把货物拿走再把游标往左退一格”。这个画面感比死记硬背强得多。另外有些教材把top初始化为0让top指向“下一个可写入的位置”。那种设计下空栈top0满栈topMaxSize入栈是先赋值再top出栈是先top--再取值。规则和我上面写的是镜像关系。无所谓哪个错但你要全篇统一别混用。我习惯top-1因为它更直观而且多种考试标准答案都用这种。5.3 链式栈的内存泄漏与野指针链式栈的动态内存管理是重灾区。第一类错误是出栈时没有free导致每次Pop都丢失一块内存。代码长这样// 错误示范 int BadPop(LinkStack *S, int *e) { if (!S-top) return 0; *e S-top-data; S-top S-top-next; // 原节点丢失没人释放 return 1; }它在逻辑上“看起来能跑”因为出栈结果数据是对的但就是把节点丢掉了。积少成多系统内存慢慢被啃光。第二类错误是free之后没有把局部指针置NULL然后误以为栈空了去访问悬空指针产生野指针。我建议你写代码时遵守一条规矩每次free完一个节点就把指向它的指针设为NULL。虽然有时候编译器会优化掉这个赋值但它在调试阶段能帮你挡住许多莫名其妙的段错误。销毁链式栈时还要小心如果直接用while(S-top ! NULL) { free(S-top); S-top S-top-next; }那也是错的。因为一旦执行freeS-top指向的内存就已经释放了再访问S-top-next就是典型的use-after-free。必须先拿next再free。这个错误在单链表插入删除章节里反复出现栈也只是换了个壳子。5.4 空栈状态下如何处理顺序栈和链式栈都会遇到空栈时调用Pop或GetTop的情况。最简单的方案是返回一个约定的错误码比如返回0表示失败。但当合法数据本身可能是0时比如你要压入一堆非负整数0是常见取值返回值就有歧义。有两种改进方法。方法一像我在第2章那样使用指针参数带回值函数本身只返回成功/失败。这种方法很干净但调用时多写一个中间变量。方法二用bool加上一个额外的全局错误变量比如int stack_error;。但全局变量在多线程环境会打架不推荐。学数据结构阶段我建议用指针参数方案这能帮你建立“函数返回值是状态数据通过参数输出”的好习惯之后学文件读写、学操作系统API会发现这套思路无处不在。5.5 一个小建议用画图代替背代码最后分享一条我自己的经验。遇到栈的边界条件想不清楚时别急着翻书拿张草稿纸画一个纵向的数组格子把top标在里面然后模拟推入三个元素、弹出一个元素的全过程。你会看到top的移动就是尺子上的游标滑动。链式栈就画成若干方框加箭头入栈时从头部插一个方框出栈时把头部方框摘掉。画完一遍你就不需要死记任何代码函数里的每一句都能从图里推导出来。这个方法帮我教过好多学生效果比对着PPT念幻灯片好太多。