教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本文基于「算法通关手册」0225. 用队列实现栈题解 展开讲解如何仅使用两个队列及其标准操作模拟出后进先出LIFO的栈语义覆盖题目约束、双队列入栈反转法、完整可运行代码、复杂度分析与手工推演并结合仓库内顺序队列、循环队列、链式队列与双向队列的源码实现帮读者透彻理解这一经典的「数据结构互模拟」设计题。一、题目概述题目链接与分类题目编号0225. 用队列实现栈Implement Stack using Queues标签栈、设计、队列难度简单在「算法通关手册」中该题同时收录于 题解总览、题目分类列表 以及 面试 100 题 / 200 题清单属于面试高频的「数据结构设计」类题目。题目要求仅使用两个队列实现一个**后入先出LIFO**的栈并支持普通栈的四种操作void push(int x)将元素x压入栈顶int pop()移除并返回栈顶元素int top()返回栈顶元素不移除boolean empty()如果栈为空返回True否则返回False。要求实现MyStack类同时必须满足以下约束只能使用队列的基本操作即push to back队尾入队、peek/pop from front查看/弹出队头、size队列大小和is empty判空所使用的语言如果不原生支持队列可以使用list列表或deque双端队列来模拟队列只要走的是标准队列操作即可。本题在 LeetCode 上还允许「仅使用一个队列」的做法但题面标准约束为两个队列本文按题解的双队列方案展开单队列优化作为延伸思路在文末给出。示例输入 [MyStack, push, push, top, pop, empty] [[], [1], [2], [], [], []] 输出 [null, null, null, 2, 2, false] 解释 MyStack myStack new MyStack(); myStack.push(1); myStack.push(2); myStack.top(); // 返回 2 myStack.pop(); // 返回 2 myStack.empty(); // 返回 False从示例可以看出按push(1)、push(2)的顺序入栈后top()和pop()得到的都是最后压入的2这正是栈「后进先出」语义的体现——而队列本身是「先进先出FIFO」因此需要用两个队列做一次「翻转」。二、前置知识栈与队列的本质差异2.1 栈后进先出LIFO栈只允许在一端栈顶进行插入和删除最后放入栈的元素最先被取出。仓库教程 栈基础 给出了三种经典操作入栈Push在栈顶加入新元素出栈Pop移除并返回栈顶元素查看栈顶Peek只查看栈顶元素不移除。仓库中的顺序栈实现 用列表 栈顶指针top完成这三个操作入栈、出栈、查看栈顶均为O(1)。2.2 队列先进先出FIFO队列只允许在队尾插入元素入队在队头删除元素出队最先进入队列的元素最先被取出。仓库教程 队列基础 定义了两种基本操作入队enqueue在队尾插入元素出队dequeue从队头删除元素。队列有四种常见实现方式仓库中均有对应源码实现方式仓库源码特点顺序存储队列queue_sequential_queue.py数组实现队满后存在「假溢出」顺序存储循环队列queue_circularSequential_queue.py通过取模运算复用空间判满用(rear 1) % size front链式存储队列queue_link_queue.py单链表实现front/rear指针分别标记队头前驱与队尾双向队列dequequeue_deque.py支持队头/队尾双侧入出本题代码即基于它2.3 核心矛盾栈要求「后进先出」队列天然是「先进先出」。若只用一个队列push到队尾的元素永远最后才被pop出来这与栈顶先出的语义正好相反。解决办法是在入栈时就把元素顺序翻转——每次新元素入栈时让队列中已存在的元素整体后移使新元素始终占据队头这样队头即栈顶pop、top就退化为普通的队头操作。三、解题思路双队列法3.1 设计要点使用两个队列pushQueue用作入栈缓冲popQueue用作存储与出栈。push操作将新元素压入pushQueue再把popQueue中之前保存的元素从队头开始依次转移进pushQueue。转移完成后pushQueue的队头是新加入的元素队尾是之前的元素而popQueue变空随后交换pushQueue与popQueue的角色保持pushQueue为空、popQueue中存放全部元素。pop操作由于popQueue队头即栈顶直接取队头元素即可。top操作直接返回popQueue队头元素不移除。empty操作判断popQueue是否为空。3.2 为什么push后要交换交换动作的本质是「角色互换」。如果不交换下一次push时就需要判断新元素该进入哪个队列逻辑会复杂交换后可以保持不变量「pushQueue恒为空popQueue恒为当前栈的全部元素」使每次push的逻辑完全一致新元素入pushQueue此时它自己一个元素也是队头将popQueue全部元素依次搬到pushQueue队尾——由于popQueue的队头正是上一次的栈顶搬运后pushQueue的队头自然成为新栈顶交换两个队列的引用恢复不变量。3.3 代码实现import collections class MyStack: def __init__(self): Initialize your data structure here. self.pushQueue collections.deque() # 入栈缓冲队列约定恒为空 self.popQueue collections.deque() # 元素存储队列队头即栈顶 def push(self, x: int) - None: Push element x onto stack. self.pushQueue.append(x) # 新元素先进入缓冲队列 while self.popQueue: # 将旧元素整体搬到新元素之后 self.pushQueue.append(self.popQueue.popleft()) # 交换两个队列popQueue 重新持有全部元素pushQueue 恢复为空 self.pushQueue, self.popQueue self.popQueue, self.pushQueue def pop(self) - int: Removes the element on top of the stack and returns that element. return self.popQueue.popleft() # 队头即栈顶直接弹出 def top(self) - int: Get the top element. return self.popQueue[0] # 查看队头元素不移除 def empty(self) - bool: Returns whether the stack is empty. return not self.popQueue # popQueue 为空即栈为空 # Your MyStack object will be instantiated and called as such: # obj MyStack() # obj.push(x) # param_2 obj.pop() # param_3 obj.top() # param_4 obj.empty()代码说明使用collections.deque模拟队列append对应push to back队尾入队popleft对应pop from front队头出队popQueue[0]对应peek from front完全符合题目「只能用标准队列操作」的约束popQueue[0]是双向队列的下标访问若用list模拟队列则等价于popQueue[0]list 队头或queue[0]若题目要求「只能使用两个队列」之外的额外约束本实现不依赖任何非标准操作可直接提交。3.4 复杂度分析时间复杂度push每次需要把popQueue中已有元素逐个搬移若当前栈中已有n个元素则耗时O(n)pop直接弹出队头O(1)top直接查看队头O(1)emptyO(1)。空间复杂度两个队列合计保存全部元素O(n)。说明因为入栈是O(n)若连续执行n次push总代价为O(n²)单队列方案的入栈同样是O(n)但可以省去交换环节空间上只用一个队列。两种方案在最坏情况下的渐进复杂度相同。四、手工推演一次完整的调用序列以示例操作序列push(1) → push(2) → top() → pop() → empty()为例逐步推演push(1)pushQueue[1]popQueue为空无搬运交换后popQueue[1]pushQueue[]。push(2)pushQueue[2]把popQueue中的1搬到队尾得到pushQueue[2, 1]交换后popQueue[2, 1]队头是2pushQueue[]。top()返回popQueue[0]即2。pop()popleft()弹出2popQueue[1]。empty()popQueue非空返回False。可以看到关键一步发生在push(2)通过「新元素先入缓冲队旧元素整体搬到新元素之后」的搬运2始终位于队头从而pop、top都能以O(1)拿到栈顶。若再push(3)则执行pushQueue[3]搬运popQueue[1]得到[3, 1]交换后popQueue[3, 1]栈顶3依然在队头——不变量始终成立。五、仓库源码印证队列的底层实现本题代码依赖的是「标准队列操作」。仓库内提供了多套队列实现帮助理解deque背后到底发生了什么顺序队列queue_sequential_queue.pyenqueue将rear右移后写入dequeue将front右移后读出缺点是队满后即使前方有空位也无法复用即「假溢出」。循环队列queue_circularSequential_queue.py用取模运算(rear 1) % size与(front 1) % size让指针循环移动判空front rear、判满(rear 1) % size front空间利用率更高——这也是 03_03_queue_basic.md 中重点讲解的实现。链式队列queue_link_queue.pyenqueue在链表尾部追加节点并更新reardequeue取出front.next并前移front无需预先分配容量。双向队列queue_deque.py同时支持push_front/push_back/pop_front/pop_back本题代码选用的collections.deque正属此类其队头出队popleft均摊为O(1)因此双队列法中的搬运环节整体代价仍然可控。无论底层是数组、循环数组还是链表对MyStack而言都只需要「队尾入队、队头出队、查看队头、判空」四个能力这正是本题考察的抽象与接口设计用受限的数据结构组合出另一种数据结构的行为。六、姊妹题对照用栈实现队列0232本题与仓库内另一道经典设计题 0232. 用栈实现队列 互为镜像维度0225 用队列实现栈0232 用栈实现队列目标用 FIFO 模拟 LIFO用 LIFO 模拟 FIFO核心策略入栈时反转push 时搬运旧元素到新元素之后出队时反转inStack整体倒入outStack关键操作push为O(n)pop/top为O(1)push为O(1)pop/peek均摊O(1)空间复杂度O(n)O(n)0232 题的思路是push直接压入inStack当outStack为空时把inStack元素依次弹出压入outStack顺序恰好反转于是outStack栈顶即队列队头。它把「反转」延迟到出队时进行从而换来push的O(1)与pop、peek的均摊O(1)。两道题放在一起对比练习能更深刻地理解「何时反转」「在哪一端反转」这一设计决策。七、延伸思考单队列方案若允许只用一个队列push时先把元素入队再将队列前size - 1个元素依次出队并入队同样能让新元素滚到队头pop、top、empty逻辑不变。空间从两个队列降为一个但入栈仍为O(n)。均摊优化参考 0232 的思路是否能把「反转」从push挪到pop让入栈变成O(1)、出栈变为均摊O(1)在双队列模型下队列本身允许从队头窥视实现方式与双栈有所不同可作为进阶思考题。接口抽象价值本题的设计意义在于验证「任意具备标准队列操作的具体实现都能组合出栈的语义」无论底层是数组、循环数组、链表还是双向队列上层代码完全不用改动——这正是数据结构「逻辑结构」与「存储结构」分离思想的直观体现。相关资源本题题解docs/solutions/0200-0299/implement-stack-using-queues.md姊妹题0232. 用栈实现队列题解队列基础教程docs/03_stack_queue_hash_table/03_03_queue_basic.md栈基础教程docs/03_stack_queue_hash_table/03_01_stack_basic.md队列相关源码codes/python/03_stack_queue_hash_table/含顺序队列、循环队列、链式队列、双向队列与顺序栈实现题目分类与题解索引00_06_categories_list.md、00_05_solutions_list.md赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 225 题解用队列实现栈Implement Stack using Queues——Go 双队列实现与测试解析LeetCode 225 题解用队列实现栈Implement Stack using Queues——Go 双队列实现与测试解析 导读 本篇围绕 Leet示例工程用队列实现栈LeetCode 225单队列旋转法图解与 Java / JS / C 三语言实现用队列实现栈LeetCode 225单队列旋转法图解与 Java / JS / C 三语言实现 导读 本文基于 algorithm base http文档教程知识库用队列实现栈三种解法与多语言实现深度剖析LeetCode 225 题用队列实现栈三种解法与多语言实现深度剖析LeetCode 225 题 本文围绕 LeetCode 225「用队列实现栈」展开系统讲解双队列、单队列、队列示例工程教程上一篇【亲测免费】 数据探查利器Capital One的DataProfiler下一篇Laravel 法语语言包翻译缺口全景Passkeys、加密环境文件与 encoding 验证规则的 12 个待补条目创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考