栈和队列专题（四）：LeetCode 232. 用栈实现队列｜双栈分工 + 按需迁移 + 摊还 O(1)

写在前面

在栈和队列专题（二）中，我们用两个队列实现了栈：通过反复搬运元素，把队列的 FIFO（先进先出）转换成了栈的 LIFO（后进先出）。

上一篇专题（三）又拆解了 LeetCode 622「设计循环队列」，用数组、front/rear 指针和取模运算完成了空间的循环复用，并且在结尾留下了一个问题：

如果不需要访问队尾，双栈实现队列会不会是更优雅的方案？

今天这篇就把方向彻底反过来：只使用两个标准栈，实现一个先进先出的队列，也就是 LeetCode 232「用栈实现队列」。

这道题表面上和 225 完全对称，但真正写下来会发现，两者的数据搬运策略差别很大：

• 225：为了拿到“最后进入”的元素，每次出栈都可能要搬运一整队数据；
• 232：两个栈明确分工后，只在必要时做一次整体迁移，元素绝不会来回反复倒。

这也是本题最值得理解的地方：为什么单次迁移可能是 O(N)，整个队列的操作整体仍然可以做到摊还 O(1)？

一、题目要求

仅使用两个栈实现先入先出队列，支持以下操作：

• push(x)：将元素 x 推到队列末尾
• pop()：从队列开头移除并返回元素
• peek()：返回队列开头的元素，不删除
• empty()：判断队列是否为空

约束：只能使用栈的标准操作——压入栈顶、弹出栈顶、获取栈顶、判空、获取元素个数，不能直接访问栈底。

二、本质问题：LIFO 怎么变成 FIFO？

栈的特性是后进先出，队列是先进先出，两者顺序恰好相反。

假设元素按1 → 2 → 3 → 4的顺序入队，真正的队列应该是：

队首 队尾 ↓ ↓ 1 → 2 → 3 → 4

第一次出队必须得到1。

但如果把它们直接压入同一个栈：

栈顶 ↓ 4 3 2 1

第一次弹出的却是4，顺序完全反了。

解决思路非常直观：再用第二个栈把顺序反转一次。 把第一个栈的元素全部弹出，依次压入第二个栈：

栈顶 ↓ 1 2 3 4

此时第二个栈的栈顶，恰好就是队列的队头。所以：两次 LIFO 叠加，就能得到 FIFO。

三、两个栈的明确分工

两个栈不是临时容器，而是职责非常清晰的两个角色：

• inStack（输入栈）：专门负责入队，所有新元素统一压入这里
• outStack（输出栈）：专门负责出队、取队头，所有读操作都从这里取

3.1 inStack：只管入队，零搬运

所有push操作直接压入inStack，不需要管 outStack 有没有数据。 比如依次 push 1、2、3：

inStack 栈顶 ↓ 3 2 1

入队全程不做任何数据搬运，因此push天然是 O(1)。

3.2 outStack：只管队头操作

pop和peek都只操作outStack。 如果 outStack 里已经有元素，它的栈顶就是当前队头，直接读取或弹出即可。

真正的问题只有一个：outStack 为空的时候怎么办？这时候才需要把 inStack 的数据整体迁移过来。

四、最关键的规则：只有 outStack 为空时才迁移

这是整道题的核心优化点，也是很多初学者最容易写错的地方。

正确做法

当outStack为空时，把inStack里的所有元素一次性全部倒入outStack，完成一次顺序反转。 迁移完成后，outStack 栈顶就是队头，后续的 pop/peek 直接操作它就行。

为什么 outStack 不为空时绝对不能迁移？

举个反例就很清楚：

1. 假设 outStack 里已经有1、2、3（栈顶是 1），说明当前队头顺序是1 → 2 → 3。
2. 此时又 push 了4、5，新元素进入 inStack。 逻辑上完整的队列应该是：1 → 2 → 3 → 4 → 5。
3. 如果这时候为了“统一存放”，把 inStack 的 4、5 也倒进 outStack，栈顶就会变成 5，队头顺序直接被打乱。

正确的逻辑是：outStack 里的元素还没消费完，就继续优先消费它； 等 outStack 彻底空了，再把新一批元素整体迁移过来排序。

这是双栈队列保持正确顺序的核心不变量：outStack 不为空，绝不迁移。

五、核心操作逐个拆解

5.1 迁移函数单独封装

迁移逻辑会被peek和pop共用，单独封装成内部函数：

static void transfer(MyQueue* obj) { while (!StackEmpty(obj->inStack)) { int val = StackTop(obj->inStack); StackPop(obj->inStack); StackPush(obj->outStack, val); } }

它只做一件事：把 inStack 全部元素倒入 outStack，完成一次整体反转。

5.2 push：直接进输入栈

