用两个栈实现队列：C语言完整实现与内存模型解析

在数据结构这一关里“用两个栈实现队列”是被问得最多的一道题。核心思路其实很简单栈是后进先出LIFO队列是先进先出FIFO两个LIFO一颠倒顺序刚好就正回来了。听起来像绕口令但真正动手用C语言写出来、把内存里发生的每一件事想清楚很多人却卡住了。这篇文章不打算只给你一份能跑通的代码我会把两种实现方案、完整的C语言细节、运行时内存模型、以及我实际踩过的坑都摊开讲适合正在复习数据结构的同学、准备技术面试的朋友以及所有想认真搞懂指针和内存分配的C语言学习者。1. 问题拆解为什么“两个栈”能拼出“队列”1.1 栈和队列的底层性格差异先花两分钟把“底子”打牢。栈是一种受限的线性表只允许在同一端栈顶进行插入和删除。常说的“后进先出”是它的天性像一个叠盘子的机器你最后放上去的盘子永远第一个被拿走。队列则不同它要求所有操作在两端进行数据从队尾进、从队头出先来的人先被服务也就是“先进先出”。把这两个概念放在一起看会产生一个直觉上的冲突栈只有一个门而队列需要两个方向不同的门。那怎么用两个栈拼出一个队列关键就在于“两次翻转等于不翻转”。你往第一个栈里按队列顺序压入元素压完后再把所有元素逐个弹出来压进第二个栈第二个栈的栈顶就变成了当初队列的队头。第二次的先进后出会抵消第一次的先进后出元素顺序重新回到先进先出。很多教材把这一步叫做“用栈模拟队列”但它并不是模拟而是真实地通过两个栈的入栈、出栈动作制造出队列的出队顺序。只要你严格按照“只操作栈顶”的规则走不直接访问中间元素得到的就是一个地地道道的FIFO结构。1.2 两种常见实现方案的取舍细心的同学会发现两个栈之间元素怎么倒腾可以有不同的玩法。常见的有两种。方案A入队时直接压入栈s1出队时如果栈s2为空就把s1的所有元素弹入s2然后从s2弹出一个。这是最经典的实现入队永远O(1)出队在s2为空时最坏O(n)但在连续操作下每个元素最多被移动两次均摊是O(1)。方案B入队时先把s2所有元素倒回s1再压入新元素出队直接从s1弹出。这个方案出队O(1)入队最坏O(n)。从对称性看似乎没问题但实现里每一插入都要搬运常数更大而且代码里更容易写出顺序混乱的bug。我下面的完整代码采用方案A。原因有几个它更贴近“缓冲”的思路s2就是一个天然的“倒序缓冲区”而且现实场景中往往是连续入队、分批出队方案A在批量出队时优势明显。如果你做在线OJ题解也基本都采用这个方案面试官也更愿意听你讲清楚均摊复杂度的来源。操作方案A方案B入队O(1)直接压s1O(n)先倒腾s2到s1出队均摊O(1)s2空时需要搬运O(1)直接弹出s1实现复杂度低中典型场景批量入队、偶尔出队出队频繁、入队稀疏2. C语言实现完整代码与关键结构设计2.1 数据结构设计栈、队列写C语言第一步不是写代码是定结构。我不喜欢把栈写成一个简简单单的数组和top变量散落在函数外边那样扩展性和可读性都很差。我更愿意用结构体把栈的所有状态封装起来每个字段的含义也很清楚data指向动态数组首元素的指针栈里的数据存在这里top栈顶下标初始化成 -1 表示空栈capacity当前容量满了就扩容。对队列我用一个结构体包装两个栈的指针typedef struct { Stack *s1; // 入队栈 Stack *s2; // 出队栈 } MyQueue;为什么不直接在MyQueue里嵌套两个Stack结构体而是用指针这里有个非常实际的原因我希望队列创建时能独立控制两个栈的容量和生命周期。如果嵌套结构体初始化顺序比较麻烦而且一旦需要扩容要改动的面更大。用指针的话每个栈都是动态分配的队列的create/destroy逻辑非常对称。2.2 全部代码下面这份代码可以原样保存成一个.c文件直接编译我用的编译器是gcc标准建议用C99以上版本。栈的底层用动态数组支持扩容队列操作包含入队、出队、取队头、判空和销毁。#include stdio.h #include stdlib.h #include stdbool.h typedef struct { int *data; int top; int capacity; } Stack; // 创建栈初始容量 cap Stack *stackCreate(int cap) { if (cap 0) cap 4; Stack *s (Stack *)malloc(sizeof(Stack)); if (!s) return NULL; s-data (int *)malloc(sizeof(int) * cap); if (!s-data) { free(s); return NULL; } s-top -1; s-capacity cap; return s; } // 销毁栈先释放内部数组再释放栈结构体 void stackDestroy(Stack *s) { if (!s) return; free(s-data); free(s); } // 入栈栈满时扩容 bool stackPush(Stack *s, int val) { if (!s) return false; if (s-top 1 s-capacity) { int newCap s-capacity * 2; int *tmp (int *)realloc(s-data, sizeof(int) * newCap); if (!tmp) return false; s-data tmp; s-capacity newCap; } s-data[s-top] val; return true; } // 出栈出栈值通过 out 指针返回 bool stackPop(Stack *s, int *out) { if (!s || s-top 0) return false; if (out) *out s-data[s-top--]; return true; } // 查看栈顶元素 bool stackPeek(Stack *s, int *out) { if (!s || s-top 0) return false; if (out) *out s-data[s-top]; return true; } bool stackEmpty(Stack *s) { return !s || s-top 0; } typedef struct { Stack *s1; Stack *s2; } MyQueue; MyQueue *queueCreate(void) { MyQueue *q (MyQueue *)malloc(sizeof(MyQueue)); if (!q) return NULL; q-s1 stackCreate(4); q-s2 stackCreate(4); if (!q-s1 || !q-s2) { stackDestroy(q-s1); stackDestroy(q-s2); free(q); return NULL; } return q; } void queuePush(MyQueue *q, int val) { if (q) stackPush(q-s1, val); } bool queuePop(MyQueue *q, int *out) { if (!q) return false; if (stackEmpty(q-s2)) { int tmp; while (stackPop(q-s1, tmp)) { // 搬运过程中如果内存不够理论上要回滚 // 这里为了代码可读性先假设内存不出问题 stackPush(q-s2, tmp); } } return stackPop(q-s2, out); } bool queuePeek(MyQueue *q, int *out) { if (!q) return false; if (stackEmpty(q-s2)) { int tmp; while (stackPop(q-s1, tmp)) { stackPush(q-s2, tmp); } } return stackPeek(q-s2, out); } bool queueEmpty(MyQueue *q) { if (!q) return true; return stackEmpty(q-s1) stackEmpty(q-s2); } void queueDestroy(MyQueue *q) { if (!q) return; stackDestroy(q-s1); stackDestroy(q-s2); free(q); } int main(void) { MyQueue *q queueCreate(); queuePush(q, 1); queuePush(q, 2); queuePush(q, 3); int x; queuePop(q, x); printf(%d\n, x); // 1 queuePush(q, 4); queuePop(q, x); printf(%d\n, x); // 2 queuePeek(q, x); printf(%d\n, x); // 3 queuePop(q, x); printf(%d\n, x); // 3 queuePop(q, x); printf(%d\n, x); // 4 queueDestroy(q); return 0; }代码里每个关键点我都加了注释。有一点要特别说明在queuePop和queuePeek里从s1往s2搬元素时如果stackPush失败内存不足会导致队列状态被改了一半。完整的工业级代码应该做回滚但这篇文章的重点是讲清楚主流程所以我先把它简化了。真要写到简历里记得把失败回滚补上。2.3 内存操作流程逐步拆解空口讲不如直接追踪数据。我们模拟上面main函数里的操作记录每一次操作后两个栈的内容。约定表格里写到栈时左边是栈底右边是栈顶。操作s1栈底-栈顶s2栈底-栈顶说明初始化空空两个空栈push(1)1空新元素压入s1push(2)1, 2空继续压入s1push(3)1, 2, 3空队列目前是 1,2,3pop() 第一次空3,2,1s1全部倒入s2栈顶变1弹出后空3,2出队结果为1push(4)43,2新元素进s1不影响s2pop() 第二次43出队结果为2pop() 第三次4空出队结果为3s2空pop() 第四次空4此时s2空导入s1的4再弹出全部结束空空队列为空这个表格值得多看几遍。入队1、2、3后s1栈顶是3当第一次出队时把3、2、1依次压入s2s2栈顶变成了1。你发现没有——s1中后进的新元素被全部压在s2的底部s2只负责最老的那一批。更关键的是只要s2还有元素新来的数据就永远待在s1不会插队到老元素前面。这就是队列纪律。还有一点容易被忽略s2中的元素顺序是s1原始顺序的镜像。比如s1从栈底到栈顶是1、2、3倒进s2后从栈底到栈顶是3、2、1这时s2的pop顺序就是1、2、3正符合原队顺序。3. 内存模型深入从这段代码看懂C程序的运行时内存3.1 栈区与堆区data数组到底睡在哪里很多初学者把“栈”这个数据结构和他们听过的“栈区”搞混。你说“用栈实现队列”里的栈是一种逻辑结构而C程序运行时内存布局里的“栈区”指的是函数调用时分配栈帧的内存区域。这两个概念名字相同但完全不同面试时一定要能把它们分开。在我们这段C代码里栈区主要负责存放普通局部变量、函数调用信息。比如main函数里的MyQueue *q指针就存在栈区stackPush里的参数s和val也存在对应栈帧里。这些变量有个特征函数结束就没无需手动释放。但是Stack结构体里的data数组并不是直接在栈区分配的它是通过malloc在堆区申请的栈区只留了一个指针指向堆区。我画一个简单的归属表对象所在区域谁负责释放main里的局部变量 x栈区编译器自动MyQueue *q 指针变量栈区编译器自动q指向的MyQueue结构体堆区queueDestroy里freeq-s1指向的Stack结构体堆区stackDestroy里frees1-data指向的动态数组堆区stackDestroy里free(s-data)所以你在代码里看到三层嵌套指针q 指向堆上的MyQueueMyQueue里又存着指向Stack的指针Stack里又存着指向数组的指针。每一层malloc都要对应一次free。我见过太多只在queueDestroy里free(q)然后吐槽内存泄漏的案例实际上q只是最外面那层壳壳里的两个栈和两个数组都被漏掉了。3.2 函数调用栈帧每次调用stackPush都发生了什么“栈区”和“栈数据结构”还有一个惊人的相似点函数调用的嵌套与返回恰好也用后进先出的方式。每次调用一个函数CPU都会为它分配一个新的栈帧里面放参数、返回地址、局部变量。函数返回后栈帧被弹出控制权回到调用者。你可以想象一下main函数调queuePushqueuePush又调stackPush。此时进程的调用栈有三层main栈帧、queuePush栈帧、stackPush栈帧。每个栈帧的布局有差异但都有一个共同点它们都压在栈区顶端返回顺序正好是逆调用顺序。这在我们的队列实现里有什么影响影响不大因为调用深度固定为三层。但如果你是递归实现栈或队列就得小心了递归深度稍微大一点比如一万层栈区会被塞满程序直接段错误。反过来也说明用动态数组实现栈底层的优势之一就是不依赖系统调用栈数据可以安全地放在堆上想扩多大扩多大。另外在stackPush内部是不知道queuePush的存在它只关心传入的Stack结构体合法、和空间够不够。这种层次隔离正是封装的好处上层队列逻辑关心顺序底层栈只关心“压进去、弹出来”。3.3 指针与结构体的那些坑写C语言绕不开“传值还是传址”的问题。假设我把queuePush原型的第一个参数改成MyQueue q而不是MyQueue *q会发生什么传值时函数会复制整个MyQueue结构体包括里面两个Stack指针。函数内部执行q.s1 something只改变副本调用者那边没有任何变化。如果结构体很小没影响但MyQueue在堆上维护大量状态复制一次多了开销。更危险的是如果我想在queueCreate里初始化q就必须传MyQueue **q否则函数内部malloc出来的地址赋不回去。我这份代码全都使用结构体指针好处是显式、高效、不复制整个结构。代价是必须有NULL检查和生命周期管理。特别提醒queueCreate里一旦某个子创建失败要记得把已经分配好的部分释放干净我代码里就是用stackDestroy(q-s1)和stackDestroy(q-s2)做清扫最后才free(q)。顺序不能反先释放内部再释放外部否则内部指针丢失内存泄漏而且没法再释放。3.4 内存泄漏排查与工具内存泄漏是一种慢性病进程不退出你很难察觉但服务跑着跑着内存就蹭蹭往上涨。排查工具有很多传统且有效的是Valgrind。如果系统没装可以先跑一下简单命令gcc -g -o stack_queue stack_queue.c valgrind --leak-checkfull ./stack_queue带-g编译是为了让Valgrind在报告里指出具体源码行。运行后如果看到“All heap blocks were freed -- no leaks are possible”就说明销毁函数把堆清理干净了。如果你只写了queueDestroy没有在两个Stack内部的data上调用freeValgrind会明确报出“definitely lost: X bytes in Y blocks”还会显示malloc那一行的行号。我在实际经验里先让程序能run、能让逻辑通过这是第一步第二件事就是开Valgrind确认没有泄漏。不是小题大做因为这道题被用来考的就是你有没有理解每个malloc背后的生命周期。4. 常见问题与排查技巧实录4.1 top初始化为0还是-1这是一个很经典的C语言细节。top指栈顶下标有两种约定top -1空栈push时先top再存pop时先返回data[top]再top--top 0空栈push时存data[top]然后toppop时先top--再取值。两种都能用但我强烈建议用-1。为什么因为data数组下标从0开始-1会自然形成一个“没有任何元素”的状态很多边界判断直接写成top 0就好。如果用0表示空栈栈里第一个元素的下标和“下一次写入位置”的语义混在一起写代码时很容易多一位少一位。从内存角度理解top不是指针只是一个整型偏移量。你不需要关心数组首地址在哪只要知道栈顶元素是data[top]而top的合法范围是-1到capacity-1。把这个边界条件想透扩容判断里的s-top 1 s-capacity才不会写反。4.2 出队时s2不为空怎么办这个坑几乎人人踩。很多人第一次写会在每次出队前都执行“把s1全部导入s2”结果就会出现顺序错乱。假设目前s2里已经有3、2栈顶是2也就是说接下来该出的顺序是2、3。这时如果s1里有新元素4、5你又在s2非空时强行把4、5倒进s2s2会变成3、2、5、4然后你pop出来的是2、3、5、4顺序彻底乱了。正确做法是只要s2非空一律先从s2出s2空了才把s1的内容搬过来。从本质上看s2缓存了“已经排好队”的元素。只要缓存没清空新的元素绝不能插队到缓存前面。这跟餐厅排队一样大厅里已经排好的人得先放进去门口新来的人只能等下一轮。4.3 动态扩容时机与均摊复杂度栈底层用动态数组扩容的常规时机是top 1 capacity也就是下一个写入位置正好超过容量。扩容用realloc很合适它可能原地扩展也可能搬去新地址对调用者透明int *tmp (int *)realloc(s-data, sizeof(int) * newCap); if (!tmp) return false; s-data tmp; s-capacity newCap;注意realloc失败时会返回NULL但原来的内存块仍然可用。如果直接写成s-data realloc(...)一旦失败s-data就变成了NULL原来的数组就丢了。务必用临时变量保存返回值这属于C语言的基本素养。每次扩容先把容量翻倍这样n次push的扩容次数是O(log n)级别总复制量约为O(n)均摊到每次push是O(1)。这也是为什么很多号称“动态数组”的数据结构插入操作均摊O(1)。同理在队列场景中一个元素最多经历入栈s1、从s1弹出、入栈s2、从s2弹出这四次操作所以出队不仅是均摊O(1)常数也算可控。4.4 常见编译错误和警告清单我汇总了几个自己经常提醒别人的编译期问题忘记#include stdlib.hmalloc/realloc会得到隐式声明警告链接时可能出错stackPush里扩容判断写成了top capacity导致最后一个元素存不进去free之后没有将指针置NULL二次free导致crash传参时误用Stack s而不是Stack *s函数内修改的不是原结构体使用未初始化的局部变量int x; queuePop(q, x)时如果queuePop返回falsex没有意义但代码没检查返回值。编译时开-Wall -Wextra是个好习惯会帮你抓出一堆类型和原型不匹配的问题。4.5 面试时怎么把这个题讲得加分这道题很多网站都收录背代码的人太多了。想让面试官眼睛一亮你要讲清楚三个层次第一为什么两个LIFO能合成FIFO第二为什么s2非空时不能倒元素第三为什么均摊复杂度是O(1)。如果再主动提到内存模型、malloc/free配对、realloc失败处理基本就能体现出工程思维。我个人被问到过一次“你这个队列能任意扩展吗”这正好是动态数组栈的价值。如果当时用固定数组实现答案就得打折扣。所以实现基础数据结构动态扩容不是炫技而是刚需。5. 实测与性能建议5.1 不同场景下的表现对比为了直观我写了个小压力测试一百万次入队紧接着一百万次出队。用方案A的双栈队列和“循环数组队列”对比。结果显示双栈版本比循环数组慢了大概2到4倍原因很简单每个元素在搬运时要经历两次入栈和两次出栈也就是两倍的栈操作。这个差距在数据量很小时无感在大规模高并发队列场景下才会让人在意。所以你得知道它的定位双栈队列的结构巧妙适合作为教学、面试、以及底层只有栈接口时的替代方案。如果你的业务里队列是核心且你需要极致的吞吐直接用环形队列可能更好但你如果只想实现一个结构清晰、不依赖环形缓冲区头部指针管理的队列双栈版本也非常能打尤其适合处理“突发写入、连续读取”这类任务。指标双栈队列环形队列入队O(1) 均摊O(1) 均摊出队均摊O(1)偶尔触发整体搬运O(1) 直接移动下标常数因子较大小实现复杂度中中适合场景教学、面试、低并发高性能FIFO如果你确定使用双栈还可以做一个小优化预先给s1和s2都开较大的初始容量减少扩容次数。计算一下批量入队100万次初始容量4会导致20次左右的realloc初始容量改成1024扩容次数会少很多性能提升肉眼可见。5.2 还能怎么玩变体和拓展这道题学完可以顺手再解决几个变体用两个队列实现栈反向思路入队时把新元素放到队尾然后循环把前面的元素全部搬到另一个队列后面需要动点脑筋实现一个支持并发访问的线程安全队列给两个栈分别上锁入队锁s1、出队锁s2比全局锁的粒度更细做一个“双端队列”的骨架底层改成两个可双向访问的数据结构其实难度比双栈大但思路类似把栈的底层换成链表避免数组扩容代价是每个节点都要malloc/free碎片化更高。如果哪天你遇到的语言标准库只提供了Stack而没有Queue比如某些古老环境或嵌入式平台双栈实现队列就是现成方案。这种“用已有基础组件组装新功能”的思路在系统设计里也常常用到。我个人还有一个小习惯写完双栈队列后一定要用随机操作序列做压力测试把入队和出队顺序打乱再和标准队列的输出比对。因为顺序敏感的bug往往在最普通的1、2、3测试里看不出来。把代码丢给随机测试跑几分钟比读十遍代码都管用。最后说点自己这些年反复体会的东西数据结构题不是背出来的是“想”出来的。我最初写这道题的时候以为弄清楚了两个栈的进出就完了直到把malloc出来的那块内存、每个函数的栈帧、每一个指针指向哪里都走了一遍才真正觉得心里有底。后来我发现面试官真正想看到的不是你能默写代码而是你能不能在白板上画出s1、s2两个方块然后用箭头标出每一步元素的走向。你能画出来说明你真的理解它你理解它这道题才真正属于你。