【LeetCode刷题日记】23：用栈实现队列

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要本文介绍如何使用两个栈实现队列功能。通过维护输入栈(stackIn)和输出栈(stackOut)在push操作时直接压入输入栈pop/peek操作时若输出栈为空则将输入栈元素全部转移至输出栈从而实现队列的先进先出特性。关键点在于延迟倒腾策略保证每个元素只被转移一次使操作均摊时间复杂度为O(1)。文章包含完整Java实现代码展示了push、pop、peek和empty等核心方法的实现逻辑。题目背景LeetCode232可直达使用栈实现队列的下列操作push(x) -- 将一个元素放入队列的尾部。pop() -- 从队列首部移除元素。peek() -- 返回队列首部的元素。empty() -- 返回队列是否为空。示例:MyQueue queue new MyQueue(); queue.push(1); queue.push(2); queue.peek(); // 返回 1 queue.pop(); // 返回 1 queue.empty(); // 返回 false说明:你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。你所使用的语言也许不支持栈。你可以使用 list 或者 deque双端队列来模拟一个栈只要是标准的栈操作即可。假设所有操作都是有效的 例如一个空的队列不会调用 pop 或者 peek 操作题目解析这道题目是最基础的栈的灵活应用我们要用栈去实现队列我们已经知道栈是先进后出而队列是先进先出使用栈来模拟队列的行为如果仅仅用一个栈是一定不行的所以需要两个栈一个输入栈一个输出栈这里要注意输入栈和输出栈的关系。如图所示我们的输入栈和输出栈实现的就是这个效果在push数据的时候只要数据放进输入栈就好但在pop的时候操作就复杂一些输出栈如果为空就把进栈数据全部导入进来注意是全部导入再从出栈弹出数据如果输出栈不为空则直接从出栈弹出数据就可以了。最后如何判断队列为空呢如果进栈和出栈都为空的话说明模拟的队列为空了。优点高效每个元素只倒腾一次均摊 O(1)延迟倒腾只有在stackOut为空时才倒腾避免频繁操作简单可靠逻辑清晰不易出错栈职责操作stackIn负责入队只做push元素都先放这里stackOut负责出队只做pop和peek元素从这里出去对比直接用栈的缺点如果每次pop都把stackIn全部倒出来再倒回去时间复杂度就是 O(n)这种延迟倒腾的设计避免了这个问题。【队列状态】 队首 ←─────────── 队尾 1 2 3 【两个栈的存储】 stackIn: [1, 2, 3] ← 3是栈顶后进 ↓ 倒腾 stackOut: [3, 2, 1] ← 1是栈顶先出 【操作流程】 push(1) → push(2) → push(3) stackIn: 1,2,3 ↓ peek() / pop() → dumpstackIn() stackIn倒进stackOut ↓ stackOut: 3,2,1 ↓ pop() → 1 ✅ 先进先出用两个栈模拟队列stackIn负责收元素stackOut负责出元素只有当stackOut为空时才把stackIn的全部倒进去这样就能把栈的 LIFO 变成队列的 FIFO。题目答案class MyQueue { StackInteger stackIn; StackInteger stackOut; /** Initialize your data structure here. */ public MyQueue() { stackIn new Stack(); // 负责进栈 stackOut new Stack(); // 负责出栈 } /** Push element x to the back of queue. */ public void push(int x) { stackIn.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { dumpstackIn(); return stackOut.pop(); } /** Get the front element. */ public int peek() { dumpstackIn(); return stackOut.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stackIn.isEmpty() stackOut.isEmpty(); } // 如果stackOut为空那么将stackIn中的元素全部放到stackOut中 private void dumpstackIn(){ if (!stackOut.isEmpty()) return; while (!stackIn.isEmpty()){ stackOut.push(stackIn.pop()); } } }结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励