void myQueuePush(MyQueue* obj, int x) { StackPush(obj->inStack, x); }

不判断 outStack，不做任何搬运。新元素本来就应该排在所有已有元素的后面，放在 inStack 里就是正确的位置。 时间复杂度：O(1)。

5.3 peek：真正负责“按需迁移”

peek是整道题的逻辑中心，所有迁移判断都收拢在这里：

int myQueuePeek(MyQueue* obj) { if (myQueueEmpty(obj)) { return -1; } if (StackEmpty(obj->outStack)) { transfer(obj); } return StackTop(obj->outStack); }

三步逻辑：

1. 先判空：两个栈都为空才是空队列
2. 再判断 outStack：为空就整体迁移，不为空就跳过
3. 直接返回 outStack 栈顶，也就是队列队头

5.4 pop：复用 peek，消除重复代码

pop和peek的前置逻辑完全一致：都要判空、都要判断是否需要迁移。 没必要把同样的代码写两遍，直接复用peek拿到队头值，再执行删除即可：

int myQueuePop(MyQueue* obj) { if (myQueueEmpty(obj)) { return -1; } int ret = myQueuePeek(obj); StackPop(obj->outStack); return ret; }

peek负责定位队头，pop只负责删除队头。公共逻辑只维护一份，既减少代码冗余，也保证逻辑统一。

5.5 empty：必须同时检查两个栈

bool myQueueEmpty(MyQueue* obj) { return StackEmpty(obj->inStack) && StackEmpty(obj->outStack); }

不能只检查 inStack——元素可能已经全部迁移到了 outStack；也不能只检查 outStack——新元素可能还在 inStack 里。 只有两个栈同时为空，队列才是真的空。

六、完整 LeetCode AC 代码

继续复用前面实现的动态顺序栈（top = -1，指向当前栈顶元素），单文件直接提交：

#include <stdlib.h> #include <stdbool.h> #include <assert.h> #include <stdio.h> typedef int STDataType; typedef struct Stack { STDataType* a; int top; int capacity; } Stack; typedef struct { Stack* inStack; Stack* outStack; } MyQueue; void StackInit(Stack* ps) { assert(ps); ps->a = NULL; ps->top = -1; ps->capacity = 0; } void StackPush(Stack* ps, STDataType data) { assert(ps); if (ps->top == ps->capacity - 1) { int num = ps->capacity == 0 ? 4 : ps->capacity * 2; STDataType* tmp = (STDataType*)realloc(ps->a, sizeof(STDataType) * num); if(tmp == NULL) { perror("realloc fail"); exit(-1); } ps->a = tmp; ps->capacity = num; } ps->top++; ps->a[ps->top] = data; } void StackPop(Stack* ps) { assert(ps); assert(ps->top >= 0); ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); assert(ps->top >= 0); return ps->a[ps->top]; } int StackEmpty(Stack* ps) { assert(ps); return ps->top == -1; } void StackDestroy(Stack* ps) { assert(ps); free(ps->a); ps->a = NULL; ps->top = -1; ps->capacity = 0; } static void transfer(MyQueue* obj) { while (!StackEmpty(obj->inStack)) { int val = StackTop(obj->inStack); StackPop(obj->inStack); StackPush(obj->outStack, val); } } MyQueue* myQueueCreate() { MyQueue* obj = (MyQueue*)malloc(sizeof(MyQueue)); obj->inStack = (Stack*)malloc(sizeof(Stack)); obj->outStack = (Stack*)malloc(sizeof(Stack)); StackInit(obj->inStack); StackInit(obj->outStack); return obj; } void myQueuePush(MyQueue* obj, int x) { StackPush(obj->inStack, x); } bool myQueueEmpty(MyQueue* obj) { return StackEmpty(obj->inStack) && StackEmpty(obj->outStack); } int myQueuePeek(MyQueue* obj) { if (myQueueEmpty(obj)) { return -1; } if (StackEmpty(obj->outStack)) { transfer(obj); } return StackTop(obj->outStack); } int myQueuePop(MyQueue* obj) { if (myQueueEmpty(obj)) { return -1; } int ret = myQueuePeek(obj); StackPop(obj->outStack); return ret; } void myQueueFree(MyQueue* obj) { StackDestroy(obj->inStack); free(obj->inStack); StackDestroy(obj->outStack); free(obj->outStack); free(obj); }

七、为什么不是每次 pop 都重新倒一次？

很多初学者会走入一个误区：每次出队都把 inStack 倒到 outStack，用完再倒回去。 这样既浪费性能，也完全没有必要。

我们用一个完整流程看一遍：

1. push 1、2、3、4 → inStack: [1,2,3,4]，outStack: 空
2. 第一次 pop → 触发迁移，outStack 变成 [4,3,2,1]（栈顶是1），弹出1
3. 第二次 pop → outStack 不为空，直接弹出2
4. 第三次 pop → 直接弹出3

