在数据结构这一关里，“用两个栈实现队列”是被问得最多的一道题。核心思路其实很简单：栈是后进先出（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空出队结果为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里freeq->s1指向的Stack结构体堆区stackDestroy里frees1->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两个方块，然后用箭头标出每一步元素的走向。你能画出来，说明你真的理解它；你理解它，这道题才真正属于你。
在数据结构这一关里，“用两个栈实现队列”是被问得最多的一道题。核心思路其实很简单：栈是后进先出（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空出队结果为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里freeq->s1指向的Stack结构体堆区stackDestroy里frees1->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两个方块，然后用箭头标出每一步元素的走向。你能画出来，说明你真的理解它；你理解它，这道题才真正属于你。