栈和队列专题（四）：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、3inStack 栈顶 ↓ 3 2 1入队全程不做任何数据搬运因此push天然是 O(1)。3.2 outStack只管队头操作pop和peek都只操作outStack。 如果 outStack 里已经有元素它的栈顶就是当前队头直接读取或弹出即可。真正的问题只有一个outStack 为空的时候怎么办这时候才需要把 inStack 的数据整体迁移过来。四、最关键的规则只有 outStack 为空时才迁移这是整道题的核心优化点也是很多初学者最容易写错的地方。正确做法当outStack为空时把inStack里的所有元素一次性全部倒入outStack完成一次顺序反转。 迁移完成后outStack 栈顶就是队头后续的 pop/peek 直接操作它就行。为什么 outStack 不为空时绝对不能迁移举个反例就很清楚假设 outStack 里已经有1、2、3栈顶是 1说明当前队头顺序是1 → 2 → 3。此时又 push 了4、5新元素进入 inStack。 逻辑上完整的队列应该是1 → 2 → 3 → 4 → 5。如果这时候为了“统一存放”把 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); }三步逻辑先判空两个栈都为空才是空队列再判断 outStack为空就整体迁移不为空就跳过直接返回 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用完再倒回去。 这样既浪费性能也完全没有必要。我们用一个完整流程看一遍push 1、2、3、4 → inStack: [1,2,3,4]outStack: 空第一次 pop → 触发迁移outStack 变成 [4,3,2,1]栈顶是1弹出1第二次 pop → outStack 不为空直接弹出2第三次 pop → 直接弹出3直到 outStack 彻底清空之前都不需要再碰 inStack。 也就是说一个元素从进入队列到离开最多只会被迁移一次push 进 inStack ↓ 最多迁移一次到 outStack ↓ 从 outStack 弹出绝不会出现in → out → in → out来回倒的情况。这就是双栈方案高效的根本原因。八、摊还 O(1) 到底是什么意思这是本题最值得理解的概念也是面试常考点。有人会质疑迁移的时候要移动 N 个元素明明是 O(N)为什么说 O(1) 答案是单次最坏是 O(N)但从一长串操作的整体平均来看每个操作的成本是常数级。我们从两个角度理解角度1单个元素的生命周期一个元素完整的一生只有四步压入 inStack → O(1)弹出 inStack → O(1)压入 outStack → O(1)弹出 outStack → O(1)每一步都是 O(1)而且每个元素最多只会被迁移一次不会反复搬运。 所以对于单个元素来说总开销是固定常数。角度2N 个元素的整体视角假设一共入队 N 个元素执行 N 次出队。所有迁移操作加起来最多处理 N 个元素所有入队、出队操作加起来也处理 N 个元素整个序列的总代价是 O(N)平均分摊到 N 次操作上O(N) / N O(1)这就是摊还时间复杂度 O(1)。注意摊还 O(1) 不代表每一次操作都是严格 O(1)。 某一次触发大规模迁移的 pop/peek 仍然可能是 O(N)但从整体平均来看每个操作的成本是常数级。九、各接口复杂度总结操作单次最坏时间复杂度摊还时间复杂度pushO(1)O(1)peekO(N)O(1)popO(N)O(1)emptyO(1)O(1)空间复杂度O(N)。 两个栈并不意味着两份数据同一时间 N 个元素只会存在于其中一个栈里只是在两个容器之间迁移。十、横向对比和另外两道经典题的区别10.1 对比 225用队列实现栈两道题看似对称迁移策略差异很大对比项225 用队列实现栈232 用栈实现队列底层结构两个队列两个栈目标特性LIFOFIFO核心策略前 N-1 个元素搬到另一个队列inStack 按需整体倒入 outStack搬运特点每次 pop/top 都可能搬运同一元素最多迁移一次pushO(1)O(1)popO(N)摊还 O(1)top/peekO(N)摊还 O(1)两道题本质都是利用底层结构的顺序特性重新组织元素的访问顺序但 232 的“输入栈 输出栈”分工更加稳定因此能做出摊还优化。10.2 对比 622循环数组队列上一篇的循环队列和本篇双栈队列都实现了 FIFO但侧重点完全不同对比项循环数组队列双栈模拟队列底层结构连续数组两个栈核心思想环形复用空间两次反转顺序FrontO(1)摊还 O(1)RearO(1)纯栈接口下不自然容量创建时固定动态增长考察重点front/rear、取模、空满区分双栈分工、按需迁移、摊还分析简单总结就是需要频繁访问队尾、固定容量缓冲选循环数组只需要标准队列操作、想复用栈模块选双栈。十一、工程化落地栈代码的复用与本次文件结构这道题最直观的工程价值就是可以直接复用已经写好的栈代码。前面我们已经完整实现过动态顺序栈的全套接口到这里不需要再从零手写一遍数组、top、扩容逻辑直接拿过来组合就能实现队列。本次提交到 Git 的版本采用三文件结构queue232.h头文件统一存放栈结构体、队列结构体以及全部对外接口的声明queue232.c核心实现文件包含完整的栈函数实现 双栈队列实现栈逻辑直接复用之前的成熟代码test.c本地测试文件覆盖入队、出队、取队头、判空等核心场景这种组织方式既保证了栈逻辑的复用又维持了单题文件结构的简洁不需要为了一道题额外拆分多层目录。队列层完全通过栈的标准接口操作底层不直接触碰数组和下标也体现了「上层依赖接口、不依赖底层实现」的思路。代码仓库数据结构/8.20 LeetCode 232.用栈实现队列 · Luminous/Code_2026 - 码云 - 开源中国写在最后LeetCode 232 的代码其实非常短真正决定理解深度的从来不是能不能记住那一行if (StackEmpty(obj-outStack)) transfer(obj);。而是能不能回答两个问题为什么只有 outStack 为空时才能迁移明明一次迁移可能移动 N 个元素为什么整体是摊还 O(1)把这两个问题想明白双栈队列就不再是一个需要背的模板而是一套可以推导出来的设计。从顺序栈、链式队列到 225 两队列模拟栈、622 数组循环队列再到今天的 232 两栈模拟队列栈和队列的关系已经非常清晰 它们不只是两个需要背接口的数据结构而是可以通过顺序反转、数据搬运和状态维护互相模拟、互相组合的基础单元。到这里栈和队列专题的三道核心结构题就全部串起来了。 下一篇我们会正式开启新的专题进入二叉树的内容当然栈和队列的经典应用题 —— 比如括号匹配、单调栈、BFS 广度优先搜索等等后面也会结合对应题目继续练习不会就此停下。基础结构是工具最终还是要落到具体问题里去发挥作用。