文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载导读「用队列实现栈」是 LeetCode 上经典的数据结构模拟题也是面试中高频考察的栈/队列互相模拟问题。本篇以 InterviewGuide 仓库中 225. 用队列实现栈 的题解为主体完整保留阿秀的 C 双队列实现并在此基础上补充算法原理、逐操作推演、复杂度分析与单队列优化方案。读完本篇你将掌握用队列模拟栈的标准套路并能举一反三地应对同类面试题。一、题目背景与考点1.1 为什么面试官爱考这道题栈Stack与队列Queue是两种完全相反的线性数据结构栈后进先出LIFO元素从同一端栈顶进、出队列先进先出FIFO元素从队尾进、从队首出。面试官通过这道题考察的正是你对两种数据结构本质差异的理解以及如何用受限的数据结构队列去模拟另一种数据结构的语义。本题在 InterviewGuide 中被归类于 精选力扣 300 道算法题之栈 分类下的 Easy 等级是栈专题入门必刷题之一。1.2 本题在栈专题中的定位在 07-栈/easy 目录下本题与 155. 最小栈用栈模拟栈 常数时间取最小、682. 棒球比赛、1047. 删除字符串中的所有相邻重复项 等共同构成栈的入门训练组而「用队列实现栈」恰好与栈专题中的 946. 验证栈序列 形成数据结构互操作的知识闭环。二、题目描述与约束条件题目要求使用队列实现栈的下列操作push(x)-- 元素 x 入栈pop()-- 移除栈顶元素top()-- 获取栈顶元素empty()-- 返回栈是否为空注意你只能使用队列的基本操作——也就是push to back、peek/pop from front、size和is empty这些操作是合法的你所使用的语言也许不支持队列你可以使用list或者deque双端队列来模拟一个队列只要是标准的队列操作即可你可以假设所有操作都是有效的例如对一个空的栈不会调用pop或者top操作。第三条约束非常关键它让我们在实现pop()和top()时无需处理空栈的边界情况代码可以更简洁。但作为严谨的工程实践本文仍会讨论空栈场景下需要注意的细节。三、核心思路队列与栈的本质差异队列是 FIFO栈是 LIFO。要让队列模拟出后进先出的效果核心矛盾在于队尾进入的元素正常情况下应该最先被弹出FIFO但栈却要求它最后被弹出。解决思路有两条主线思路策略代价双队列法本题解用第二个队列做中转站pop时把队尾元素以外的所有元素临时搬走pop变慢push保持 O(1)单队列法优化方案push时立即把新元素旋转到队首让队首永远等价于栈顶push变慢pop/top均为 O(1)两条主线各有取舍核心都是利用一次整体搬移/旋转来逆转元素的相对出队顺序。四、解法一双队列法原文档题解这是 225.用队列实现栈 原文档给出的第一版解法思路直白用一个主队列in存储数据用辅助队列out在弹出时充当缓冲区。4.1 完整代码阿秀原版class MyStack { public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { in.push(x); } /** Removes the element on top of the stack and returns that element. */ int pop() { while (in.size()1) { out.push(in.front()); in.pop(); } int iin.front(); in.pop(); while (!out.empty()) { in.push(out.front()); out.pop(); } return i; } /** Get the top element. */ int top() { return in.back(); } /** Returns whether the stack is empty. */ bool empty() { return in.empty() out.empty(); } private: queueint in; queueint out; };原文档记录的提交表现执行用时 4 ms击败 73.27% 的 C 提交内存消耗 9 MB击败 23.13% 的 C 提交。这里需要说明该数据是当时提交时的快照统计仅作参考实际表现随 LeetCode 评测机与用例集的变化会有波动。4.2 逐操作推演push(x)入栈直接把x压入主队列in的队尾时间复杂度 O(1)。in的队尾就是栈顶队首就是栈底。pop()出栈核心操作出栈要求弹出最后入栈的元素也就是in的队尾元素。但队列只能从队首弹出于是分三步走搬移while (in.size()1)将in中除队尾元素外的所有元素依次弹出并压入辅助队列out注意原顺序不变弹出此时in中只剩一个元素——也就是栈顶元素int i in.front(); in.pop();将其弹出并保存回迁while (!out.empty())将out中的元素按原顺序全部搬回in保证主队列数据完整、顺序不变。以入栈序列1 → 2 → 3为例初始 in: [1,2,3]队首 1队尾 3栈顶 3 pop(): 搬移后 in: [3]out: [1,2] 弹出 3返回 3 回迁后 in: [1,2]队尾 2新的栈顶 2每一次pop()的时间复杂度为 O(n)n 为栈内元素个数因为需要搬移n-1个元素再搬回。top()获取栈顶这里直接return in.back();。C 标准库的std::queue是容器适配器底层默认基于deque实现除了标准的push/pop/front之外还额外提供了back()方法返回队尾元素引用。由于入栈元素始终追加在in队尾且pop()之后剩余元素相对顺序不变in的队尾元素永远就是最后入栈的栈顶元素因此top()可以做到 O(1)。empty()判空return in.empty() out.empty();。理论上每次pop()结束时out都已被清空只判断in.empty()即可同时判断out属于防御性写法保证在任何状态下判空结果都正确时间复杂度 O(1)。4.3 复杂度总结双队列法操作时间复杂度说明push(x)O(1)直接入队pop()O(n)搬移 n-1 个元素 弹出一个 搬回 n-1 个元素top()O(1)直接返回队尾元素empty()O(1)判空空间复杂度O(n)两个队列合计存储全部元素从源码结构看该实现有一个值得注意的特点out队列只承担临时中转职责任何时刻都不保存数据因此空间上并没有因为双队列而翻倍仍是 O(n)。五、解法二单队列法push 时旋转双队列法让pop变慢了。如果我们换一个角度在push的时候就把新元素旋转到队首让队列的队首永远等价于栈顶那么pop/top都能回到 O(1)。这一版本不需要第二个队列仅靠一个队列的弹出-重新入队即可完成。class MyStack { public: /** Initialize your data structure here. */ MyStack() { } /** Push element x onto stack. */ void push(int x) { q.push(x); // 将新元素之前的 size-1 个元素依次从队首弹出并重新压回队尾 // 旋转完成后x 位于队首等价于栈顶 for (int i 0; i q.size() - 1; i) { q.push(q.front()); q.pop(); } } /** Removes the element on top of the stack and returns that element. */ int pop() { int x q.front(); // 队首即栈顶 q.pop(); return x; } /** Get the top element. */ int top() { return q.front(); // 队首即栈顶 } /** Returns whether the stack is empty. */ bool empty() { return q.empty(); } private: queueint q; };执行过程示例入栈1 → 2 → 3push(1): q[1] push(2): q[1,2]旋转 1 次 - [2,1]队首 2 即栈顶 push(3): q[2,1,3]旋转 2 次 - [3,2,1]队首 3 即栈顶 pop(): 返回并弹出队首 3 - [2,1]新的栈顶 2复杂度对比操作双队列法单队列法push(x)O(1)O(n)旋转 n-1 个元素pop()O(n)O(1)top()O(1)O(1)empty()O(1)O(1)空间O(n)O(n)两种方法本质上都是用一次 O(n) 的搬移/旋转换取另一种操作的 O(1)。如果业务场景中入栈频繁、出栈稀疏双队列法更优如果出栈频繁、入栈稀疏单队列法更优。面试时能主动对比这两种取舍是加分项。六、实现细节与易错点top()的in.back()依赖语言特性原解法之所以能用 O(1) 实现top()是因为 C 的std::queue提供了back()。如果面试语言是只提供push/pop/front的纯队列接口如部分语言的标准队列就需要通过弹出全部元素并记录队尾元素再恢复的方式模拟top()代价会变成 O(n)。这一点可以结合 155. 最小栈 中双栈同步保存状态的思路来体会数据结构模拟题的通用套路。out队列必须保持为空双队列法的正确性建立在每次pop()结束后out被清空这一不变量上。如果某次pop()执行到一半被中断现实中不会但思维上要保证out残留数据会导致后续行为错乱。空栈边界题目保证不会对空栈调用pop/top所以原代码没有判空。实际工程中建议在pop()/top()前增加if (empty())的防护避免queue::front()在空队列上调用引发未定义行为。关于只能用队列基本操作的约束注意题目允许使用list或deque模拟队列但不允许直接使用栈语义。也就是说不能用vector的push_back/pop_back偷懒必须严格通过队首出、队尾进的语义来实现。七、举一反三姊妹题与知识闭环在 InterviewGuide 的栈专题中与本题形成闭环的题目还有155. 最小栈用辅助栈同步记录当前最小值与本题用辅助队列做中转是同一类主结构 辅助结构的组合模式946. 验证栈序列考察栈的 push/pop 过程模拟与本题一样要求精确理解什么时刻该 pop、什么时刻该 push1047. 删除字符串中的所有相邻重复项与844. 比较含退格的字符串利用栈只能操作一端的特性做字符串处理是栈应用的常见变体。更进阶的姊妹题是232. 用栈实现队列方向相反用两个栈模拟先进先出它采用双栈 倒水的思路入队时压入in栈出队时若out栈为空则把in全部倒入out再从out弹出。理解了用队列实现栈后反向模拟题可以顺手攻克。全部栈专题题目清单及难度分级可参见 07-栈/introduce.md本专题的 Easy 级题解合集含 155、225、682、844、1047汇总于 total/07-栈/easy/easy.md适合集中刷题复盘。八、总结「225. 用队列实现栈」是一道典型的数据结构互模拟题目核心收获有三点理解本质栈的 LIFO 与队列的 FIFO 对立必须通过搬移/旋转来逆转出队顺序掌握套路双队列法中转搬移pop慢与单队列法push旋转push慢是两种标准答案要能讲清各自的复杂度取舍注意细节top()的 O(1) 实现依赖 Cqueue::back()跨语言时要意识到接口差异空栈防护与辅助结构的不变量是保证正确性的关键。无论校招还是社招面试能流畅写出双队列版本并主动补充单队列方案的候选人通常都能在栈与队列这一轮考察中顺利过关。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐LeetCode 225 题解用队列实现栈Implement Stack using Queues——Go 双队列实现与测试解析LeetCode 225 题解用队列实现栈Implement Stack using Queues——Go 双队列实现与测试解析 导读 本篇围绕 Leet示例工程用队列实现栈LeetCode 225双队列模拟 LIFO 的完整设计与复杂度分析用队列实现栈LeetCode 225双队列模拟 LIFO 的完整设计与复杂度分析 本文基于「算法通关手册」 0225. 用队列实现栈题解 https://教程文档知识库用队列实现栈三种解法与多语言实现深度剖析LeetCode 225 题用队列实现栈三种解法与多语言实现深度剖析LeetCode 225 题 本文围绕 LeetCode 225「用队列实现栈」展开系统讲解双队列、单队列、队列示例工程教程上一篇Gqrx完全指南15分钟快速上手开源SDR接收器免费收听全球无线电下一篇Orleans集成测试最佳实践环境隔离与数据清理创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考