尧图网页设计 
LeetCode 225 题解用队列实现栈Implement Stack using Queues——Go 双队列实现与测试解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 225 题“用队列实现栈”展开结合 LeetCode-Go 仓库中leetcode/0225.Implement-Stack-using-Queues目录下的完整 Go 实现与单元测试讲解如何仅借助队列的标准操作入队、出队、取队首、判空、求长度模拟出栈的 LIFO 语义。读完本文你将掌握双队列法实现push/pop/top/empty四个接口的完整代码、时间复杂度推导以及如何用 Go 自带的go test验证该实现的正确性。题目原文与要求题目要求使用队列实现栈的如下操作原题见 leetcode/0225.Implement-Stack-using-Queues/README.mdpush(x)—— 将元素 x 压入栈顶pop()—— 移除并返回栈顶元素top()—— 获取栈顶元素empty()—— 返回栈是否为空。题目给出的示例调用序列为MyStack stack new MyStack(); stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false题目同时给出了三条关键约束Note只能使用队列的标准操作即push to back从队尾入队、peek/pop from front从队首查看/出队、size求长度和is empty判空某些语言可能不原生支持队列可以用 list 或 deque双端队列模拟队列但只能使用队列的标准操作可以假设所有操作都是合法的即不会对空栈调用pop或top。题目大意题目要求用队列实现一个栈的基本操作push(x)、pop()、top()、empty()。核心难点在于队列是FIFO先进先出而栈是LIFO后进先出二者出队/出栈顺序相反必须通过某种搬移策略把队尾元素变成栈顶。解题思路双队列实现法按照题目要求实现即可本仓库采用经典的双队列方案。核心思想是维护两个队列主队列enque始终保存栈中元素并且保证队尾元素就是栈顶元素辅助队列deque在pop/top时临时承接从主队列倒腾出来的元素。当需要弹出栈顶即主队列队尾元素时先把主队列中除队尾以外的所有元素依次出队并入辅助队列此时主队列剩下的唯一元素就是栈顶弹出该元素后把辅助队列升格为主队列并将辅助队列置空等待下一次搬移。这样一轮操作之后栈的剩余元素仍然完整地保存在主队列中且顺序满足队尾即栈顶的约定。为什么能用两个队列模拟栈因为题目允许使用 list 或 deque 模拟队列所以仓库实现直接用两个[]int切片充当队列只使用切片的append相当于队尾入队和slice[1:]截取相当于队首出队这两个标准操作完全满足题目的约束条件。完整源码解析本仓库的实现位于 225. Implement Stack using Queues.go完整代码如下package leetcode type MyStack struct { enque []int deque []int } /** Initialize your data structure here. */ func Constructor225() MyStack { return MyStack{[]int{}, []int{}} } /** Push element x onto stack. */ func (this *MyStack) Push(x int) { this.enque append(this.enque, x) } /** Removes the element on top of the stack and returns that element. */ func (this *MyStack) Pop() int { length : len(this.enque) for i : 0; i length-1; i { this.deque append(this.deque, this.enque[0]) this.enque this.enque[1:] } topEle : this.enque[0] this.enque this.deque this.deque nil return topEle } /** Get the top element. */ func (this *MyStack) Top() int { topEle : this.Pop() this.enque append(this.enque, topEle) return topEle } /** Returns whether the stack is empty. */ func (this *MyStack) Empty() bool { if len(this.enque) 0 { return true } return false }数据结构设计type MyStack struct { enque []int deque []int }enque是主队列deque是辅助队列。两个字段都是[]int切片利用切片天然支持从尾部追加与从头部截取的特性来模拟队列操作入队队尾append(q, x)出队队首q[0]取值后q q[1:]截断求长度len(q)判空len(q) 0。构造函数Constructor225()返回一个两个队列均为空切片的MyStack。命名后缀225是为了与 LeetCode 题号对应避免与同包内其他题目定义的Constructor冲突。push直接入主队列func (this *MyStack) Push(x int) { this.enque append(this.enque, x) }push是最简单的操作把新元素追加到主队列enque的队尾即可时间复杂度 O(1)。由于我们约定队尾即栈顶新压入的元素天然处于队尾正好对应栈顶位置。pop搬移除队尾外的所有元素func (this *MyStack) Pop() int { length : len(this.enque) for i : 0; i length-1; i { this.deque append(this.deque, this.enque[0]) this.enque this.enque[1:] } topEle : this.enque[0] this.enque this.deque this.deque nil return topEle }pop是双队列法的核心分四步记录主队列当前长度length循环length-1次把主队列队首元素依次弹出并追加到辅助队列deque队尾同时用this.enque this.enque[1:]从主队列头部截断。循环结束后主队列恰好只剩一个元素它就是队尾元素即栈顶取出栈顶元素topEle : this.enque[0]把辅助队列赋给主队列this.enque this.deque此时栈内剩余元素按原顺序保留随后将deque置空this.deque nil准备下一轮搬移。最后返回topEle。由于每次pop需要把主队列中除队尾外的全部元素搬移一遍时间复杂度为 O(n)其中 n 为栈中元素个数。top复用 pop 再把栈顶压回func (this *MyStack) Top() int { topEle : this.Pop() this.enque append(this.enque, topEle) return topEle }top的巧妙之处在于直接复用了Pop()先弹出栈顶元素再把该元素压回主队列队尾。由于弹出后主队列只剩栈顶元素将其追加回队尾后主队列重新满足队尾即栈顶的约定栈内容完全不变。因此top的时间复杂度同样是O(n)。empty判断主队列是否为空func (this *MyStack) Empty() bool { if len(this.enque) 0 { return true } return false }由于所有元素始终只保存在主队列enque中deque在每次pop后被置空push只操作enque所以只需判断len(this.enque) 0即可。该操作时间复杂度O(1)。各操作复杂度汇总操作平均/最坏时间复杂度空间复杂度push(x)O(1)O(1)切片扩容均摊pop()O(n)O(n)辅助队列临时存放top()O(n)O(n)empty()O(1)O(1)整体—O(n)两个队列合计存放全部元素可以看到本实现以pop/top的 O(n) 搬移成本换取了push的 O(1) 常数时间是入栈快、出栈慢的策略。另一种思路是入栈时搬移、出栈时直接取队首此时push为 O(n) 而pop/top为 O(1)两种方案可根据实际操作频率取舍。单元测试与运行验证仓库为本题提供了单元测试文件 225. Implement Stack using Queues_test.gopackage leetcode import ( fmt testing ) func Test_Problem225(t *testing.T) { obj : Constructor225() fmt.Printf(obj %v\n, obj) param5 : obj.Empty() fmt.Printf(param_5 %v\n, param5) obj.Push(2) fmt.Printf(obj %v\n, obj) obj.Push(10) fmt.Printf(obj %v\n, obj) param2 : obj.Pop() fmt.Printf(param_2 %v\n, param2) param3 : obj.Top() fmt.Printf(param_3 %v\n, param3) param4 : obj.Empty() fmt.Printf(param_4 %v\n, param4) }该测试覆盖了完整的生命周期Constructor225()构造空栈随后调用Empty()应返回true输出param_5 true依次Push(2)、Push(10)栈内元素从底到顶为[2, 10]Pop()返回栈顶10输出param_2 10弹出后栈内仅剩[2]Top()返回栈顶2且不删除元素输出param_3 2再次Empty()返回false输出param_4 false因为栈内还有元素2。运行方式与仓库其他题目一致先进入题目目录再执行测试cd leetcode/0225.Implement-Stack-using-Queues go test -v -run Test_Problem225 .-v会打印测试中的fmt.Printf输出读者可以直观对照每一步的预期结果。整个仓库通过 gotest.sh 中的go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...统一跑全部题目的测试并生成覆盖率报告项目描述中宣称的 100% test coverage 正是由这类逐题测试用例保障的。从源码结构看仓库中队列与栈的基础设施为帮助读者理解队列与栈两种数据结构的本质差异仓库在 structures 目录下提供了独立的通用实现可作对比参考structures/Queue.go 中Queue用nums []int实现Push追加到尾部、Pop从头部nums[0]取出并截断——这正是标准队列的 FIFO 语义structures/Stack.go 中Stack同样用nums []int实现Push追加到尾部、Pop从尾部nums[len(nums)-1]取出并截断——这是标准栈的 LIFO 语义。二者的唯一区别就在于Pop取头部还是取尾部这从侧面印证了本题用 FIFO 结构模拟 LIFO 行为必须引入额外搬移的根本原因。对应的测试 structures/Queue_test.go 与 structures/Stack_test.go 分别验证了先进先出与后进先出两种顺序队列按 0 到 99 的入队顺序出队栈则按 99 到 0 的逆序出栈。本题的MyStack实现正是把这种逆序出栈的需求通过双队列搬移在内部消化掉了。从源码结构看leetcode/0225.Implement-Stack-using-Queues/225. Implement Stack using Queues.go属于leetcode包package leetcode与仓库根目录 go.mod 声明的模块github.com/halfrost/LeetCode-Go下的其他题目实现保持一致所有题解按题号.题目名的目录组织方便按题检索。实现变体与延伸思考变体一入栈时搬移push 为 O(n)把搬移动作提前到push每次压栈时先把主队列所有元素搬到辅助队列把新元素放入空的主队列队首再把辅助队列元素搬回。此时push为 O(n)而pop/top/empty均为 O(1)。适合多读少写频繁top/pop的场景。变体二单队列实现更进阶的版本只用一个队列即可完成每次push时把新元素入队然后依次弹出队首元素并重新入队循环n-1次让新元素旋转到队首实现 O(n) 的push与 O(1) 的pop。本仓库选择双队列版本逻辑更直观也更贴合题目用队列实现栈的经典教学思路。关于top复用pop的边界讨论本实现的top()基于所有操作都是合法的这一前提题目 Note 第 3 条明确保证不会对空栈调用pop/top。因此top()调用Pop()时无需担心空切片越界。同理pop()中this.enque[0]的访问也依赖这一合法性保证这是实现可以保持简洁的前提条件。小结本题的解法核心是用两个队列模拟一个栈主队列保持队尾即栈顶的约定辅助队列在弹出时临时搬移元素本仓库实现中push为 O(1)pop/top为 O(n)empty为 O(1)整体空间复杂度 O(n)top通过复用pop再压回元素实现代码简洁且不破坏栈内容配套的 单元测试 完整覆盖了构造、判空、入栈、出栈、取栈顶的全流程可直接通过go test运行验证仓库 structures 目录下的Queue与Stack通用实现可作为理解 FIFO / LIFO 差异的最佳对照素材。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 LeetCode 225 题解：用队列实现栈（Implement Stack using Queues）——Go 双队列实现与测试解析
LeetCode 225 题解用队列实现栈Implement Stack using Queues——Go 双队列实现与测试解析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本篇围绕 LeetCode 225 题“用队列实现栈”展开结合 LeetCode-Go 仓库中leetcode/0225.Implement-Stack-using-Queues目录下的完整 Go 实现与单元测试讲解如何仅借助队列的标准操作入队、出队、取队首、判空、求长度模拟出栈的 LIFO 语义。读完本文你将掌握双队列法实现push/pop/top/empty四个接口的完整代码、时间复杂度推导以及如何用 Go 自带的go test验证该实现的正确性。题目原文与要求题目要求使用队列实现栈的如下操作原题见 leetcode/0225.Implement-Stack-using-Queues/README.mdpush(x)—— 将元素 x 压入栈顶pop()—— 移除并返回栈顶元素top()—— 获取栈顶元素empty()—— 返回栈是否为空。题目给出的示例调用序列为MyStack stack new MyStack(); stack.push(1); stack.push(2); stack.top(); // returns 2 stack.pop(); // returns 2 stack.empty(); // returns false题目同时给出了三条关键约束Note只能使用队列的标准操作即push to back从队尾入队、peek/pop from front从队首查看/出队、size求长度和is empty判空某些语言可能不原生支持队列可以用 list 或 deque双端队列模拟队列但只能使用队列的标准操作可以假设所有操作都是合法的即不会对空栈调用pop或top。题目大意题目要求用队列实现一个栈的基本操作push(x)、pop()、top()、empty()。核心难点在于队列是FIFO先进先出而栈是LIFO后进先出二者出队/出栈顺序相反必须通过某种搬移策略把队尾元素变成栈顶。解题思路双队列实现法按照题目要求实现即可本仓库采用经典的双队列方案。核心思想是维护两个队列主队列enque始终保存栈中元素并且保证队尾元素就是栈顶元素辅助队列deque在pop/top时临时承接从主队列倒腾出来的元素。当需要弹出栈顶即主队列队尾元素时先把主队列中除队尾以外的所有元素依次出队并入辅助队列此时主队列剩下的唯一元素就是栈顶弹出该元素后把辅助队列升格为主队列并将辅助队列置空等待下一次搬移。这样一轮操作之后栈的剩余元素仍然完整地保存在主队列中且顺序满足队尾即栈顶的约定。为什么能用两个队列模拟栈因为题目允许使用 list 或 deque 模拟队列所以仓库实现直接用两个[]int切片充当队列只使用切片的append相当于队尾入队和slice[1:]截取相当于队首出队这两个标准操作完全满足题目的约束条件。完整源码解析本仓库的实现位于 225. Implement Stack using Queues.go完整代码如下package leetcode type MyStack struct { enque []int deque []int } /** Initialize your data structure here. */ func Constructor225() MyStack { return MyStack{[]int{}, []int{}} } /** Push element x onto stack. */ func (this *MyStack) Push(x int) { this.enque append(this.enque, x) } /** Removes the element on top of the stack and returns that element. */ func (this *MyStack) Pop() int { length : len(this.enque) for i : 0; i length-1; i { this.deque append(this.deque, this.enque[0]) this.enque this.enque[1:] } topEle : this.enque[0] this.enque this.deque this.deque nil return topEle } /** Get the top element. */ func (this *MyStack) Top() int { topEle : this.Pop() this.enque append(this.enque, topEle) return topEle } /** Returns whether the stack is empty. */ func (this *MyStack) Empty() bool { if len(this.enque) 0 { return true } return false }数据结构设计type MyStack struct { enque []int deque []int }enque是主队列deque是辅助队列。两个字段都是[]int切片利用切片天然支持从尾部追加与从头部截取的特性来模拟队列操作入队队尾append(q, x)出队队首q[0]取值后q q[1:]截断求长度len(q)判空len(q) 0。构造函数Constructor225()返回一个两个队列均为空切片的MyStack。命名后缀225是为了与 LeetCode 题号对应避免与同包内其他题目定义的Constructor冲突。push直接入主队列func (this *MyStack) Push(x int) { this.enque append(this.enque, x) }push是最简单的操作把新元素追加到主队列enque的队尾即可时间复杂度 O(1)。由于我们约定队尾即栈顶新压入的元素天然处于队尾正好对应栈顶位置。pop搬移除队尾外的所有元素func (this *MyStack) Pop() int { length : len(this.enque) for i : 0; i length-1; i { this.deque append(this.deque, this.enque[0]) this.enque this.enque[1:] } topEle : this.enque[0] this.enque this.deque this.deque nil return topEle }pop是双队列法的核心分四步记录主队列当前长度length循环length-1次把主队列队首元素依次弹出并追加到辅助队列deque队尾同时用this.enque this.enque[1:]从主队列头部截断。循环结束后主队列恰好只剩一个元素它就是队尾元素即栈顶取出栈顶元素topEle : this.enque[0]把辅助队列赋给主队列this.enque this.deque此时栈内剩余元素按原顺序保留随后将deque置空this.deque nil准备下一轮搬移。最后返回topEle。由于每次pop需要把主队列中除队尾外的全部元素搬移一遍时间复杂度为 O(n)其中 n 为栈中元素个数。top复用 pop 再把栈顶压回func (this *MyStack) Top() int { topEle : this.Pop() this.enque append(this.enque, topEle) return topEle }top的巧妙之处在于直接复用了Pop()先弹出栈顶元素再把该元素压回主队列队尾。由于弹出后主队列只剩栈顶元素将其追加回队尾后主队列重新满足队尾即栈顶的约定栈内容完全不变。因此top的时间复杂度同样是O(n)。empty判断主队列是否为空func (this *MyStack) Empty() bool { if len(this.enque) 0 { return true } return false }由于所有元素始终只保存在主队列enque中deque在每次pop后被置空push只操作enque所以只需判断len(this.enque) 0即可。该操作时间复杂度O(1)。各操作复杂度汇总操作平均/最坏时间复杂度空间复杂度push(x)O(1)O(1)切片扩容均摊pop()O(n)O(n)辅助队列临时存放top()O(n)O(n)empty()O(1)O(1)整体—O(n)两个队列合计存放全部元素可以看到本实现以pop/top的 O(n) 搬移成本换取了push的 O(1) 常数时间是入栈快、出栈慢的策略。另一种思路是入栈时搬移、出栈时直接取队首此时push为 O(n) 而pop/top为 O(1)两种方案可根据实际操作频率取舍。单元测试与运行验证仓库为本题提供了单元测试文件 225. Implement Stack using Queues_test.gopackage leetcode import ( fmt testing ) func Test_Problem225(t *testing.T) { obj : Constructor225() fmt.Printf(obj %v\n, obj) param5 : obj.Empty() fmt.Printf(param_5 %v\n, param5) obj.Push(2) fmt.Printf(obj %v\n, obj) obj.Push(10) fmt.Printf(obj %v\n, obj) param2 : obj.Pop() fmt.Printf(param_2 %v\n, param2) param3 : obj.Top() fmt.Printf(param_3 %v\n, param3) param4 : obj.Empty() fmt.Printf(param_4 %v\n, param4) }该测试覆盖了完整的生命周期Constructor225()构造空栈随后调用Empty()应返回true输出param_5 true依次Push(2)、Push(10)栈内元素从底到顶为[2, 10]Pop()返回栈顶10输出param_2 10弹出后栈内仅剩[2]Top()返回栈顶2且不删除元素输出param_3 2再次Empty()返回false输出param_4 false因为栈内还有元素2。运行方式与仓库其他题目一致先进入题目目录再执行测试cd leetcode/0225.Implement-Stack-using-Queues go test -v -run Test_Problem225 .-v会打印测试中的fmt.Printf输出读者可以直观对照每一步的预期结果。整个仓库通过 gotest.sh 中的go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...统一跑全部题目的测试并生成覆盖率报告项目描述中宣称的 100% test coverage 正是由这类逐题测试用例保障的。从源码结构看仓库中队列与栈的基础设施为帮助读者理解队列与栈两种数据结构的本质差异仓库在 structures 目录下提供了独立的通用实现可作对比参考structures/Queue.go 中Queue用nums []int实现Push追加到尾部、Pop从头部nums[0]取出并截断——这正是标准队列的 FIFO 语义structures/Stack.go 中Stack同样用nums []int实现Push追加到尾部、Pop从尾部nums[len(nums)-1]取出并截断——这是标准栈的 LIFO 语义。二者的唯一区别就在于Pop取头部还是取尾部这从侧面印证了本题用 FIFO 结构模拟 LIFO 行为必须引入额外搬移的根本原因。对应的测试 structures/Queue_test.go 与 structures/Stack_test.go 分别验证了先进先出与后进先出两种顺序队列按 0 到 99 的入队顺序出队栈则按 99 到 0 的逆序出栈。本题的MyStack实现正是把这种逆序出栈的需求通过双队列搬移在内部消化掉了。从源码结构看leetcode/0225.Implement-Stack-using-Queues/225. Implement Stack using Queues.go属于leetcode包package leetcode与仓库根目录 go.mod 声明的模块github.com/halfrost/LeetCode-Go下的其他题目实现保持一致所有题解按题号.题目名的目录组织方便按题检索。实现变体与延伸思考变体一入栈时搬移push 为 O(n)把搬移动作提前到push每次压栈时先把主队列所有元素搬到辅助队列把新元素放入空的主队列队首再把辅助队列元素搬回。此时push为 O(n)而pop/top/empty均为 O(1)。适合多读少写频繁top/pop的场景。变体二单队列实现更进阶的版本只用一个队列即可完成每次push时把新元素入队然后依次弹出队首元素并重新入队循环n-1次让新元素旋转到队首实现 O(n) 的push与 O(1) 的pop。本仓库选择双队列版本逻辑更直观也更贴合题目用队列实现栈的经典教学思路。关于top复用pop的边界讨论本实现的top()基于所有操作都是合法的这一前提题目 Note 第 3 条明确保证不会对空栈调用pop/top。因此top()调用Pop()时无需担心空切片越界。同理pop()中this.enque[0]的访问也依赖这一合法性保证这是实现可以保持简洁的前提条件。小结本题的解法核心是用两个队列模拟一个栈主队列保持队尾即栈顶的约定辅助队列在弹出时临时搬移元素本仓库实现中push为 O(1)pop/top为 O(n)empty为 O(1)整体空间复杂度 O(n)top通过复用pop再压回元素实现代码简洁且不破坏栈内容配套的 单元测试 完整覆盖了构造、判空、入栈、出栈、取栈顶的全流程可直接通过go test运行验证仓库 structures 目录下的Queue与Stack通用实现可作为理解 FIFO / LIFO 差异的最佳对照素材。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考