LeetCode-Go 题解用双栈实现队列Implement Queue using StacksLeetCode 232【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文深入解析 LeetCode 232 题「用栈实现队列」核心思路是利用两个栈的负负得正特性将栈的后进先出LIFO顺序翻转成队列的先进先出FIFO顺序。文章以 leetcode/0232.Implement-Queue-using-Stacks/README.md 为基础结合本仓库 Go 源码与测试用例讲解双栈队列的完整实现、各操作的复杂度与边界条件并给出可复制运行的代码与验证方法。题目要求实现一个队列但底层只能使用栈的标准操作需要支持以下四个方法方法行为push(x)将元素 x 推入队列尾部pop()移除并返回队首元素peek()返回队首元素不移除empty()返回队列是否为空题目示例节选自 README.mdMyQueue queue new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false题目附有三条关键约束只能使用栈的标准操作即 push to top、peek/pop from top、size、is empty如果语言不原生支持栈可以用 list 或 deque双端队列模拟但同样只能用栈的标准操作可以假定所有操作都是合法的即不会对空队列调用pop()或peek()。解题思路双栈翻转顺序栈是后进先出队列是先进先出二者顺序正好相反。用两个栈各翻转一次顺序就会被纠正回来元素先压入输入栈再全部倒入输出栈此时输出栈顶恰好是原序列的队首。本仓库的实现位于 leetcode/0232.Implement-Queue-using-Stacks/232. Implement Queue using Stacks.go数据结构如下type MyQueue struct { Stack *[]int // 输入栈push 时元素先进这里 Queue *[]int // 输出栈元素倒过来后栈顶即队首 } /** Initialize your data structure here. */ func Constructor232() MyQueue { tmp1, tmp2 : []int{}, []int{} return MyQueue{Stack: tmp1, Queue: tmp2} }仓库中Stack输入栈与Queue输出栈都以*[]int的形式持有构造器Constructor232返回两个空切片。注意命名上的巧思名为Queue的字段其实是一个栈它承担逆序后存放元素的角色栈顶永远指向真正的队首。Push只进输入栈/** Push element x to the back of queue. */ func (this *MyQueue) Push(x int) { *this.Stack append(*this.Stack, x) }push是 O(1) 操作直接追加到输入栈顶即可无需搬运数据。核心辅助方法fromStackToQueue这是双栈解法的灵魂负责把输入栈整体倒进输出栈func (this *MyQueue) fromStackToQueue(s, q *[]int) { for len(*s) 0 { popped : (*s)[len(*s)-1] *s (*s)[:len(*s)-1] *q append(*q, popped) } }循环弹出输入栈栈顶并压入输出栈。经过这次搬运输入栈的栈底最早入队的元素会成为输出栈的栈顶。Pop 与 Peek惰性搬运/** Removes the element from in front of queue and returns that element. */ func (this *MyQueue) Pop() int { if len(*this.Queue) 0 { this.fromStackToQueue(this.Stack, this.Queue) } popped : (*this.Queue)[len(*this.Queue)-1] *this.Queue (*this.Queue)[:len(*this.Queue)-1] return popped } /** Get the front element. */ func (this *MyQueue) Peek() int { if len(*this.Queue) 0 { this.fromStackToQueue(this.Stack, this.Queue) } return (*this.Queue)[len(*this.Queue)-1] }两个方法都采用惰性搬运策略只有当输出栈为空时才触发fromStackToQueue将输入栈整体倒过来否则直接取输出栈栈顶。这样搬运成本被摊薄到多次操作上pop和peek均摊时间复杂度为 O(1)。Empty双栈同判/** Returns whether the queue is empty. */ func (this *MyQueue) Empty() bool { return len(*this.Stack)len(*this.Queue) 0 }注意empty()必须同时检查两个栈输入栈里可能还躺着尚未搬运的元素此时队列并不为空。复杂度分析操作时间复杂度说明pushO(1)仅追加到输入栈pop均摊 O(1)仅当输出栈为空时搬运每个元素至多被搬运一次peek均摊 O(1)同pop只读不弹emptyO(1)比较两个栈长度之和空间复杂度为 O(n)n 为队列中元素总数两个栈合计存放全部元素无额外开销。运行与验证仓库为该题提供了配套测试 leetcode/0232.Implement-Queue-using-Stacks/232. Implement Queue using Stacks_test.go覆盖主流程与输出栈为空时 Peek 触发搬运的边界场景func Test_Problem232(t *testing.T) { obj : Constructor232() fmt.Printf(obj %v\n, obj) obj.Push(2) obj.Push(10) param2 : obj.Pop() // 触发一次 fromStackToQueue返回 2 fmt.Printf(param_2 %v\n, param2) param3 : obj.Peek() // 输出栈非空直接取栈顶返回 10 fmt.Printf(param_3 %v\n, param3) param4 : obj.Empty() // false fmt.Printf(param_4 %v\n, param4) // Peek when the Queue is empty so it triggers fromStackToQueue. obj2 : Constructor232() obj2.Push(5) obj2.Push(7) peeked : obj2.Peek() // 输出栈为空触发搬运返回 5 if peeked ! 5 { t.Fatalf(Peek() %v, want %v, peeked, 5) } fmt.Printf(peeked %v\n, peeked) }测试覆盖了两个重要场景连续 Push 后首次 Popobj.Push(2); obj.Push(10)后第一次Pop()输出栈为空触发搬运弹出的是最早入队的 2验证 FIFO 语义输出栈为空时的 Peek显式注释说明Peek when the Queue is empty so it triggers fromStackToQueue并断言返回最早入队的 5验证惰性搬运在 Peek 路径上同样生效。在本仓库中运行该测试即可验证实现正确性go test -v ./leetcode/0232.Implement-Queue-using-Stacks/仓库根目录的 gotest.sh 还提供了全量测试脚本它会对./leetcode/...下所有题目一次性执行覆盖率测试并生成coverage.txt可用于确认整个题解集合含本题的测试状态。工程化细节为什么用指针持有切片实现中两个栈字段都声明为*[]int这是 Go 中修改切片时需要留意的点append可能触发底层数组扩容并返回新的切片头若字段直接持有[]int必须显式回写如this.Stack append(this.Stack, x)。本实现统一通过指针间接修改配合辅助方法fromStackToQueue(s, q *[]int)的指针参数确保每次弹栈、压栈、搬运后底层切片状态始终被正确回写逻辑清晰且不易遗漏。与仓库通用数据结构的关系本仓库在 structures 目录下提供了通用的 Stack.go 与 Queue.go 工具结构含Push、Pop、Len、IsEmpty方法。本题解出于只能使用栈的标准操作的题目约束直接在题解文件内以[]int模拟栈并自定义MyQueue类型未依赖通用结构——这也正是 LeetCode 在线评测的要求提交的必须是自包含、可直接运行的独立代码。读者可以对比通用实现与本题解理解栈的 peek/pop from top、size、is empty 标准操作在 Go 中分别对应slice[len-1]取值、slice[:len-1]截断与len()判断。小结LeetCode 232 是双栈模拟队列的经典题目核心要点可归纳为顺序翻转栈 LIFO 经过两次翻转得到 FIFO惰性搬运仅在输出栈为空时才整体倒数据实现均摊 O(1) 的pop/peek空判定empty()必须同时检查两个栈不能只看输出栈。掌握该模式后可顺带理解与之对应的用队列实现栈类问题以及双栈在其他场景如表达式求值、单调栈中的扩展用法是栈与队列互相模拟类面试题的最佳入门范本。【免费下载链接】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-Go 题解：用双栈实现队列（Implement Queue using Stacks，LeetCode 232）
LeetCode-Go 题解用双栈实现队列Implement Queue using StacksLeetCode 232【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本文深入解析 LeetCode 232 题「用栈实现队列」核心思路是利用两个栈的负负得正特性将栈的后进先出LIFO顺序翻转成队列的先进先出FIFO顺序。文章以 leetcode/0232.Implement-Queue-using-Stacks/README.md 为基础结合本仓库 Go 源码与测试用例讲解双栈队列的完整实现、各操作的复杂度与边界条件并给出可复制运行的代码与验证方法。题目要求实现一个队列但底层只能使用栈的标准操作需要支持以下四个方法方法行为push(x)将元素 x 推入队列尾部pop()移除并返回队首元素peek()返回队首元素不移除empty()返回队列是否为空题目示例节选自 README.mdMyQueue queue new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // returns 1 queue.pop(); // returns 1 queue.empty(); // returns false题目附有三条关键约束只能使用栈的标准操作即 push to top、peek/pop from top、size、is empty如果语言不原生支持栈可以用 list 或 deque双端队列模拟但同样只能用栈的标准操作可以假定所有操作都是合法的即不会对空队列调用pop()或peek()。解题思路双栈翻转顺序栈是后进先出队列是先进先出二者顺序正好相反。用两个栈各翻转一次顺序就会被纠正回来元素先压入输入栈再全部倒入输出栈此时输出栈顶恰好是原序列的队首。本仓库的实现位于 leetcode/0232.Implement-Queue-using-Stacks/232. Implement Queue using Stacks.go数据结构如下type MyQueue struct { Stack *[]int // 输入栈push 时元素先进这里 Queue *[]int // 输出栈元素倒过来后栈顶即队首 } /** Initialize your data structure here. */ func Constructor232() MyQueue { tmp1, tmp2 : []int{}, []int{} return MyQueue{Stack: tmp1, Queue: tmp2} }仓库中Stack输入栈与Queue输出栈都以*[]int的形式持有构造器Constructor232返回两个空切片。注意命名上的巧思名为Queue的字段其实是一个栈它承担逆序后存放元素的角色栈顶永远指向真正的队首。Push只进输入栈/** Push element x to the back of queue. */ func (this *MyQueue) Push(x int) { *this.Stack append(*this.Stack, x) }push是 O(1) 操作直接追加到输入栈顶即可无需搬运数据。核心辅助方法fromStackToQueue这是双栈解法的灵魂负责把输入栈整体倒进输出栈func (this *MyQueue) fromStackToQueue(s, q *[]int) { for len(*s) 0 { popped : (*s)[len(*s)-1] *s (*s)[:len(*s)-1] *q append(*q, popped) } }循环弹出输入栈栈顶并压入输出栈。经过这次搬运输入栈的栈底最早入队的元素会成为输出栈的栈顶。Pop 与 Peek惰性搬运/** Removes the element from in front of queue and returns that element. */ func (this *MyQueue) Pop() int { if len(*this.Queue) 0 { this.fromStackToQueue(this.Stack, this.Queue) } popped : (*this.Queue)[len(*this.Queue)-1] *this.Queue (*this.Queue)[:len(*this.Queue)-1] return popped } /** Get the front element. */ func (this *MyQueue) Peek() int { if len(*this.Queue) 0 { this.fromStackToQueue(this.Stack, this.Queue) } return (*this.Queue)[len(*this.Queue)-1] }两个方法都采用惰性搬运策略只有当输出栈为空时才触发fromStackToQueue将输入栈整体倒过来否则直接取输出栈栈顶。这样搬运成本被摊薄到多次操作上pop和peek均摊时间复杂度为 O(1)。Empty双栈同判/** Returns whether the queue is empty. */ func (this *MyQueue) Empty() bool { return len(*this.Stack)len(*this.Queue) 0 }注意empty()必须同时检查两个栈输入栈里可能还躺着尚未搬运的元素此时队列并不为空。复杂度分析操作时间复杂度说明pushO(1)仅追加到输入栈pop均摊 O(1)仅当输出栈为空时搬运每个元素至多被搬运一次peek均摊 O(1)同pop只读不弹emptyO(1)比较两个栈长度之和空间复杂度为 O(n)n 为队列中元素总数两个栈合计存放全部元素无额外开销。运行与验证仓库为该题提供了配套测试 leetcode/0232.Implement-Queue-using-Stacks/232. Implement Queue using Stacks_test.go覆盖主流程与输出栈为空时 Peek 触发搬运的边界场景func Test_Problem232(t *testing.T) { obj : Constructor232() fmt.Printf(obj %v\n, obj) obj.Push(2) obj.Push(10) param2 : obj.Pop() // 触发一次 fromStackToQueue返回 2 fmt.Printf(param_2 %v\n, param2) param3 : obj.Peek() // 输出栈非空直接取栈顶返回 10 fmt.Printf(param_3 %v\n, param3) param4 : obj.Empty() // false fmt.Printf(param_4 %v\n, param4) // Peek when the Queue is empty so it triggers fromStackToQueue. obj2 : Constructor232() obj2.Push(5) obj2.Push(7) peeked : obj2.Peek() // 输出栈为空触发搬运返回 5 if peeked ! 5 { t.Fatalf(Peek() %v, want %v, peeked, 5) } fmt.Printf(peeked %v\n, peeked) }测试覆盖了两个重要场景连续 Push 后首次 Popobj.Push(2); obj.Push(10)后第一次Pop()输出栈为空触发搬运弹出的是最早入队的 2验证 FIFO 语义输出栈为空时的 Peek显式注释说明Peek when the Queue is empty so it triggers fromStackToQueue并断言返回最早入队的 5验证惰性搬运在 Peek 路径上同样生效。在本仓库中运行该测试即可验证实现正确性go test -v ./leetcode/0232.Implement-Queue-using-Stacks/仓库根目录的 gotest.sh 还提供了全量测试脚本它会对./leetcode/...下所有题目一次性执行覆盖率测试并生成coverage.txt可用于确认整个题解集合含本题的测试状态。工程化细节为什么用指针持有切片实现中两个栈字段都声明为*[]int这是 Go 中修改切片时需要留意的点append可能触发底层数组扩容并返回新的切片头若字段直接持有[]int必须显式回写如this.Stack append(this.Stack, x)。本实现统一通过指针间接修改配合辅助方法fromStackToQueue(s, q *[]int)的指针参数确保每次弹栈、压栈、搬运后底层切片状态始终被正确回写逻辑清晰且不易遗漏。与仓库通用数据结构的关系本仓库在 structures 目录下提供了通用的 Stack.go 与 Queue.go 工具结构含Push、Pop、Len、IsEmpty方法。本题解出于只能使用栈的标准操作的题目约束直接在题解文件内以[]int模拟栈并自定义MyQueue类型未依赖通用结构——这也正是 LeetCode 在线评测的要求提交的必须是自包含、可直接运行的独立代码。读者可以对比通用实现与本题解理解栈的 peek/pop from top、size、is empty 标准操作在 Go 中分别对应slice[len-1]取值、slice[:len-1]截断与len()判断。小结LeetCode 232 是双栈模拟队列的经典题目核心要点可归纳为顺序翻转栈 LIFO 经过两次翻转得到 FIFO惰性搬运仅在输出栈为空时才整体倒数据实现均摊 O(1) 的pop/peek空判定empty()必须同时检查两个栈不能只看输出栈。掌握该模式后可顺带理解与之对应的用队列实现栈类问题以及双栈在其他场景如表达式求值、单调栈中的扩展用法是栈与队列互相模拟类面试题的最佳入门范本。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考