不瞒你说我最早写栈是在准备校招刷题的时候。当时的想法特别简单栈嘛后进先出push 和 pop 两个操作十分钟就能写完。直到有一次面试官追问“你的栈扩容到多少扩容失败怎么办返回 -1 表示空栈那栈里面存 -1 这个合法值怎么办”我当场被问住了。从那时起我才意识到一个基本的整形栈——只装 int 类型数据的栈——想实现得严谨需要思考的东西远比教材上的三行伪代码多。本文就围绕整形栈把数组版、链式版、边界条件、实战应用整个链条完整过一遍希望给正在学数据结构、或者想补基础的朋友一点参考。1. 为什么先写“整形栈”而不是直接上泛型栈1.1 栈到底在解决什么问题栈的本质是一种操作受限的线性表所有的插入和删除都只能在一端进行也就是栈顶。日常里最贴切的类比是叠盘子你最后放上去的盘子一定最先被拿走。CrtlZ 撤销操作、浏览器后退按钮、编辑器里的括号匹配背后全是这门朴素的逻辑。问题在于数组和链表这两门基础数据结构给我们的直觉是“随意存取”。我可以在数组任意位置读一个元素也可以在链表中随意插入一个节点。但真实场景里很多信息天然就是逆序产生的函数一层层调用进去返回的时候必须一层层倒着出来表达式里先读到数字后遇到运算符计算顺序却要从里往外推。这时候强行用数组下标去记录“谁先谁后”反而别扭。栈把这个逆序关系收敛成了接口——你不需要关心数据躺在哪个位置只需要记住栈顶是谁。如果让我用一句话总结栈的价值那就是它把“最近的优先处理”这个规则固化成了数据结构让调用方不需要再手工维护顺序逻辑。1.2 为什么偏偏是整型市面上很多教程一上来就写StackT或者StackE用泛型、模板、void*看起来高级但对初学者其实是个灾难。以 C 语言为例如果想写一个通用栈就得用void*存指针处理类型转换、内存所有权、拷贝语义这些琐碎细节会把你从数据结构的核心逻辑里拽走。C 的模板栈稍好但如果没掌握 RAII 和移动语义内存泄漏照样找上门。而整形栈把所有复杂度集中到了容器本身。int 元素没有析构函数不需要深拷贝入栈出栈就是四字节数据搬家。这样你能完整地体验容量规划、扩容策略、内存分配失败、边界条件检测而不被语言特性分心。再说一个容易被忽略的事实真实算法题里栈里装的东西绝大多数时候就是整数。DFS 里记录访问顺序存的是节点编号单调栈里存的是数组下标括号匹配里存的是左括号的索引位置。所以“整形栈”并不是一个玩具模型它是算法题里出现频率最高的栈形态。1.3 在动手之前先摸清 int 的脾气既然是整形栈就得先确认 int 的边界行为。int 在 32 位系统下能表示的最小值是 -2147483648最大值是 2147483647。这意味着两件事其一-1 完全可能是一个合法数据。很多初学实现喜欢用“返回 -1 表示空栈”这在整形栈里是不可接受的——因为用户真的可能 push 一个 -1。我见过有同学把“输入范围不含负数”当作借口结果上线后被一条合法的负数数据打出 bug。其二栈的容量本身也可能逼近 int 上限。一个数组栈里存 20 亿个 int算下来需要 8GB 内存一般机器早就扛不住了所以容量溢出在实践中倒不是首要问题。但写代码时要养成好习惯扩容倍数和索引类型尽量不要用裸 int该用 size_t 的地方就用 size_t别给自己留定时炸弹。2. 顺序栈数组版整形栈的完整落地2.1 接口设计先把约定定清楚写任何数据结构第一步永远是定义 API 的边界。我最终敲定的操作集合如下操作函数签名语义初始化void stack_init(IntStack *s)将栈置为空状态入栈bool stack_push(IntStack *s, int value)成功返回 true失败返回 false出栈bool stack_pop(IntStack *s, int *out)空栈返回 false否则取出栈顶元素到 out查看栈顶bool stack_top(const IntStack *s, int *out)空栈返回 false否则把栈顶值写入 out判空bool stack_empty(const IntStack *s)栈空返回 true元素数量int stack_size(const IntStack *s)返回当前元素个数销毁void stack_destroy(IntStack *s)释放全部内部资源这里最关键的决策是pop和top都采用bool 返回值 出参的模式。为什么不直接返回 int因为空栈时候选错误码不好找-1 可能是合法数据0 也可能是合法数据。与其纠结错误码不如用一个布尔值表达“操作是否成功”然后通过指针把真正的数据带出来。2.2 完整代码实现#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; size_t capacity; size_t size; } IntStack; void stack_init(IntStack *s) { s-data NULL; s-capacity 0; s-size 0; } bool stack_push(IntStack *s, int value) { if (s-size s-capacity) { size_t new_cap s-capacity 0 ? 8 : s-capacity * 2; int *tmp (int *)realloc(s-data, new_cap * sizeof(int)); if (tmp NULL) { return false; // 扩容失败原栈保持不变 } s-data tmp; s-capacity new_cap; } s-data[s-size] value; return true; } bool stack_pop(IntStack *s, int *out) { if (s-size 0) { return false; } *out s-data[--s-size]; return true; } bool stack_top(const IntStack *s, int *out) { if (s-size 0) { return false; } *out s-data[s-size - 1]; return true; } bool stack_empty(const IntStack *s) { return s-size 0; } size_t stack_size(const IntStack *s) { return s-size; } void stack_destroy(IntStack *s) { free(s-data); s-data NULL; s-capacity 0; s-size 0; }2.3 扩容机制为什么是 2 倍而不是加 8数组栈的最大痛点就是容量不够时怎么办。两种常见策略固定增量扩容每次加 N 个和倍数扩容每次翻倍。我习惯用 2 倍扩张原因很简单均摊成本低。假设初始容量为 8每次翻倍。当栈从容量 8 涨到容量 16 时需要拷贝 8 个元素从 16 涨到 32 时拷贝 16 个以此类推。总共插入 n 个元素扩容时拷贝的总次数大约是 n n/2 n/4 ... 2n均摊到每次 push 就是 O(1)。而固定增量扩容每次扩容都要拷贝当前所有元素n 次插入下来总拷贝次数是 O(n²)数据量一大立刻露馅。另外注意 realloc 的正确打开方式。错误示范s-data (int *)realloc(s-data, new_cap * sizeof(int));如果 realloc 失败它返回 NULL但原来的内存还活着。你直接把这个 NULL 赋给 s-data原来的指针就丢了内存泄漏栈也彻底崩坏。正确写法是先用临时变量接收返回值判断非 NULL 之后再赋值给 s-data。这点在真实项目里特别重要因为栈满扩容时通常恰好是系统内存压力较大的时候。2.4 别小看容量字段的类型上面代码里我用size_t而不是int来存 capacity 和 size。如果偷懒用 int就可能出现一种诡异场景栈里已经存了超过 2^31-1 个元素size 溢出变成负数判空逻辑立刻失效。虽然现实中很难真的塞进 20 亿个 int但用 size_t 只是一行改动没必要留这个隐患。还有一个细节当 capacity 已经很大时capacity * 2可能连 size_t 都溢出。严谨的写法是在扩容前判断new_cap SIZE_MAX / sizeof(int)这类边界不过实际工程里极少走到那个量级。知道这个坑写的时候顺手判断一下即可。3. 链式栈无容量上限的整形栈与选型对比3.1 为什么链表天然适合做栈链式栈的思路是把每个元素包装成一个节点节点里存 int 数据和指向下一个节点的指针。栈顶就是链表的头节点入栈操作变成了“在头部插入一个新节点”出栈操作变成了“删除头节点”。因为链表头部操作本来就是 O(1)所以整个过程非常丝滑。链表版最大的优点是没有容量上限。只要 malloc 还能分配出内存栈就能继续长。这在处理“无法预估峰值”的场景时特别有用比如从文件/网络流里不断读取数据压栈你不知道最终会有多少条数组版需要反复扩容链表版则天然支持动态增长。3.2 完整代码实现#include stdio.h #include stdlib.h #include stdbool.h typedef struct Node { int data; struct Node *next; } Node; typedef struct { Node *top; size_t size; } LinkedIntStack; void stack_init(LinkedIntStack *s) { s-top NULL; s-size 0; } bool stack_push(LinkedIntStack *s, int value) { Node *node (Node *)malloc(sizeof(Node)); if (node NULL) { return false; } node-data value; node-next s-top; s-top node; s-size; return true; } bool stack_pop(LinkedIntStack *s, int *out) { if (s-top NULL) { return false; } Node *del s-top; *out del-data; s-top del-next; free(del); s-size--; return true; } bool stack_top(const LinkedIntStack *s, int *out) { if (s-top NULL) { return false; } *out s-top-data; return true; } bool stack_empty(const LinkedIntStack *s) { return s-top NULL; } size_t stack_size(const LinkedIntStack *s) { return s-size; } void stack_destroy(LinkedIntStack *s) { Node *cur s-top; while (cur ! NULL) { Node *next cur-next; free(cur); cur next; } s-top NULL; s-size 0; }3.3 内存生命周期谁分配谁释放链式栈的内存管理比数组版复杂因为每个节点都是 malloc 出来的。几个关键点入栈时节点分配失败函数返回 false此时栈本身的状态不能改变。所以我在堆内存分配成功之后才去修改 size 和 top。出栈时先用临时指针记录待删除节点然后把 top 移到下一个节点最后才能 free。如果先 free 再改 top你立刻访问了野指针。destroy 必须以遍历方式逐个释放节点。有些人会偷懒只 free(top)结果整个链表的内存都泄漏了进程常驻一晚上内存就肉眼可见地涨。写链式栈最容易出现的“反直觉”bug 是节点结构体里存的是 int不是 int 的指针。有的同学会写出int *data这种声明那意味着每个节点内部还要管理一块 int 大小的堆内存纯属给自己加戏。int 直接内嵌在节点里就能用了。3.4 数组版与链表版的选型对照维度数组栈链表栈容量上限由动态扩容决定受连续内存限制仅受堆内存总量限制单次 push 最坏耗时扩容时 O(n) 拷贝malloc 系统调用耗时均摊时间复杂度O(1)O(1)malloc 本身有波动CPU 缓存友好度高数据连续存放低节点地址分散额外内存开销预分配容量可能大于元素数每个节点多占用一个 next 指针扩容失败影响返回 false原栈可用返回 false原栈可用适用场景算法题、高频读写、内存受限嵌入式无法预估峰值、节点缓存池良好的系统我个人的经验是做算法题、写业务代码时无脑选数组版因为缓存局部性好性能稳定做嵌入式或者实现无锁数据结构时链表版反而更容易控制内存布局。没有谁是绝对王者关键是明确每一条路的性格。4. 边界条件与踩坑复盘从测试用例到生产级细节4.1 第一坑返回值策略的妥协我最开始实现的整形栈清一色是用“特殊返回值”表达异常。入栈返回 -1 表示失败出栈返回 -1 表示空栈查看栈顶返回 -1 表示空栈。后来在括号匹配的测试用例里我往栈里压了一个 -1 作为括号编号出栈时程序把 -1 当成“栈已空”直接判断匹配失败。这个 bug 的教训是数据结构的接口语义必须与数据域的取值空间完全隔离。用 bool 出参的方式虽然调用时多写几行代码但彻底消灭了这类隐晦问题。如果你在 C 里写还可以用std::optionalint语义更清晰。4.2 第二坑realloc 失败后的状态一致性前面说的s-data realloc(...)错误写法实际发生过一次内存泄漏事故。当时服务端代码做压力测试栈容量到百万级别时内存突然飙高。定位后发现问题出在扩容失败的路径上realloc 失败返回 NULL旧指针丢失栈数据没了但调用方还以为 push 成功了。正确写法必须保证在任何失败路径上容器对象本身都保持调用前的一致状态。我在stack_push里用 tmp 接收 realloc 结果确认成功后才更新 data 和 capacity就是这个思路的直接体现。4.3 第三坑链式栈的释放顺序与调试体验排查链式栈的内存问题时我在日志里打印每个节点的地址和值发现实体还是原来的地址列表。后来发现销毁函数里有个顺序错误// 错误写法 free(cur); cur cur-next; // 已经释放了cur再访问cur-next是野指针正确顺序是先用临时变量保存 next再 free 当前节点。这个坑几乎每个写过链表的人都踩过但只有自己 debug 一遍才会真正长记性。另外链式栈在调试器里的体验比数组栈差很多。数组栈可以直接看整个连续内存区域而链表节点散落在堆里的各种地址上调试器列表只能显示一个节点。我的习惯是写一个 debug 打印函数把栈的所有元素从头到尾打印出来配合 size 一起看排查速度快得多。4.4 测试策略不要靠眼睛验证写数据结构的最大谎言是“我写完了运行一下看起来很对”。真正可靠的验证方式是拿实现和一个已知正确的标准实现做随机对照测试。我是用 Python 的 list 模拟一个标准栈然后生成大量随机操作序列比如 10 万次随机 push/pop。每个操作在 C 实现和 Python 实现里同时执行然后比对每一步的 size、top 值、操作是否成功。这类差分测试能在几十秒内把边界 bug 逼出来比我手动测试一周都有效。import random ref [] ops [] for _ in range(100000): if random.random() 0.5: val random.randint(-2147483648, 2147483647) ops.append((push, val)) else: ops.append((pop, None)) # 把 ops 发给 C 程序执行再与本地的 ref 对照边界测试也别忽略空栈 pop、空栈 top、push 一个元素后立刻 pop、连续 push 到扩容边界刚好超过初始容量 8、16、32、栈里同时出现 INT_MAX 和 INT_MIN。这些用例每一条都对应一个真实风险点。5. 从括号匹配到单调栈整形栈的真实战场5.1 括号匹配只靠字符栈也能做但整型栈更通用括号匹配是栈教学的经典案例。基本思路遇到左括号入栈遇到右括号时弹出栈顶并检查是否匹配。通常教程里会用字符栈但我这里演示一个用整形栈做的版本因为它在扩展场景下更通用——当括号种类增多时你可以把括号映射成编号入栈的依然是 int。#include string.h bool is_matched(const char *s) { IntStack st; stack_init(st); bool ok true; for (int i 0; s[i] ! \0; i) { char c s[i]; int type 0; if (c () type 1; else if (c [) type 2; else if (c {) type 3; else if (c ) || c ] || c }) { int top; if (!stack_pop(st, top)) { ok false; break; } int expected (c )) ? 1 : (c ]) ? 2 : 3; if (top ! expected) { ok false; break; } } if (type ! 0) { if (!stack_push(st, type)) { ok false; break; } } } if (ok !stack_empty(st)) { ok false; } stack_destroy(st); return ok; }这个版本的可读性可能比纯字符栈略低但它说明了一个重要观点栈里存什么不重要重要的是栈顶元素的语义和你的比较规则一致。在更复杂的解析场景里你往往需要同时保存括号类型和括号在字符串中的位置这时候把两者编码成两个整数打包入栈整形栈的价值就完全体现了。5.2 逆波兰表达式遇到运算符就弹两个数逆波兰表达式后缀表达式不需要括号运算符跟在操作数后面。比如3 4 5 *就等价于(3 4) * 5。求值过程很简单从左到右扫描遇到数字就入栈遇到运算符就弹出两个数计算再把结果入栈。扫描 3 - 栈 [3] 扫描 4 - 栈 [3, 4] 扫描 - 弹出 4 和 3计算 7栈 [7] 扫描 5 - 栈 [7, 5] 扫描 * - 弹出 5 和 7计算 35栈 [35]这里栈里存的每一步都是整数中途的计算结果也是整数整形栈和计算器的逻辑严丝合缝。中缀转后缀的过程也依靠栈存运算符本质上是对运算符优先级做 LIFO 管理。如果你平时用 C 写计算器这绝对是最顺手的数据结构。5.3 单调栈栈里装下标是整形栈的高光形态提到整型栈我强烈建议每个初学者研究一下单调栈。以 LeetCode 739“每日温度”为例给你一个温度数组要求返回每一天要等多少天才能等到更高温度。朴素解法是双重循环 O(n²)但用单调递减栈可以把时间压到 O(n)。核心思路从左到右遍历数组下标入栈。每次遇到一个新温度把它和栈顶下标对应的温度比较如果新温度更高说明栈顶那天的“下一个更高温度”就是今天弹出栈顶并记录距离然后继续比较新的栈顶。这样“栈底到栈顶”保持温度递减每个元素入栈出栈各一次总复杂度 O(n)。在这个算法里栈里装的完全是整数下标数据本体依然留在原数组里。这种“栈存索引、原数组存数据”的模式在最大矩形、接雨水、滑动窗口最大值里反复出现。如果你理解了一个整形栈这些题目都会觉得如鱼得水因为它们本质上都在问你能不能巧妙地把逆序的索引关系用栈管理起来。5.4 别忽略函数调用栈的启示最后提一个更底层的例子程序运行时的函数调用栈本质上就是一堆栈帧。每个函数的局部变量、返回地址被压入栈帧调用结束之后栈帧弹出控制权回到上一级调用者。返回地址在内存里是一个数字函数指针是一个地址这些都可以视作整型值。递归改非递归时你经常需要自己模拟这个栈把函数参数压栈循环里弹出来处理再把新的调用参数压回去。这时候你写的其实就是一个保存 int 参数的整形栈。理解这一个应用你就能触类旁通栈在编译器、虚拟机、图形学渲染管线里的无数用法。写在最后的一点个人体会把数组版和链表版的整形栈完整实现一遍之后我自己在真实项目里更倾向数组版理由很朴素现代 CPU 对连续内存的访问效率远高于散落堆里的链表节点而且数组版的调试体验好太多——你不需要在调试器里一个节点一个节点地跳直接看内存区域就够了。链表版只有在峰值完全无法预估、或者内存来自固定池的嵌入式场景里我才会主动选择。当然工程里如果用的是 C我基本都是直接std::stackint自己造轮子的目的不是为了替代标准库而是为了搞清楚标准库到底替你扛了哪些雷。你亲手写过一次整形栈再看任何语言里的栈实现都会觉得所有 API 设计都是有理由的。