我带人的时候特别喜欢问一个问题用C语言、数组实现一个栈你打算怎么写这个问题表面简单实际上能看出很多基本功——结构体怎么设计、边界条件想不想得全、指针和值传递搞没搞明白、动态内存用得好不好。说实话面试过不少候选人能把栈说清楚、写利索的数据结构这一关基本都稳了。这篇文章就从最经典的“数组实现栈”出发把思路、代码、坑、以及栈最常见的应用场景一次讲透。无论你是刚学数据结构的学生、准备笔试面试的求职者还是写了几年业务代码想回头补基础的开发者这篇都能让你少走弯路。内容参考了大量C语言教学实践代码可以直接拿去跑也可以直接作为数据结构实验报告的核心素材。1. 为什么栈是“最简单也最容易被低估”的数据结构栈的定义背起来很容易只允许在一端插入和删除的线性表先进后出LIFO。但真正理解栈在计算机世界里的地位需要把眼界拉开一点——它远不止是教材里一道练习题。1.1 栈在计算机世界里无处不在函数调用就是最典型的栈。每一次函数调用系统都会把返回地址、参数、局部变量压进调用栈函数返回时再弹出。递归为什么能一层一层正确返回靠的就是这个机制。很多人学递归的时候对“归”这一步百思不得其解其实画一下调用栈的变化就全明白了。表达式求值也是栈。编译原理里处理运算符优先级、把中缀表达式转成后缀表达式核心数据结构都是栈。你在C语言里写一个a b * c编译器底层就是在用栈对运算符做暂存和回溯。还有很多你日常在用的功能本质上都是栈编辑器里的撤销CtrlZ操作浏览器的页面后退函数调用栈与递归括号匹配检查进制转换里的短除法“栈”这个名词同时指代两种东西一是抽象数据结构二是内存布局中的栈区。二者名字同源语义也相关——函数调用栈就是把栈帧压入系统栈再在返回时弹出。热词里常出现“栈和堆”“栈空间”这些搜索词其实就是很多人在函数调用栈、内存布局和数据结构的栈之间产生了混淆。理解了抽象栈你理解内存栈区也会更容易。1.2 为什么先用数组来实现栈很多人会问链式栈和数组栈有什么区别为什么教材几乎都是从数组栈讲起数组在内存中是连续存储的实现栈非常自然用一块连续内存保存元素用一个整型变量标记栈顶位置入栈就是移动栈顶指针并写入出栈就是读取后回移指针。这个模型足够简单简单到可以让你把全部注意力集中在“栈本身的逻辑”上而不是被指针操作分心。另外数组栈的性能通常更优。连续内存对CPU缓存友好访问时不涉及指针跳转也不需要为每个节点单独分配内存。链式栈虽然扩容灵活但每个节点多出一个指针域的开销在数据量大的时候这种浪费会被放大。当然固定容量数组有一个天花板——装满了怎么办这就要聊到动态扩容。第5节会专门讲这个问题先把静态版本写透。2. 数组栈的结构设计与初始化写栈的第一步不是急着写push和pop而是把结构体设计想清楚。这个设计影响后面所有代码的简洁程度和出错概率。2.1 结构体定义三个成员一个都不能少最简单的数组栈结构体长这样#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶元素的下标空栈时为 -1 } SeqStack;data是存放元素的数组top标记栈顶位置。为什么用int *data而不是固定数组这取决于你是否需要动态扩容。上面的写法是示意图实际项目里更常用指针加容量的形式typedef struct { int *data; // 指向堆上分配的连续空间 int capacity; // 当前分配的容量 int top; // 栈顶元素下标空栈时为 -1 } SeqStack;我推荐直接按第二种写。因为一旦要用动态扩容data必须是指针capacity必须被显式记录——否则你没法判断栈什么时候满。固定数组版本虽然写法直观但遇到容量不足只能干瞪眼或者事先定一个很大的MAX_SIZE浪费内存。2.2 top 索引的含义从 -1 还是 0 开始这是新手最容易纠结的问题也是面试里常被追问的细节。有两种主流设计方案一top指向栈顶元素本身空栈时top -1。入栈s-data[s-top] value;出栈*out s-data[s-top--];方案二top指向下一个可用位置空栈时top 0。入栈s-data[s-top] value;出栈*out s-data[--s-top];两种都能工作但我强烈建议用方案一。原因很简单data[s-top]就是栈顶元素读起来直白判空条件s-top -1语义清晰在调试时看着top的值就能直接推算栈里有几个元素top 1个。方案二把top定义为“下一个可用位置”在 peek 时要写成data[s-top - 1]多一次减法也更容易让初学者糊涂。很多经典教材比如严蔚敏老师的《数据结构C语言版》里也采用了类似的“栈顶指针指向栈顶元素”的设计这个约定经过大量验证你按它写就不会错。2.3 初始化和销毁一对对称操作初始化要做两件事分配存储空间把栈置为空。void init(SeqStack *s) { s-capacity 4; // 初始容量后续可扩展 s-data (int *)malloc(sizeof(int) * s-capacity); if (s-data NULL) { s-capacity 0; s-top -1; return; } s-top -1; }注意这里的形参必须是SeqStack *s也就是指针。如果写成void init(SeqStack s)那函数内部修改的是实参的副本调用结束后栈根本不会被初始化。这个坑太经典了没见过几十次也听过几十次第4节会专门展开。对应的销毁函数长这样void destroy(SeqStack *s) { free(s-data); s-data NULL; s-capacity 0; s-top -1; }为什么释放后要把data置为 NULL为了防悬垂指针。释放后的指针指向的内存已经交还系统再访问就是未定义行为。置 NULL 之后如果后续误用s-data至少会在访问时立刻段错误而不是“好像还能用”——问题暴露得越早越容易修。另外free(NULL)是安全的这让我们在重复调用destroy时不会崩。3. 五个核心操作的实现与边界处理结构体和初始化搞定后核心操作就是入栈、出栈、取栈顶、判空、判满。每个操作都必须把边界条件放在第一位。3.1 入栈 push先检查再写入bool push(SeqStack *s, int value) { if (s-top s-capacity - 1) { return false; // 栈满 } s-top; s-data[s-top] value; return true; }我习惯把s-top和s-data[s-top] value写成两行而不是合并成data[s-top]。效果一样但两行写法的可读性更好新手看代码时不会产生歧义。返回值用bool表示成功与否。很多教材里的写法是void push(SeqStack *s, int value)不管栈满不满硬塞。练习可以真实代码不行——栈满时如果继续写top会越界data[top]访问到的就是数组之外的内存这是未定义行为。返回值的存在就是为了让调用方能处理这种异常。3.2 出栈 pop两个返回值的设计bool pop(SeqStack *s, int *out) { if (s-top 0) { return false; // 空栈 } *out s-data[s-top]; s-top--; return true; }这里有个设计问题值得展开为什么出栈不用int pop(SeqStack *s)直接返回栈顶元素原因是无法表达错误。如果空栈时返回 0那恰好栈里存的也是 0 怎么办调用方无法区分“这次出栈成功、弹出的值是0”和“空栈了返回0当占位符”。C语言没有异常机制最普遍的惯例就是用返回值表示操作是否成功用出参指针带回实际数据。如果你确实想写int pop(SeqStack *s)也不是不行但需要额外约定一个特殊值表示失败比如INT_MAX一旦数据里真的存在这个值就穿帮了。所以更稳健的方案还是上面这种“bool成功标识 出参”的写法。出栈后要不要把data[s-top 1]清空不必要因为top已经回移这个位置处于逻辑上的无效区下次入栈写入时自然会被覆盖。但我在调试复杂代码时会临时置 0纯粹是为了让内存里残留的旧数据更容易被肉眼发现发布版本里不会保留这种多余操作。3.3 取栈顶 peek只读不改bool peek(SeqStack *s, int *out) { if (s-top 0) { return false; } *out s-data[s-top]; return true; }peek 与 pop 的唯一区别是top不移动。写算法题的时候s-data[s-top]可以直接用但封装成 peek 函数更规范因为调用方不需要知道结构体内部布局。3.4 判空、判满与大小bool is_empty(SeqStack *s) { return s-top -1; } bool is_full(SeqStack *s) { return s-top s-capacity - 1; } int size(SeqStack *s) { return s-top 1; }这三个函数简单到不能再简单但它们是所有边界检查的基础。判空用top -1判满用top capacity - 1元素个数是top 1。把这些逻辑独立成函数主流程的代码会清晰很多以后如果改成链式栈调用方的代码几乎不用动。3.5 一个完整可运行的最小示例把上面的拼起来就是一个可以直接编译运行的 demo#include stdio.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void init(SeqStack *s) { s-top -1; } bool is_empty(SeqStack *s) { return s-top -1; } bool is_full(SeqStack *s) { return s-top MAX_SIZE - 1; } bool push(SeqStack *s, int value) { if (is_full(s)) { return false; } s-data[s-top] value; return true; } bool pop(SeqStack *s, int *out) { if (is_empty(s)) { return false; } *out s-data[s-top--]; return true; } bool peek(SeqStack *s, int *out) { if (is_empty(s)) { return false; } *out s-data[s-top]; return true; } int main() { SeqStack s; init(s); push(s, 10); push(s, 20); push(s, 30); int v; while (pop(s, v)) { printf(%d , v); } printf(\n); return 0; }这段代码的输出是30 20 10体现的就是后进先出。你把它抄到 IDE 里跑一遍再把pop循环改成 peek 试试能直观感受到两个操作的区别。4. 最容易踩的四个坑一次讲透光把代码写出来不算完把坑踩明白才算真正掌握。下面这几个问题是我在帮人检查代码时遇到频率最高的。4.1 值传递导致“初始化无效”看这段代码void init_bad(SeqStack s) { s.top -1; } int main() { SeqStack s; init_bad(s); // 栈没有被初始化 // 此时 s.top 的值完全不确定 return 0; }问题根源是C语言的按值传递。s传入init_bad时函数收到的是实参的一份拷贝函数内部修改的s.top只影响这份拷贝调用结束后拷贝销毁真正的s纹丝不动。这类 bug 的隐蔽之处在于有的人会在init_bad里打印s.top发现确实是 -1于是确认“初始化成功了”回到 main 里再打印s.top 又变成随机值。这种“函数里正常、调用方没效果”的现象几乎可以立刻锁定为传值问题。排查方法也简单凡是函数内部需要修改结构体内容的一律传指针void init(SeqStack *s)并用s-top访问成员。这个习惯要从学 C 第一天就建立起来。4.2 下标越界data[-1] 与 data[capacity]如果你写bool pop(SeqStack *s, int *out) { *out s-data[s-top--]; // 空栈时 top -1data[-1] 越界 }在空栈状态下调用data[-1]读取的是数组指针之前的内存属于未定义行为。C语言不会帮你检查程序可能“碰巧”还能继续跑也可能产生一个莫名其妙的巨大数值或者直接崩溃。越界访问不一定会立刻报错这才是最危险的——问题被延迟到不可预期的时刻爆发。排查这类问题用 Valgrind 或者 AddressSanitizer 编译运行一下立刻现原形。我的习惯是每个涉及下标的操作先明确当前top的取值范围再访问数组。空栈先判、满栈先判这个习惯能挡住九成以上的越界。4.3 不检查返回值错误一路传播边界检查做了但调用方无视返回值一样会出问题push(s, 1); push(s, 2); push(s, 3); // 假设容量只有2这里返回 false int v; pop(s, v); // 弹出的是3 // 你以为栈里还有1实际已经空了真实程序里栈的容量和操作顺序往往由运行时的数据决定不由程序员的主观意愿决定。读文件、接收网络数据、解析表达式任何一步都可能让栈的状态和你预期的不一致。所以不仅每个操作要返回状态码调用方也必须检查。这是 C 语言里很基本的健壮性要求。4.4 动态扩容中 realloc 的失败处理这是“看着没问题、实际有隐患”的典型s-data (int *)realloc(s-data, sizeof(int) * s-capacity * 2); s-capacity * 2;如果realloc失败它会返回 NULL但原来的那块内存仍然有效。问题在于你把 NULL 赋给了s-data原来的内存地址就丢了既没法继续用也没法free泄漏已经发生。如果是长期运行的服务程序这种泄漏重复几次就可能把内存耗尽。正确写法是引入临时指针int new_cap s-capacity * 2; int *tmp (int *)realloc(s-data, sizeof(int) * new_cap); if (tmp NULL) { return false; // 扩容失败原栈还能继续使用 } s-data tmp; s-capacity new_cap;先用tmp接住新地址确认成功后再覆盖旧指针这样即使失败原有的数据和指针也没有遭到破坏。这个“临时变量过渡”的思路在处理任何可能失败的资源操作时都通用。5. 动态扩容版从固定容量走向可增长栈第2节的固定容量版本适合学习但真实场景里元素数量往往不可预知。读文件、解析字符串、模拟函数调用鬼知道会压进来多少个元素。这时候就需要动态扩容。5.1 什么时候必须用动态栈如果栈的最大深度在编译期就能确定且不大比如只是暂存几个临时值固定数组就够了。但遇到下面这些情况固定容量就不行栈的深度由外部输入决定比如读取的表达式长度未知同一个栈需要在多个场景复用不同场景深度差异巨大内存资源宝贵不想为一个平均使用 10 个元素的栈预留 1000 个元素的空间动态栈的思路也简单容量不够时申请一块更大的空间把旧数据搬运过去释放旧空间。5.2 倍增策略为什么比线性增长好扩容时每次扩大多少我见过有人每次固定加 8 个元素也见过有人每次翻倍。工程实践几乎都推荐倍增。假设初始容量 4倍增第 5 个元素入栈时扩容到 8需要搬运 4 个元素第 9 个元素入栈时扩容到 16需要搬运 8 个元素第 17 个元素入栈时扩容到 32需要搬运 16 个元素搬运成本一共是 4816...等压入 n 个元素后总搬运量大约是 2n均摊到每次 push 上是 O(1)。而如果每次固定加 8搬运量是 81624...总成本量级是 O(n²)均摊下来每次 push 就是 O(n)。数据量一大线性增长的扩容代价非常明显。所以扩容策略的结论很简单用倍增别用等差。5.3 完整实现与测试#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; int capacity; int top; } DynStack; void init(DynStack *s) { s-capacity 4; s-data (int *)malloc(sizeof(int) * s-capacity); if (s-data NULL) { s-capacity 0; s-top -1; return; } s-top -1; } bool is_empty(DynStack *s) { return s-top -1; } bool push(DynStack *s, int value) { if (s-top s-capacity - 1) { int new_cap s-capacity 0 ? 4 : s-capacity * 2; int *tmp (int *)realloc(s-data, sizeof(int) * new_cap); if (tmp NULL) { return false; } s-data tmp; s-capacity new_cap; } s-data[s-top] value; return true; } bool pop(DynStack *s, int *out) { if (s-top 0) { return false; } *out s-data[s-top--]; return true; } bool peek(DynStack *s, int *out) { if (s-top 0) { return false; } *out s-data[s-top]; return true; } void destroy(DynStack *s) { free(s-data); s-data NULL; s-capacity 0; s-top -1; } int main() { DynStack s; init(s); for (int i 0; i 100; i) { if (!push(s, i)) { printf(push %d failed\n, i); break; } } int v; while (pop(s, v)) { printf(%d , v); } printf(\n); destroy(s); return 0; }注意push函数里的边界判断当capacity 0初始化失败过时先把容量重置为 4 再尝试。这个细节是对异常路径的兜底虽然不常见但一旦初始化失败后续至少不会在容量 0 的情况下做乘法溢出。运行这段代码会先把 0 到 99 压栈然后从 99 开始倒序输出。你也可以在push的扩容分支里加一行printf(expand to %d\n, new_cap);观察容量是怎么从 4 变 8、变 16、一路涨上去的。这种亲眼看到扩容发生的感觉比单看概念直观得多。6. 栈的应用实战括号匹配与表达式求值栈的价值不在栈本身而在它能解决的问题。这一节用两个经典场景说明栈怎么在实际的代码里发光发热。6.1 括号匹配一道面试题的完整解法问题给定一个只含()、[]、{}的字符串判断括号是否成对且嵌套正确。思路非常自然——碰到左括号就入栈碰到右括号就弹出栈顶的左括号检查类型是否匹配。如果中途发现栈空右括号多余或者最终栈不为空左括号多余就判定为不匹配。bool is_match(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool check_brackets(const char *str) { SeqStack s; init(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 }) { char top; if (!pop(s, top)) { return false; // 遇到右括号但栈空说明右括号多余 } if (!is_match(top, c)) { return false; // 括号类型不匹配 } } } return is_empty(s); }测试几组数据验证一下输入结果原因()true正常匹配()[]{}true连续多组匹配([{}])true嵌套匹配([)]false类型交叉栈顶是(遇到的是)才对却来了]([false最终栈里还剩左括号这个逻辑是递归下降解析器、JSON 校验、配置文件合法性检查等场景的雏形。理解了它编译器前端的一部分神秘面纱就揭开了。6.2 用栈把中缀表达式转后缀表达式中缀表达式就是我们平时写的1 2 * 3后缀表达式是1 2 3 * 。计算机计算后缀表达式容易但人写的是中缀。转换过程同样依赖栈遇到数字直接输出。遇到运算符如果栈为空或者当前运算符优先级高于栈顶入栈否则把栈顶弹出输出直到栈顶优先级低于当前运算符再入栈。遇到左括号入栈遇到右括号弹出直到左括号。结束后把栈里剩余运算符全部弹出。核心思想是运算符需要“等一等”再输出等什么呢等优先级更高的运算符先处理完。这种“暂存-回溯”的节奏和栈的后进先出特性完美契合。这部分代码不难建议你基于第3节的 SeqStack 自己推一遍 [3,1,4,2] 这种复杂点的表达式转换过程对栈的理解会深很多。6.3 函数调用栈数组栈的“原型”栈在系统层面最经典的存在就是函数调用栈。每次函数调用系统在栈区分配一块栈帧记录返回地址、参数、局部变量、保存的寄存器函数返回时栈帧被弹出执行流回到调用点。在进程的内存布局里函数调用栈的栈区通常在用户空间的高地址段向下生长堆区向上生长。局部变量随函数调用自动分配、自动释放生命周期严格嵌套——这正是 LIFO 的体现。所以数据结构栈不只是“一种题目”它就是真实计算机运行机制的抽象。顺带回答一个搜索热词里常见的问题为什么在 C/C 里声明一个特别大的局部数组会段错误而 malloc 一个大数组不会因为局部数组分配在栈区系统栈区大小是有限的Linux 默认通常 8MBmalloc 分配在堆区容量由操作系统根据内存资源动态管理。理解了函数调用栈这类问题自然就通了。还有一个很有意思的衍生场景小程序页面栈。小程序的页面跳转也是用栈管理的页面栈默认上限是 10 层。超过之后无法继续 navigateTo就是因为页面只压栈不出栈。解决办法就是及时用 redirectTo 或 navigateBack 让旧页面出栈而不是无限压栈。你看栈的思想到处都是。7. 数组栈 vs 链式栈怎么选很多教材把数组栈和链式栈并列讲但实际工程里两者的地位并不对等。这一节把各自的优劣摊开来比一比方便你做选择。7.1 性能与空间对比维度数组栈链式栈入栈出栈复杂度O(1)O(1)空间占用只需要存储元素无额外指针开销每个节点额外一个 next 指针64 位系统为 8 字节内存连续性连续缓存友好节点分散缓存命中率低扩容需要 realloc 并搬运数据均摊 O(1)无容量上限每次 malloc 一个节点实现复杂度低结构清晰需要维护指针链表更容易出指针错误潜在风险固定容量可能溢出动态扩容可能失败高频 malloc/free 可能导致内存碎片从表里基本能得出一个结论对于绝大多数业务场景和算法题数组栈都更合适。链式栈的优势主要在“完全没有容量上限”以及“扩容不需要搬运已有数据”但在元素数量不大时这个优势基本体现不出来。7.2 什么时候才真正需要链式栈我自己的经验是需要链式栈的场景通常具备这几个特征之一元素数量完全不可预估且可能非常大数组扩容的搬运成本不可接受栈的使用方式是频繁创建、销毁而不是长期存在此时动态扩容就没有意义你在实现一个需要支持随机删除或合并操作的复杂数据结构链式结构更方便做题和日常开发先用数组栈就够了。真的遇到上述瓶颈再切链式栈不迟。很多人在入门阶段纠结“我该用数组版还是链表版”其实应该先把自己需要解决的问题跑通再去优化数据结构选型。数据结构是工具不是目的。就我个人实际编码的体会来说数组栈还有一个容易被忽略的好处调试体验好。因为内存连续在调试器里看data数组所有元素一目了然链式栈要看一个节点得先找到链表头然后在指针之间跳来跳去非常别扭。团队里带新人的时候我也总是让他们先把数组栈写熟、写对再考虑链式版本前者能帮他们把“栈的逻辑”和“C 语言的细节”彻底分开后者则是把两件事揉在一起考验综合能力。如果你正在准备数据结构实验报告上面第 3 节的代码和第 4 节的踩坑清单可以直接用。如果你在准备面试把第 6 节的括号匹配手写一遍再把栈实现改成动态扩容基本就稳了。希望这篇能把数组栈这个基础中的基础讲透让你在遇到任何需要栈的场景时都能毫不犹豫地把它写对、写好。
C语言数组实现栈：从结构设计到动态扩容全解析
我带人的时候特别喜欢问一个问题用C语言、数组实现一个栈你打算怎么写这个问题表面简单实际上能看出很多基本功——结构体怎么设计、边界条件想不想得全、指针和值传递搞没搞明白、动态内存用得好不好。说实话面试过不少候选人能把栈说清楚、写利索的数据结构这一关基本都稳了。这篇文章就从最经典的“数组实现栈”出发把思路、代码、坑、以及栈最常见的应用场景一次讲透。无论你是刚学数据结构的学生、准备笔试面试的求职者还是写了几年业务代码想回头补基础的开发者这篇都能让你少走弯路。内容参考了大量C语言教学实践代码可以直接拿去跑也可以直接作为数据结构实验报告的核心素材。1. 为什么栈是“最简单也最容易被低估”的数据结构栈的定义背起来很容易只允许在一端插入和删除的线性表先进后出LIFO。但真正理解栈在计算机世界里的地位需要把眼界拉开一点——它远不止是教材里一道练习题。1.1 栈在计算机世界里无处不在函数调用就是最典型的栈。每一次函数调用系统都会把返回地址、参数、局部变量压进调用栈函数返回时再弹出。递归为什么能一层一层正确返回靠的就是这个机制。很多人学递归的时候对“归”这一步百思不得其解其实画一下调用栈的变化就全明白了。表达式求值也是栈。编译原理里处理运算符优先级、把中缀表达式转成后缀表达式核心数据结构都是栈。你在C语言里写一个a b * c编译器底层就是在用栈对运算符做暂存和回溯。还有很多你日常在用的功能本质上都是栈编辑器里的撤销CtrlZ操作浏览器的页面后退函数调用栈与递归括号匹配检查进制转换里的短除法“栈”这个名词同时指代两种东西一是抽象数据结构二是内存布局中的栈区。二者名字同源语义也相关——函数调用栈就是把栈帧压入系统栈再在返回时弹出。热词里常出现“栈和堆”“栈空间”这些搜索词其实就是很多人在函数调用栈、内存布局和数据结构的栈之间产生了混淆。理解了抽象栈你理解内存栈区也会更容易。1.2 为什么先用数组来实现栈很多人会问链式栈和数组栈有什么区别为什么教材几乎都是从数组栈讲起数组在内存中是连续存储的实现栈非常自然用一块连续内存保存元素用一个整型变量标记栈顶位置入栈就是移动栈顶指针并写入出栈就是读取后回移指针。这个模型足够简单简单到可以让你把全部注意力集中在“栈本身的逻辑”上而不是被指针操作分心。另外数组栈的性能通常更优。连续内存对CPU缓存友好访问时不涉及指针跳转也不需要为每个节点单独分配内存。链式栈虽然扩容灵活但每个节点多出一个指针域的开销在数据量大的时候这种浪费会被放大。当然固定容量数组有一个天花板——装满了怎么办这就要聊到动态扩容。第5节会专门讲这个问题先把静态版本写透。2. 数组栈的结构设计与初始化写栈的第一步不是急着写push和pop而是把结构体设计想清楚。这个设计影响后面所有代码的简洁程度和出错概率。2.1 结构体定义三个成员一个都不能少最简单的数组栈结构体长这样#include stdio.h #include stdlib.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; // 栈顶元素的下标空栈时为 -1 } SeqStack;data是存放元素的数组top标记栈顶位置。为什么用int *data而不是固定数组这取决于你是否需要动态扩容。上面的写法是示意图实际项目里更常用指针加容量的形式typedef struct { int *data; // 指向堆上分配的连续空间 int capacity; // 当前分配的容量 int top; // 栈顶元素下标空栈时为 -1 } SeqStack;我推荐直接按第二种写。因为一旦要用动态扩容data必须是指针capacity必须被显式记录——否则你没法判断栈什么时候满。固定数组版本虽然写法直观但遇到容量不足只能干瞪眼或者事先定一个很大的MAX_SIZE浪费内存。2.2 top 索引的含义从 -1 还是 0 开始这是新手最容易纠结的问题也是面试里常被追问的细节。有两种主流设计方案一top指向栈顶元素本身空栈时top -1。入栈s-data[s-top] value;出栈*out s-data[s-top--];方案二top指向下一个可用位置空栈时top 0。入栈s-data[s-top] value;出栈*out s-data[--s-top];两种都能工作但我强烈建议用方案一。原因很简单data[s-top]就是栈顶元素读起来直白判空条件s-top -1语义清晰在调试时看着top的值就能直接推算栈里有几个元素top 1个。方案二把top定义为“下一个可用位置”在 peek 时要写成data[s-top - 1]多一次减法也更容易让初学者糊涂。很多经典教材比如严蔚敏老师的《数据结构C语言版》里也采用了类似的“栈顶指针指向栈顶元素”的设计这个约定经过大量验证你按它写就不会错。2.3 初始化和销毁一对对称操作初始化要做两件事分配存储空间把栈置为空。void init(SeqStack *s) { s-capacity 4; // 初始容量后续可扩展 s-data (int *)malloc(sizeof(int) * s-capacity); if (s-data NULL) { s-capacity 0; s-top -1; return; } s-top -1; }注意这里的形参必须是SeqStack *s也就是指针。如果写成void init(SeqStack s)那函数内部修改的是实参的副本调用结束后栈根本不会被初始化。这个坑太经典了没见过几十次也听过几十次第4节会专门展开。对应的销毁函数长这样void destroy(SeqStack *s) { free(s-data); s-data NULL; s-capacity 0; s-top -1; }为什么释放后要把data置为 NULL为了防悬垂指针。释放后的指针指向的内存已经交还系统再访问就是未定义行为。置 NULL 之后如果后续误用s-data至少会在访问时立刻段错误而不是“好像还能用”——问题暴露得越早越容易修。另外free(NULL)是安全的这让我们在重复调用destroy时不会崩。3. 五个核心操作的实现与边界处理结构体和初始化搞定后核心操作就是入栈、出栈、取栈顶、判空、判满。每个操作都必须把边界条件放在第一位。3.1 入栈 push先检查再写入bool push(SeqStack *s, int value) { if (s-top s-capacity - 1) { return false; // 栈满 } s-top; s-data[s-top] value; return true; }我习惯把s-top和s-data[s-top] value写成两行而不是合并成data[s-top]。效果一样但两行写法的可读性更好新手看代码时不会产生歧义。返回值用bool表示成功与否。很多教材里的写法是void push(SeqStack *s, int value)不管栈满不满硬塞。练习可以真实代码不行——栈满时如果继续写top会越界data[top]访问到的就是数组之外的内存这是未定义行为。返回值的存在就是为了让调用方能处理这种异常。3.2 出栈 pop两个返回值的设计bool pop(SeqStack *s, int *out) { if (s-top 0) { return false; // 空栈 } *out s-data[s-top]; s-top--; return true; }这里有个设计问题值得展开为什么出栈不用int pop(SeqStack *s)直接返回栈顶元素原因是无法表达错误。如果空栈时返回 0那恰好栈里存的也是 0 怎么办调用方无法区分“这次出栈成功、弹出的值是0”和“空栈了返回0当占位符”。C语言没有异常机制最普遍的惯例就是用返回值表示操作是否成功用出参指针带回实际数据。如果你确实想写int pop(SeqStack *s)也不是不行但需要额外约定一个特殊值表示失败比如INT_MAX一旦数据里真的存在这个值就穿帮了。所以更稳健的方案还是上面这种“bool成功标识 出参”的写法。出栈后要不要把data[s-top 1]清空不必要因为top已经回移这个位置处于逻辑上的无效区下次入栈写入时自然会被覆盖。但我在调试复杂代码时会临时置 0纯粹是为了让内存里残留的旧数据更容易被肉眼发现发布版本里不会保留这种多余操作。3.3 取栈顶 peek只读不改bool peek(SeqStack *s, int *out) { if (s-top 0) { return false; } *out s-data[s-top]; return true; }peek 与 pop 的唯一区别是top不移动。写算法题的时候s-data[s-top]可以直接用但封装成 peek 函数更规范因为调用方不需要知道结构体内部布局。3.4 判空、判满与大小bool is_empty(SeqStack *s) { return s-top -1; } bool is_full(SeqStack *s) { return s-top s-capacity - 1; } int size(SeqStack *s) { return s-top 1; }这三个函数简单到不能再简单但它们是所有边界检查的基础。判空用top -1判满用top capacity - 1元素个数是top 1。把这些逻辑独立成函数主流程的代码会清晰很多以后如果改成链式栈调用方的代码几乎不用动。3.5 一个完整可运行的最小示例把上面的拼起来就是一个可以直接编译运行的 demo#include stdio.h #include stdbool.h #define MAX_SIZE 100 typedef struct { int data[MAX_SIZE]; int top; } SeqStack; void init(SeqStack *s) { s-top -1; } bool is_empty(SeqStack *s) { return s-top -1; } bool is_full(SeqStack *s) { return s-top MAX_SIZE - 1; } bool push(SeqStack *s, int value) { if (is_full(s)) { return false; } s-data[s-top] value; return true; } bool pop(SeqStack *s, int *out) { if (is_empty(s)) { return false; } *out s-data[s-top--]; return true; } bool peek(SeqStack *s, int *out) { if (is_empty(s)) { return false; } *out s-data[s-top]; return true; } int main() { SeqStack s; init(s); push(s, 10); push(s, 20); push(s, 30); int v; while (pop(s, v)) { printf(%d , v); } printf(\n); return 0; }这段代码的输出是30 20 10体现的就是后进先出。你把它抄到 IDE 里跑一遍再把pop循环改成 peek 试试能直观感受到两个操作的区别。4. 最容易踩的四个坑一次讲透光把代码写出来不算完把坑踩明白才算真正掌握。下面这几个问题是我在帮人检查代码时遇到频率最高的。4.1 值传递导致“初始化无效”看这段代码void init_bad(SeqStack s) { s.top -1; } int main() { SeqStack s; init_bad(s); // 栈没有被初始化 // 此时 s.top 的值完全不确定 return 0; }问题根源是C语言的按值传递。s传入init_bad时函数收到的是实参的一份拷贝函数内部修改的s.top只影响这份拷贝调用结束后拷贝销毁真正的s纹丝不动。这类 bug 的隐蔽之处在于有的人会在init_bad里打印s.top发现确实是 -1于是确认“初始化成功了”回到 main 里再打印s.top 又变成随机值。这种“函数里正常、调用方没效果”的现象几乎可以立刻锁定为传值问题。排查方法也简单凡是函数内部需要修改结构体内容的一律传指针void init(SeqStack *s)并用s-top访问成员。这个习惯要从学 C 第一天就建立起来。4.2 下标越界data[-1] 与 data[capacity]如果你写bool pop(SeqStack *s, int *out) { *out s-data[s-top--]; // 空栈时 top -1data[-1] 越界 }在空栈状态下调用data[-1]读取的是数组指针之前的内存属于未定义行为。C语言不会帮你检查程序可能“碰巧”还能继续跑也可能产生一个莫名其妙的巨大数值或者直接崩溃。越界访问不一定会立刻报错这才是最危险的——问题被延迟到不可预期的时刻爆发。排查这类问题用 Valgrind 或者 AddressSanitizer 编译运行一下立刻现原形。我的习惯是每个涉及下标的操作先明确当前top的取值范围再访问数组。空栈先判、满栈先判这个习惯能挡住九成以上的越界。4.3 不检查返回值错误一路传播边界检查做了但调用方无视返回值一样会出问题push(s, 1); push(s, 2); push(s, 3); // 假设容量只有2这里返回 false int v; pop(s, v); // 弹出的是3 // 你以为栈里还有1实际已经空了真实程序里栈的容量和操作顺序往往由运行时的数据决定不由程序员的主观意愿决定。读文件、接收网络数据、解析表达式任何一步都可能让栈的状态和你预期的不一致。所以不仅每个操作要返回状态码调用方也必须检查。这是 C 语言里很基本的健壮性要求。4.4 动态扩容中 realloc 的失败处理这是“看着没问题、实际有隐患”的典型s-data (int *)realloc(s-data, sizeof(int) * s-capacity * 2); s-capacity * 2;如果realloc失败它会返回 NULL但原来的那块内存仍然有效。问题在于你把 NULL 赋给了s-data原来的内存地址就丢了既没法继续用也没法free泄漏已经发生。如果是长期运行的服务程序这种泄漏重复几次就可能把内存耗尽。正确写法是引入临时指针int new_cap s-capacity * 2; int *tmp (int *)realloc(s-data, sizeof(int) * new_cap); if (tmp NULL) { return false; // 扩容失败原栈还能继续使用 } s-data tmp; s-capacity new_cap;先用tmp接住新地址确认成功后再覆盖旧指针这样即使失败原有的数据和指针也没有遭到破坏。这个“临时变量过渡”的思路在处理任何可能失败的资源操作时都通用。5. 动态扩容版从固定容量走向可增长栈第2节的固定容量版本适合学习但真实场景里元素数量往往不可预知。读文件、解析字符串、模拟函数调用鬼知道会压进来多少个元素。这时候就需要动态扩容。5.1 什么时候必须用动态栈如果栈的最大深度在编译期就能确定且不大比如只是暂存几个临时值固定数组就够了。但遇到下面这些情况固定容量就不行栈的深度由外部输入决定比如读取的表达式长度未知同一个栈需要在多个场景复用不同场景深度差异巨大内存资源宝贵不想为一个平均使用 10 个元素的栈预留 1000 个元素的空间动态栈的思路也简单容量不够时申请一块更大的空间把旧数据搬运过去释放旧空间。5.2 倍增策略为什么比线性增长好扩容时每次扩大多少我见过有人每次固定加 8 个元素也见过有人每次翻倍。工程实践几乎都推荐倍增。假设初始容量 4倍增第 5 个元素入栈时扩容到 8需要搬运 4 个元素第 9 个元素入栈时扩容到 16需要搬运 8 个元素第 17 个元素入栈时扩容到 32需要搬运 16 个元素搬运成本一共是 4816...等压入 n 个元素后总搬运量大约是 2n均摊到每次 push 上是 O(1)。而如果每次固定加 8搬运量是 81624...总成本量级是 O(n²)均摊下来每次 push 就是 O(n)。数据量一大线性增长的扩容代价非常明显。所以扩容策略的结论很简单用倍增别用等差。5.3 完整实现与测试#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; int capacity; int top; } DynStack; void init(DynStack *s) { s-capacity 4; s-data (int *)malloc(sizeof(int) * s-capacity); if (s-data NULL) { s-capacity 0; s-top -1; return; } s-top -1; } bool is_empty(DynStack *s) { return s-top -1; } bool push(DynStack *s, int value) { if (s-top s-capacity - 1) { int new_cap s-capacity 0 ? 4 : s-capacity * 2; int *tmp (int *)realloc(s-data, sizeof(int) * new_cap); if (tmp NULL) { return false; } s-data tmp; s-capacity new_cap; } s-data[s-top] value; return true; } bool pop(DynStack *s, int *out) { if (s-top 0) { return false; } *out s-data[s-top--]; return true; } bool peek(DynStack *s, int *out) { if (s-top 0) { return false; } *out s-data[s-top]; return true; } void destroy(DynStack *s) { free(s-data); s-data NULL; s-capacity 0; s-top -1; } int main() { DynStack s; init(s); for (int i 0; i 100; i) { if (!push(s, i)) { printf(push %d failed\n, i); break; } } int v; while (pop(s, v)) { printf(%d , v); } printf(\n); destroy(s); return 0; }注意push函数里的边界判断当capacity 0初始化失败过时先把容量重置为 4 再尝试。这个细节是对异常路径的兜底虽然不常见但一旦初始化失败后续至少不会在容量 0 的情况下做乘法溢出。运行这段代码会先把 0 到 99 压栈然后从 99 开始倒序输出。你也可以在push的扩容分支里加一行printf(expand to %d\n, new_cap);观察容量是怎么从 4 变 8、变 16、一路涨上去的。这种亲眼看到扩容发生的感觉比单看概念直观得多。6. 栈的应用实战括号匹配与表达式求值栈的价值不在栈本身而在它能解决的问题。这一节用两个经典场景说明栈怎么在实际的代码里发光发热。6.1 括号匹配一道面试题的完整解法问题给定一个只含()、[]、{}的字符串判断括号是否成对且嵌套正确。思路非常自然——碰到左括号就入栈碰到右括号就弹出栈顶的左括号检查类型是否匹配。如果中途发现栈空右括号多余或者最终栈不为空左括号多余就判定为不匹配。bool is_match(char left, char right) { return (left ( right )) || (left [ right ]) || (left { right }); } bool check_brackets(const char *str) { SeqStack s; init(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 }) { char top; if (!pop(s, top)) { return false; // 遇到右括号但栈空说明右括号多余 } if (!is_match(top, c)) { return false; // 括号类型不匹配 } } } return is_empty(s); }测试几组数据验证一下输入结果原因()true正常匹配()[]{}true连续多组匹配([{}])true嵌套匹配([)]false类型交叉栈顶是(遇到的是)才对却来了]([false最终栈里还剩左括号这个逻辑是递归下降解析器、JSON 校验、配置文件合法性检查等场景的雏形。理解了它编译器前端的一部分神秘面纱就揭开了。6.2 用栈把中缀表达式转后缀表达式中缀表达式就是我们平时写的1 2 * 3后缀表达式是1 2 3 * 。计算机计算后缀表达式容易但人写的是中缀。转换过程同样依赖栈遇到数字直接输出。遇到运算符如果栈为空或者当前运算符优先级高于栈顶入栈否则把栈顶弹出输出直到栈顶优先级低于当前运算符再入栈。遇到左括号入栈遇到右括号弹出直到左括号。结束后把栈里剩余运算符全部弹出。核心思想是运算符需要“等一等”再输出等什么呢等优先级更高的运算符先处理完。这种“暂存-回溯”的节奏和栈的后进先出特性完美契合。这部分代码不难建议你基于第3节的 SeqStack 自己推一遍 [3,1,4,2] 这种复杂点的表达式转换过程对栈的理解会深很多。6.3 函数调用栈数组栈的“原型”栈在系统层面最经典的存在就是函数调用栈。每次函数调用系统在栈区分配一块栈帧记录返回地址、参数、局部变量、保存的寄存器函数返回时栈帧被弹出执行流回到调用点。在进程的内存布局里函数调用栈的栈区通常在用户空间的高地址段向下生长堆区向上生长。局部变量随函数调用自动分配、自动释放生命周期严格嵌套——这正是 LIFO 的体现。所以数据结构栈不只是“一种题目”它就是真实计算机运行机制的抽象。顺带回答一个搜索热词里常见的问题为什么在 C/C 里声明一个特别大的局部数组会段错误而 malloc 一个大数组不会因为局部数组分配在栈区系统栈区大小是有限的Linux 默认通常 8MBmalloc 分配在堆区容量由操作系统根据内存资源动态管理。理解了函数调用栈这类问题自然就通了。还有一个很有意思的衍生场景小程序页面栈。小程序的页面跳转也是用栈管理的页面栈默认上限是 10 层。超过之后无法继续 navigateTo就是因为页面只压栈不出栈。解决办法就是及时用 redirectTo 或 navigateBack 让旧页面出栈而不是无限压栈。你看栈的思想到处都是。7. 数组栈 vs 链式栈怎么选很多教材把数组栈和链式栈并列讲但实际工程里两者的地位并不对等。这一节把各自的优劣摊开来比一比方便你做选择。7.1 性能与空间对比维度数组栈链式栈入栈出栈复杂度O(1)O(1)空间占用只需要存储元素无额外指针开销每个节点额外一个 next 指针64 位系统为 8 字节内存连续性连续缓存友好节点分散缓存命中率低扩容需要 realloc 并搬运数据均摊 O(1)无容量上限每次 malloc 一个节点实现复杂度低结构清晰需要维护指针链表更容易出指针错误潜在风险固定容量可能溢出动态扩容可能失败高频 malloc/free 可能导致内存碎片从表里基本能得出一个结论对于绝大多数业务场景和算法题数组栈都更合适。链式栈的优势主要在“完全没有容量上限”以及“扩容不需要搬运已有数据”但在元素数量不大时这个优势基本体现不出来。7.2 什么时候才真正需要链式栈我自己的经验是需要链式栈的场景通常具备这几个特征之一元素数量完全不可预估且可能非常大数组扩容的搬运成本不可接受栈的使用方式是频繁创建、销毁而不是长期存在此时动态扩容就没有意义你在实现一个需要支持随机删除或合并操作的复杂数据结构链式结构更方便做题和日常开发先用数组栈就够了。真的遇到上述瓶颈再切链式栈不迟。很多人在入门阶段纠结“我该用数组版还是链表版”其实应该先把自己需要解决的问题跑通再去优化数据结构选型。数据结构是工具不是目的。就我个人实际编码的体会来说数组栈还有一个容易被忽略的好处调试体验好。因为内存连续在调试器里看data数组所有元素一目了然链式栈要看一个节点得先找到链表头然后在指针之间跳来跳去非常别扭。团队里带新人的时候我也总是让他们先把数组栈写熟、写对再考虑链式版本前者能帮他们把“栈的逻辑”和“C 语言的细节”彻底分开后者则是把两件事揉在一起考验综合能力。如果你正在准备数据结构实验报告上面第 3 节的代码和第 4 节的踩坑清单可以直接用。如果你在准备面试把第 6 节的括号匹配手写一遍再把栈实现改成动态扩容基本就稳了。希望这篇能把数组栈这个基础中的基础讲透让你在遇到任何需要栈的场景时都能毫不犹豫地把它写对、写好。
