示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载本文围绕《剑指 Offer第 2 版》面试题 09 展开完整讲解如何仅用栈LIFO这一数据结构模拟出队列FIFO的入队与出队语义并给出 doocs/leetcode 仓库中 Python3、Java、C、Go、TypeScript、Rust、JavaScript、C#、Swift 九种语言的实现细节。读完本文你不仅能透彻理解「双栈倒序」这一经典数据结构的组合技巧还能掌握其时间复杂度分析与边界处理为面试中同类「用受限数据结构实现另一数据结构」的题目如用两个队列实现栈、包含 min 函数的栈打下基础。题目背景与考点定位本题出自《剑指 Offer第 2 版》是栈与队列这对「语义相反」的数据结构最经典的组合题。题目要求实现一个队列类CQueue对外提供两个方法appendTail(value)在队列尾部插入整数deleteHead()在队列头部删除整数若队列为空则返回-1。其核心考点是数据结构语义的转换栈是后进先出LIFO队列是先进先出FIFO两者对元素的「取出顺序」完全相反。题目给出的约束是只能使用栈不能直接使用队列或链表因此必须通过两个栈的协作来「扭转」元素顺序。在 doocs/leetcode 仓库中本题收录于 lcof 系列目录标签为栈、设计难度为「简单」同系列还有面试题 30包含 min 函数的栈等同类「栈 设计」题型可作为练习延伸。题目描述与输入输出约定示例 1输入 [CQueue,appendTail,deleteHead,deleteHead] [[],[3],[],[]] 输出[null,null,3,-1]操作序列含义创建队列 → 尾部插入 3 → 删除头部得 3→ 再次删除头部队列已空返回 -1。示例 2输入 [CQueue,deleteHead,appendTail,appendTail,deleteHead,deleteHead] [[],[],[5],[2],[],[]] 输出[null,-1,null,null,5,2]操作序列含义创建队列 → 删除头部队列为空返回 -1→ 尾部插入 5 → 尾部插入 2 → 删除头部按 FIFO 应返回先入队的 5→ 删除头部返回 2。数据约束入队元素取值1 values 10000对appendTail、deleteHead的调用次数最多为10000次。从约束看本题不要求刻意优化常数但方法设计仍需保证在 10^4 次调用下整体高效这引出了下文「摊销 O(1)」的分析。解法思路为什么两个栈能实现队列核心直觉单个栈只能在一端栈顶操作天然是「后进先出」而队列需要在两端操作——尾部进、头部出。如果只用一个栈出队时拿到的永远是最后入队的元素顺序完全颠倒。破局点引入第二个栈把顺序「倒回来」。stk1负责接收入队元素appendTail直接压入stk1此时栈顶即队列尾部deleteHead出队时若stk2为空则把stk1中的元素逐个弹出并压入stk2——经过这一次倒序stk1栈底最先入队、队列头部的元素被翻转到stk2的栈顶之后每次出队直接从stk2弹出栈顶即可直至stk2被取空后再进行下一次批量倒序若两个栈均为空说明队列中没有元素返回-1。为什么正确栈的倒序操作相当于把「先进后出」抵消一次变成「先进先出」。入队顺序a, b, c压入stk1后栈内从上到下为c, b, a全部倒入stk2后stk2从上到下为a, b, c恰好恢复为入队顺序弹出时得到a最先入队者符合队列语义。关键性质每个元素至多被「进出」两次——一次压入stk1、一次从stk1转移到stk2、一次从stk2弹出。因此单次deleteHead虽在最坏情况下需要 O(n) 的搬运但摊还到每个元素上仍为 O(1)。多语言实现仓库源码逐一拆解以下实现与仓库 lcof/面试题09. 用两个栈实现队列 目录下的Solution.*文件一一对应可对照阅读。Python3对应 Solution.pyclass CQueue: def __init__(self): self.stk1 [] self.stk2 [] def appendTail(self, value: int) - None: self.stk1.append(value) def deleteHead(self) - int: if not self.stk2: while self.stk1: self.stk2.append(self.stk1.pop()) return -1 if not self.stk2 else self.stk2.pop() # Your CQueue object will be instantiated and called as such: # obj CQueue() # obj.appendTail(value) # param_2 obj.deleteHead()要点deleteHead中先检查stk2是否为空空时才触发搬运搬运后再次判空决定返回-1还是弹出栈顶。两行逻辑把「空队列」与「正常出队」两种分支合并处理。Java对应 Solution.javaclass CQueue { private DequeInteger stk1 new ArrayDeque(); private DequeInteger stk2 new ArrayDeque(); public CQueue() { } public void appendTail(int value) { stk1.push(value); } public int deleteHead() { if (stk2.isEmpty()) { while (!stk1.isEmpty()) { stk2.push(stk1.pop()); } } return stk2.isEmpty() ? -1 : stk2.pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj new CQueue(); * obj.appendTail(value); * int param_2 obj.deleteHead(); */要点使用ArrayDeque充当栈push/pop均为栈顶操作比java.util.Stack更推荐——Stack继承自Vector方法带synchronized且有历史包袱ArrayDeque底层为可扩容数组栈操作 O(1) 且无锁开销。C对应 Solution.cppclass CQueue { public: CQueue() { } void appendTail(int value) { stk1.push(value); } int deleteHead() { if (stk2.empty()) { while (!stk1.empty()) { stk2.push(stk1.top()); stk1.pop(); } } if (stk2.empty()) { return -1; } int ans stk2.top(); stk2.pop(); return ans; } private: stackint stk1, stk2; }; /** * Your CQueue object will be instantiated and called as such: * CQueue* obj new CQueue(); * obj-appendTail(value); * int param_2 obj-deleteHead(); */要点注意 C 的std::stack没有「查看并弹出」的一步操作需先top()取值再pop()弹出deleteHead中把空判断拆成两段先处理搬运再统一判空返回-1逻辑更清晰。Go对应 Solution.gotype CQueue struct { stk1, stk2 []int } func Constructor() CQueue { return CQueue{[]int{}, []int{}} } func (this *CQueue) AppendTail(value int) { this.stk1 append(this.stk1, value) } func (this *CQueue) DeleteHead() int { if len(this.stk2) 0 { for len(this.stk1) 0 { this.stk2 append(this.stk2, this.stk1[len(this.stk1)-1]) this.stk1 this.stk1[:len(this.stk1)-1] } } if len(this.stk2) 0 { return -1 } ans : this.stk2[len(this.stk2)-1] this.stk2 this.stk2[:len(this.stk2)-1] return ans } /** * Your CQueue object will be instantiated and called as such: * obj : Constructor(); * obj.AppendTail(value); * param_2 : obj.DeleteHead(); */要点Go 标准库没有专用栈类型用切片模拟——append压栈、取len-1处元素为栈顶、切片缩容[:len-1]实现弹栈。Constructor显式初始化两个空切片。TypeScript对应 Solution.tsclass CQueue { private stk1: number[]; private stk2: number[]; constructor() { this.stk1 []; this.stk2 []; } appendTail(value: number): void { this.stk1.push(value); } deleteHead(): number { if (this.stk2.length 0) { while (this.stk1.length) { this.stk2.push(this.stk1.pop()); } } return this.stk2.length 0 ? -1 : this.stk2.pop(); } } /** * Your CQueue object will be instantiated and called as such: * var obj new CQueue() * obj.appendTail(value) * var param_2 obj.deleteHead() */要点利用数组push/pop天然符合栈语义while (this.stk1.length)利用数值 0 的假值特性作为循环终止条件。Rust对应 Solution.rsstruct CQueue { s1: Veci32, s2: Veci32, } /** * self means the method takes an immutable reference. * If you need a mutable reference, change it to mut self instead. */ impl CQueue { fn new() - Self { CQueue { s1: Vec::new(), s2: Vec::new(), } } fn append_tail(mut self, value: i32) { self.s1.push(value); } fn delete_head(mut self) - i32 { match self.s2.pop() { Some(value) value, None { while !self.s1.is_empty() { self.s2.push(self.s1.pop().unwrap()); } self.s2.pop().unwrap_or(-1) } } } }要点Rust 版本借助Option的pop()返回值做模式匹配stk2非空直接取栈顶为空则先搬运再弹出并用unwrap_or(-1)优雅处理「搬运后仍为空」的情况全程无 panic 风险。JavaScript对应 Solution.jsvar CQueue function () { this.stk1 []; this.stk2 []; }; /** * param {number} value * return {void} */ CQueue.prototype.appendTail function (value) { this.stk1.push(value); }; /** * return {number} */ CQueue.prototype.deleteHead function () { if (!this.stk2.length) { while (this.stk1.length) { this.stk2.push(this.stk1.pop()); } } return this.stk2.length ? this.stk2.pop() : -1; }; /** * Your CQueue object will be instantiated and called as such: * var obj new CQueue() * obj.appendTail(value) * var param_2 obj.deleteHead() */要点采用构造函数 原型方法的写法与 LeetCode 判题器的实例化约定一致判空同样借助数组length的真假值。C#对应 Solution.cspublic class CQueue { private Stackint stk1 new Stackint(); private Stackint stk2 new Stackint(); public CQueue() { } public void AppendTail(int value) { stk1.Push(value); } public int DeleteHead() { if (stk2.Count 0) { while (stk1.Count ! 0) { stk2.Push(stk1.Pop()); } } return stk2.Count 0 ? -1 : stk2.Pop(); } } /** * Your CQueue object will be instantiated and called as such: * CQueue obj new CQueue(); * obj.AppendTail(value); * int param_2 obj.DeleteHead(); */要点直接使用 .NET 的Stackint泛型栈Push/Pop/Count语义清晰与题目描述一一对应。Swift对应 Solution.swiftclass CQueue { private var stk1: [Int] [] private var stk2: [Int] [] init() { } func appendTail(_ value: Int) { stk1.append(value) } func deleteHead() - Int { if stk2.isEmpty { while !stk1.isEmpty { stk2.append(stk1.removeLast()) } } return stk2.isEmpty ? -1 : stk2.removeLast() } } /** * Your CQueue object will be instantiated and called as such: * let obj CQueue(); * obj.appendTail(value); * let param_2 obj.DeleteHead(); */要点Swift 中数组的append/removeLast天然构成栈操作removeLast()返回被移除的元素与stk2.isEmpty判断配合即完成出队。边界条件与正确性论证实现虽短但有三个必须正确处理的分支连续出队直到stk2取空一旦stk2非空deleteHead必须直接弹stk2绝不能重复搬运stk1——否则会把已在stk2中排好序的元素重新打乱。stk2空但stk1非空此时才触发批量倒序倒序完成后stk2栈顶即队列头部。双栈皆空队列中无元素按题目约定返回-1与「合法的入队元素1 values 10000」相呼应-1不会与真实数据冲突。正确性的核心在于倒序操作的时机入队永远压入stk1出队永远来自stk2。stk1的栈顶方向是「新」stk2的栈顶方向是「旧」两者各自职责单一互不干扰。复杂度分析操作时间复杂度说明appendTailO(1)单次压栈无搬运deleteHeadO(n)最坏/ O(1)摊还仅当stk2为空且stk1非空时触发整体搬运耗时与stk1中元素数成正比每个元素至多被搬入stk2一次故摊还到每次操作上为 O(1)空间复杂度O(n)两个栈合计存储全部在队列中的元素n为队列中的元素个数理解摊还分析是本题的加分项虽然单次deleteHead可能触发 O(n) 的搬运但 10^4 次操作的总代价仍为 O(n) 级别每个元素进出栈共 3 次常数操作平均下来每次操作 O(1)。扩展同类题型的迁移思路双栈模拟队列的核心方法论「用两个语义相反的结构互相倒序抵消」可以推广到一系列题目用两个栈实现队列本题入栈栈 出栈栈出队时倒序用队列实现栈入队栈用普通队列出栈时把前 n-1 个元素轮转到队尾剩余队首即栈顶面试题 30 包含 min 函数的栈仓库同系列见 lcof/README.md用辅助栈记录历史最小值本质也是「主结构 辅助结构」协同。在 doocs/leetcode 仓库中这类「数据结构设计」题的完整题解均位于 solution 目录 与 lcof 目录 下同一题目通常配有README.md含思路讲解与多语言标签页和独立Solution.*源码文件便于对照学习。总结「用两个栈实现队列」是一道信息密度极高的经典面试题它同时考察对栈/队列语义的深刻理解、对操作时机的把握以及摊还复杂度的分析能力。doocs/leetcode 仓库 面试题 09 题解 提供了九种主流语言的完整实现读者可直接对照本文逐步推演「入栈 → 倒序 → 出栈」的完整数据流将这套方法论内化为解决数据结构设计类题目的通用武器。赞分享示例工程教程【免费下载链接】leetcodeLeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer第 2 版》、《程序员面试金典第 6 版》题解项目地址https://gitcode.com/doocs/leetcode点击查看免费下载相关推荐CS-Notes 剑指 Offer 题解用两个栈实现队列——Push/Pop 模拟与均摊 O(1) 复杂度解析CS Notes 剑指 Offer 题解用两个栈实现队列——Push/Pop 模拟与均摊 O 1 复杂度解析 本篇基于 CS Notes 仓库中《剑指 Off知识库文档教程InterviewGuide 剑指 Offer 刷题笔记No5 用两个栈实现队列——从朴素倒栈到 O(1) 摊还复杂度的双栈方案InterviewGuide 剑指 Offer 刷题笔记No5 用两个栈实现队列——从朴素倒栈到 O 1 摊还复杂度的双栈方案 本篇技术指南聚焦 Inte文档教程知识库InterviewGuide 剑指 Offer 第 5 题精讲用两个栈实现一个队列C 解法、边界分析与 STL 底层原理InterviewGuide 剑指 Offer 第 5 题精讲用两个栈实现一个队列C 解法、边界分析与 STL 底层原理 本篇是《带你快速刷完 67教程上一篇Zephyr RTOS蓝牙低功耗自动重连终极指南打造稳定BLE连接下一篇OLMo错误排查指南常见问题与解决方案创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考