实现一个整形栈看完这个题目我愣了几秒紧接着就乐了。愣是因为整形多半是整型的笔误乐是因为这大概是每个写代码的人绕不过去的一道基础题但真正把它当回事、认真从零写一遍的人说实话不多。这个栈字在计算机世界里被用得太滥了有系统底层的调用栈有编译器里的操作数栈有算法题里大杀四方的单调栈还有前端后端嘴里天天挂的技术栈、全栈项目。有意思的是这些场景全都建立在同一个抽象模型上——后进先出LIFO。而实现一个整形栈就是把这种抽象落到内存里的最小、最完整的练习你既要管数据放哪又要管空间不够了怎么办还要管取空栈的时候别崩。这篇内容我按自己的实战经验来写主线是C语言下的动态数组栈适合三类人正在学数据结构的学生、要应付笔试面试的求职者以及在嵌入式或底层环境里需要手写基础容器的工程师。看完你能得到一份可以直接抄走的完整代码、一套边界处理的心法还有一堆我在真实调试里踩过的坑。1. 动手之前先说清楚这个栈到底要解决什么问题1.1 从抽象模型到真实场景栈的定义一句话就能说完只能在一端栈顶插入和删除元素的线性表。听起来干巴巴的可它背后的应用清单相当惊人。函数调用时每进入一层函数系统就把返回地址、参数、局部变量压进调用栈函数返回时再弹出去这套机制保证了嵌套调用能按正确的顺序回到该回的位置。表达式的括号匹配和四则运算求值经典做法是维护两个栈——操作数栈和运算符栈。浏览器的前进后退、编辑器的撤销重做本质也都是栈。深度优先搜索和回溯算法栈更是它们的地基。所以我常说栈不是为了让面试官为难而存在的知识点它是所有基础数据结构里最贴近机器真实运行逻辑的一个。你在报错日志里看到的backtrace调用栈回溯说白了就是调试器沿着调用栈的帧结构一层层往外走的产物。理解了栈你才算真正开始理解程序是怎么跑起来的。1.2 为什么第一步要拿整型开刀做任何数据结构选一个合适的最小元素类型都很重要。int是天然的试验品它占4个字节是值语义没有指针和生命周期问题赋值就是拷贝比较就是等值测试时一眼能看出对错。等int栈写明白了你再去实现字符串栈、结构体栈、泛型栈差别只是元素的内存布局和所有权管理变复杂了栈本身的逻辑骨架完全不用换。我见过不少人上来就搞void*万能栈结果在类型安全上吃尽苦头。我劝你先老老实实把int栈这关过了后面的事后面再说地基不打牢房子盖得再高也是危楼。2. 两种主流实现选型数组栈和链表栈怎么挑2.1 底层路线的对比写一个栈物理上只有两种容器可选连续内存的数组或者节点分散的链表。先做方案选型后面代码才不会返工。我把两种方案的关键差异列成了一张表这是我最常用的一张自检表。对比维度数组栈链表栈内存布局连续一次性分配大块每个节点分别分配访问速度缓存友好下标直达需要跟随指针跳转扩容方式整体搬移均摊成本低每次push分配一个新节点额外开销几乎没有每个节点多一个指针字段实现难度中难点在扩容和溢出低但内存释放容易被忽略适用场景高频访问、容量可预估栈多而零散、内存碎片敏感在实际工程里两类栈都有大量用户。但我的默认选择是数组栈尤其当栈的访问非常频繁、数据量又比较集中时数组的缓存局部性优势是压倒性的。详细原因我放在下面单独讲。2.2 为什么要优先选动态数组先说说缓存局部性。CPU读取数据的时候是一块一块拉进缓存的数组元素在内存里紧挨着访问第N个元素的时候周围十几个元素已经被一起带进缓存了。链表呢每个节点可能散落在内存的各个角落访问一个节点就要做一次指针跳转大概率触发缓存未命中。在高频push/pop的场景下这两者的性能差距能拉到一个数量级这不是夸张是我实测过的结论。另一个原因是分配开销。数组栈的扩容是偶尔一次大动作平时push只是在已有的连续内存里写一个值。链表栈每次push都要调用malloc申请节点每次pop都要free这两个系统调用在高频场景下会变成巨大的瓶颈。当然malloc/free并不总是那么慢但如果你想写一个高性能的基础容器能把它们省掉就尽量省掉。2.3 链表栈在什么情况下更合适链表栈也不是没有闪光点。它的push是纯粹的O(1)不需要扩容搬移每个栈独立管理自己的节点不需要预留capacity实现上完全不用考虑realloc带来的指针失效问题代码写起来干净利落。我一般在两种场景下会主动选链表栈一是栈的总数特别多单个栈的平均元素很少比如给模拟器里每个线程维护一个小的中间栈数组方案会浪费大量未使用的capacity二是内存碎片严重、无法一次性分配连续大块的环境。如果你拿不准记住一个粗暴的判断法性能敏感选数组逻辑简单选链表两头都想要就用内存池配链表但那已经是后话了。3. 核心设计与完整实现动态数组栈的C语言落地3.1 结构体和API怎么定才顺手设计上我倾向把数据结构内部状态和用户操作彻底分开。栈内部有data指针、capacity、size三个字段对外只暴露操作函数用户拿到的始终是一个指向栈对象的指针和一个标准化的返回值。这样的结构不仅清晰而且方便以后在里面加锁、加统计信息用户代码一行都不用改。typedef struct { int *data; /* 指向堆上连续内存 */ int capacity; /* 当前分配的总容量 */ int size; /* 已用的元素个数也是下一个空位的下标 */ } IntStack; /* 初始化与销毁 */ void StackInit(IntStack *s); void StackDestroy(IntStack *s); /* 基本操作成功返回0失败返回-1 */ int StackPush(IntStack *s, int value); int StackPop(IntStack *s, int *out); int StackPeek(const IntStack *s, int *out); /* 查询状态 */ int StackIsEmpty(const IntStack *s); int StackSize(const IntStack *s);这里有一个很多人一开始不习惯的约定Pop和Peek不直接返回元素值而是通过out指针参数带出结果。为什么这么设计因为函数返回值要专门用来报告错误状态。弹出空栈返回-1窥视空栈顶返回-1扩容失败返回-1。调用方永远能区分正常拿到了一个值和这次操作失败了这在工程代码里是非常关键的错误处理纪律。还有一个细节所有函数都只接收指向栈对象的指针不从参数传结构体本身。原因很实在——结构体内部有指向堆内存的指针如果按值传递拷贝出来的临时结构体会让同一块堆内存同时存在两个拥有者销毁时必然导致双重释放这是C语言新手最容易踩的雷。3.2 初始化、销毁和扩容策略初始化要做的事很朴素data置空、容量和大小清零。注意不要图省事在Init里就malloc一大块内存正确的做法是让第一次push触发扩容。这样创建一个空栈的成本是零能被放进各种只读路径里而不会拖累性能。void StackInit(IntStack *s) { s-data NULL; s-capacity 0; s-size 0; } void StackDestroy(IntStack *s) { free(s-data); s-data NULL; s-capacity 0; s-size 0; }StackDestroy里有一行特别容易被忽略的代码s-data NULL。free之后如果不置空栈对象就成了个拿着悬垂指针的空壳下次任何操作都会在诡异的地方崩溃。这个习惯我从int栈一直带到了后来的泛型容器里救了我很多次。扩容函数是数组栈的精髓直接关系到性能上限static int StackGrow(IntStack *s) { int newCapacity (s-capacity 0) ? 4 : s-capacity * 2; int *newData (int *)realloc(s-data, (size_t)newCapacity * sizeof(int)); if (newData NULL) { return -1; /* 保留原数组栈依然可用 */ } s-data newData; s-capacity newCapacity; return 0; }初始容量取4而不是1是因为realloc本身有成本从1慢慢涨会导致扩容次数过多实测中还会制造大量内存碎片。每次翻倍而不是加固定数量的原因更经典翻倍扩容能保证每个元素平均只被搬运常数次这就是教科书里说的均摊O(1)。你算一下就会发现插入第N个元素时总搬运次数大约是NN/2N/4...收敛于2N所以每个元素的均摊成本就是常数。3.3 Push把空间不足变成内部小事push逻辑很短但每一行都有讲究int StackPush(IntStack *s, int value) { if (s-size s-capacity) { if (StackGrow(s) ! 0) { return -1; } } s-data[s-size] value; return 0; }首先要判断满了没有满则先扩容。注意我把扩容失败当成一次普通失败返回-1由上层决定是记录日志还是直接终止。嵌入式场景里有人喜欢在这直接断言退出但作为通用库优雅返回错误码更稳妥。然后是写值和size自增。这里有一个隐蔽的坑s-data是int*realloc成功后旧指针就失效了但新指针已经赋值回s-data所以只要后续都通过结构体访问就不会有问题。真正的麻烦来自外部有人提前保存了s-data的副本扩容之后副本变成悬垂指针这种bug我在后面第4节详细说。3.4 Pop与Peek下溢和边界判断int StackPop(IntStack *s, int *out) { if (s-size 0) { return -1; } if (out ! NULL) { *out s-data[--s-size]; } else { s-size--; } return 0; } int StackPeek(const IntStack *s, int *out) { if (s-size 0) { return -1; } if (out ! NULL) { *out s-data[s-size - 1]; } return 0; }pop的核心动作是先把size减一再取data[size]这个下标位置的值顺序不能反。Peek则只是看栈顶元素不改变size所以它接收const指针告诉调用方我不会动你的栈。这里我想多说一个习惯问题pop的时候要不要把已经弹出去的那个槽位清零对int栈来说无所谓int没有悬垂指针问题。但如果将来泛化成结构体栈这一步就是必须的——否则元素虽然在逻辑上被移除了它内部的指针字段还指向旧内存谁在栈外捡到这份数据都可能出事。我从int栈开始就养成了设计时预留清理逻辑的习惯等到写复杂对象栈的时候自然就知道怎么处理了。3.5 完整代码与使用示例把上面的模块拼起来就是一份可以直接编译运行的整体实现#include stdio.h #include stdlib.h typedef struct { int *data; int capacity; int size; } IntStack; void StackInit(IntStack *s) { s-data NULL; s-capacity 0; s-size 0; } void StackDestroy(IntStack *s) { free(s-data); s-data NULL; s-capacity 0; s-size 0; } static int StackGrow(IntStack *s) { int newCapacity (s-capacity 0) ? 4 : s-capacity * 2; int *newData (int *)realloc(s-data, (size_t)newCapacity * sizeof(int)); if (newData NULL) return -1; s-data newData; s-capacity newCapacity; return 0; } int StackPush(IntStack *s, int value) { if (s-size s-capacity) { if (StackGrow(s) ! 0) return -1; } s-data[s-size] value; return 0; } int StackPop(IntStack *s, int *out) { if (s-size 0) return -1; if (out ! NULL) *out s-data[--s-size]; return 0; } int StackPeek(const IntStack *s, int *out) { if (s-size 0) return -1; if (out ! NULL) *out s-data[s-size - 1]; return 0; } int StackIsEmpty(const IntStack *s) { return s-size 0; } int StackSize(const IntStack *s) { return s-size; } int main(void) { IntStack s; StackInit(s); for (int i 0; i 10; i) { StackPush(s, i * i); } int v; while (StackPop(s, v) 0) { printf(%d , v); } printf(\n); StackDestroy(s); return 0; }这段代码跑出来的输出是81 64 49 36 25 16 9 4 1 0正好是后进先出。我建议你拿到之后自己编译运行一遍看着这一串逆序的平方数被打出来手写栈的第一个自信就是这么建立的。4. 我踩过的坑和排查实录4.1 扩容后指针地址变化引发的use-after-free这是我在一个表达式解析器里真实翻过车的场景。当时解析器的某模块为了性能缓存了栈顶元素的直接地址结果一次循环里连续push了几千个元素触发多次扩容缓存下来的旧地址全部变成垃圾数据读出来的内容一会儿对一会儿错查了整整一个下午。排查方法其实很简单在StackGrow函数里临时打印realloc前后的data地址肉眼就能看到扩容后指针跳了。从此我定了一条铁律任何情况下都不要长期持有栈内部元素的指针需要数据就通过返回值拷出来一份让栈自己管理它的内存。4.2 空栈弹出的假正常这可能是所有bug里最阴险的一类。调用方拿到了pop的返回值却直接忽略栈空时函数返回-1out参数保持着原来的值程序不崩、不报警但业务结果已经完全不对。比如你弹栈做undo栈空时弹出来一个旧值用户界面会显示一次不该有的回退这种问题比崩溃难查十倍。对策没有捷径就一条凡是调用可能失败的接口必须检查返回值。我在团队里定的规矩是Pop和Peek的返回值不检查代码评审直接打回。C语言没有异常机制错误码就是唯一的沟通渠道你不听他说话他就用更难看的方式让你听见。4.3 扩容溢出和realloc失败的处理容量翻倍在工程里还有个隐藏风险当capacity增长到上亿级别capacity乘2再乘sizeof(int)可能溢出int甚至size_t。虽然int栈要push几十亿个元素才会触发但作为一个库的维护者该防御的还是要防御。我建议用size_t做容量计算或者在上限处做个判断比如容量超过130就返回-1提示已经到顶了。realloc失败的处理也是一门学问。很多人一看到realloc返回NULL就慌了直接认为栈报废了。其实realloc有一个重要特性失败时它不会动原来的指针你的数据还完好地躺在原地。正确的做法是原样保留旧数组向上层返回-1让栈继续以旧容量工作。我在低内存的嵌入式设备上实测过这条恢复路径在某些临界场景里能救一命。4.4 别把系统调用栈和手写栈搞混聊到这里必须顺手把概念边界划清楚。操作系统里的调用栈、中断栈跟咱们手写的IntStack完全不是一回事但抽象模型一模一样。系统调用栈是CPU和操作系统共同维护的运行时机制每进入一个函数就压入一帧包含返回地址、帧指针、局部变量每返回就从栈顶弹出一帧。中断发生时CPU会切换到独立的中断栈保存被打断现场的寄存器状态。理解了这套机理你再看嵌入式开发里常见的ARM调用栈回溯日志那些Backtrace条目其实就是一层层栈帧被回溯时记录下来的调用顺序。说到底底层的栈用的是同一个后进先出思想只不过压进去的从int变成了栈帧结构。这就是为什么我说把int栈亲手写一遍你对整个计算机运行模型的理解都会上一个台阶。5. 从整形栈出发还能走多远5.1 泛型栈、线程安全栈、内存池栈如果说int栈是骨架工程化方向就是在骨架上加肉。泛型化是最常见的一步C可以用模板一个模板类搞定任意类型C语言要么用void*加类型标志要么用宏生成——X-Macro方案在嵌入式C代码里很流行用一套宏定义批量生成不同元素类型的栈代码改动成本极低。再进一步是线程安全栈。多线程共享一个栈时push和pop需要加锁保护C标准库的mutex就能满足追求极致性能的会用无锁方案用CAS操作原子地更新栈顶指针这就是另一个深水区了。性能敏感的场景还会引入内存池给链表栈预分配一批节点避免高频push/pop时反复调用malloc和free这个方向对嵌入式开发尤其重要。5.2 单调栈同一个模型不同的玩法单调栈是算法题里的大明星它在普通栈的基础上保证栈内元素按某种规则单调递增或递减。典型题目是下一个更大元素从左到右扫描数组维护一个单调递减栈遇到比栈顶大的元素就弹栈弹出时记录答案。这个技巧能把O(n^2)的暴力解法优化到O(n)。我面试过不少人聊到单调栈都能说个大概真到白板上写代码就露馅错的地方几乎都集中在弹栈时机和边界处理上。根本原因就是基础栈的push/pop边界不够熟逻辑稍一复杂就崩。所以我说扎实的int栈基本功是理解单调栈的前提这个顺序没法跳。5.3 栈和队列、堆和栈的边界感最后做一个高频概念辨析。栈和队列都是线性结构一个后进先出一个先进先出很多系统用两个栈模拟一个队列也能用一个循环队列模拟栈这两个概念经常被放在一起考。而堆这个词更麻烦它既可以指动态内存区域也可以指一种完全二叉树结构堆排序、优先队列。堆区内存由malloc管理生命周期自由栈区内存由编译器自动管理函数一进出就自动分配释放。把这两者放到同一张内存图里看会特别清晰你在程序里new一个对象对象本身在堆区但指向它的指针变量在栈区你手写的IntStack结构体可以在栈区而内部data数组却通过malloc活在堆区。理解了这层关系很多关于内存的困惑都能迎刃而解。我一个人这些年带新人的体会是基础容器的实现光看十遍不如自己写一遍。这个int栈加起来不过七八十行但它逼着你面对扩容、边界、内存、错误处理这四个躲不开的问题。建议你拿到代码之后先自己敲一遍然后试着把整型改成字符串再把Pop和Peek改成能返回错误码的API最后试着加上容量缩水的逻辑。每一步都会让你对内存和栈的理解更扎实。真到某天你对着backtrace做调用栈回溯、或者用单调栈秒杀算法题的时候你会感谢今天这几十行代码。