在数据结构这一关里，“用两个栈实现队列”是被问得最多的一道题。核心思路其实很简单：栈是后进先出（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)，直接压s1 | O(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 | 空 | 新元素压入s1 |
| push(2) | 1, 2 | 空 | 继续压入s1 |
| push(3) | 1, 2, 3 | 空 | 队列目前是 1,2,3 |
| pop() 第一次 | 空 | 3,2,1 | s1全部倒入s2，栈顶变1 |
| 弹出后 | 空 | 3,2 | 出队结果为1 |
| push(4) | 4 | 3,2 | 新元素进s1，不影响s2 |
| pop() 第二次 | 4 | 3 | 出队结果为2 |
| pop() 第三次 | 4 | 空 | 出队结果为3，s2空 |
| pop() 第四次 | 空 | 4 | 此时s2空，导入s1的4，再弹出 |
| 全部结束 | 空 | 空 | 队列为空 |
这个表格值得多看几遍。入队1、2、3后，s1栈顶是3；当第一次出队时，把3、2、1依次压入s2，s2栈顶变成了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里free |
| q->s1指向的Stack结构体 | 堆区 | stackDestroy里free |
| s1->data指向的动态数组 | 堆区 | stackDestroy里free(s->data) |
所以你在代码里看到三层嵌套指针：q 指向堆上的MyQueue，MyQueue里又存着指向Stack的指针，Stack里又存着指向数组的指针。每一层malloc都要对应一次free。我见过太多只在queueDestroy里free(q)然后吐槽内存泄漏的案例，实际上q只是最外面那层壳，壳里的两个栈和两个数组都被漏掉了。
3.2 函数调用栈帧：每次调用stackPush都发生了什么
“栈区”和“栈数据结构”还有一个惊人的相似点：函数调用的嵌套与返回恰好也用后进先出的方式。每次调用一个函数，CPU都会为它分配一个新的栈帧，里面放参数、返回地址、局部变量。函数返回后栈帧被弹出，控制权回到调用者。
你可以想象一下，main函数调queuePush，queuePush又调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-check=full ./stack_queue带-g编译是为了让Valgrind在报告里指出具体源码行。运行后如果看到“All heap blocks were freed -- no leaks are possible”就说明销毁函数把堆清理干净了。如果你只写了queueDestroy，没有在两个Stack内部的data上调用free，Valgrind会明确报出“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]然后top++，pop时先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倒进s2，s2会变成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.h>，malloc/realloc会得到隐式声明警告，链接时可能出错； stackPush里扩容判断写成了top >= capacity，导致最后一个元素存不进去；- free之后没有将指针置NULL，二次free导致crash；
- 传参时误用
Stack s而不是Stack *s，函数内修改的不是原结构体； - 使用未初始化的局部变量
int x; queuePop(q, &x)时，如果queuePop返回false，x没有意义，但代码没检查返回值。
编译时开-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两个方块，然后用箭头标出每一步元素的走向。你能画出来，说明你真的理解它；你理解它，这道题才真正属于你。