直到 outStack 彻底清空之前，都不需要再碰 inStack。 也就是说，一个元素从进入队列到离开，最多只会被迁移一次：

push 进 inStack ↓ 最多迁移一次到 outStack ↓ 从 outStack 弹出

绝不会出现in → out → in → out来回倒的情况。这就是双栈方案高效的根本原因。

八、摊还 O(1) 到底是什么意思？

这是本题最值得理解的概念，也是面试常考点。

有人会质疑：迁移的时候要移动 N 个元素，明明是 O(N)，为什么说 O(1)？ 答案是：单次最坏是 O(N)，但从一长串操作的整体平均来看，每个操作的成本是常数级。

我们从两个角度理解：

角度1：单个元素的生命周期

一个元素完整的一生只有四步：

1. 压入 inStack → O(1)
2. 弹出 inStack → O(1)
3. 压入 outStack → O(1)
4. 弹出 outStack → O(1)

每一步都是 O(1)，而且每个元素最多只会被迁移一次，不会反复搬运。 所以对于单个元素来说，总开销是固定常数。

角度2：N 个元素的整体视角

假设一共入队 N 个元素，执行 N 次出队。

• 所有迁移操作加起来，最多处理 N 个元素
• 所有入队、出队操作加起来，也处理 N 个元素

整个序列的总代价是 O(N)，平均分摊到 N 次操作上：

O(N) / N = O(1)

这就是摊还时间复杂度 O(1)。

注意：摊还 O(1) 不代表每一次操作都是严格 O(1)。 某一次触发大规模迁移的 pop/peek 仍然可能是 O(N)，但从整体平均来看，每个操作的成本是常数级。

九、各接口复杂度总结

空间复杂度：O(N)。 两个栈并不意味着两份数据，同一时间 N 个元素只会存在于其中一个栈里，只是在两个容器之间迁移。

十、横向对比：和另外两道经典题的区别

10.1 对比 225：用队列实现栈

两道题看似对称，迁移策略差异很大：

两道题本质都是利用底层结构的顺序特性，重新组织元素的访问顺序；但 232 的“输入栈 + 输出栈”分工更加稳定，因此能做出摊还优化。

10.2 对比 622：循环数组队列

上一篇的循环队列和本篇双栈队列，都实现了 FIFO，但侧重点完全不同：

简单总结就是：需要频繁访问队尾、固定容量缓冲，选循环数组；只需要标准队列操作、想复用栈模块，选双栈。

十一、工程化落地：栈代码的复用与本次文件结构

这道题最直观的工程价值，就是可以直接复用已经写好的栈代码。前面我们已经完整实现过动态顺序栈的全套接口，到这里不需要再从零手写一遍数组、top、扩容逻辑，直接拿过来组合就能实现队列。

本次提交到 Git 的版本，采用三文件结构：

• queue232.h：头文件，统一存放栈结构体、队列结构体，以及全部对外接口的声明
• queue232.c：核心实现文件，包含完整的栈函数实现 + 双栈队列实现，栈逻辑直接复用之前的成熟代码
• test.c：本地测试文件，覆盖入队、出队、取队头、判空等核心场景

这种组织方式既保证了栈逻辑的复用，又维持了单题文件结构的简洁，不需要为了一道题额外拆分多层目录。队列层完全通过栈的标准接口操作底层，不直接触碰数组和下标，也体现了「上层依赖接口、不依赖底层实现」的思路。

代码仓库：

数据结构/8.20 LeetCode 232.用栈实现队列 · Luminous/Code_2026 - 码云 - 开源中国

写在最后

LeetCode 232 的代码其实非常短，真正决定理解深度的，从来不是能不能记住那一行if (StackEmpty(obj->outStack)) transfer(obj);。

而是能不能回答两个问题：

1. 为什么只有 outStack 为空时才能迁移？
2. 明明一次迁移可能移动 N 个元素，为什么整体是摊还 O(1)？

把这两个问题想明白，双栈队列就不再是一个需要背的模板，而是一套可以推导出来的设计。

从顺序栈、链式队列，到 225 两队列模拟栈、622 数组循环队列，再到今天的 232 两栈模拟队列，栈和队列的关系已经非常清晰： 它们不只是两个需要背接口的数据结构，而是可以通过顺序反转、数据搬运和状态维护互相模拟、互相组合的基础单元。

到这里，栈和队列专题的三道核心结构题就全部串起来了。 下一篇我们会正式开启新的专题，进入二叉树的内容，当然，栈和队列的经典应用题 —— 比如括号匹配、单调栈、BFS 广度优先搜索等等，后面也会结合对应题目继续练习，不会就此停下。基础结构是工具，最终还是要落到具体问题里去发挥作用。