《剑指 Offer》学习记录:题 9:用两个栈实现队列
2023-09-27 14:28:59 时间
题 9:用两个栈实现队列
题目:用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的功能。——《剑指 Offer》P68
解题思路
队列是先进先出的结构,将一系列的数据入队列后全部出队列,这些数据的顺序不会改变。栈是先进后出的结构,将一系列的数据入栈后全部出栈,这些数据将会逆序出栈。如果将这些逆序的数据再次全部入栈,然后全部出栈就可以恢复这些顺序原有的序列。借助 2 个栈实现队列的关键时,在合适的时候进行出栈操作。例如将 1,2,3 这些数据做入队列操作,也就是将这些数据入第一个栈。
如果要执行出队列操作,由于第一个栈直接出栈会导致顺序逆序,所以要将所有元素出栈进入第二个栈。
此时数据的顺序已经恢复,出队列操作就直接在第二个栈做出栈操作即可。
将数据 4 入队列,也是直接将这些数据入第一个栈就行。
而如果要做出队列操作,注意第二个栈中已经有一些数据了,因此在第二个栈做出栈操作即可。
由此我们可以总结出入队列和出队列操作的时机,入队列操作只需要将数据入第一个栈。出队列操作则需要分类讨论,如果第二个栈有数据,则直接对第二个栈做出栈操作即可。如果第二个栈没有数据,需要先将第一个栈的数据全部出栈后入第二个栈,再对第二个栈做出栈操作。
题解代码
class CQueue:
def __init__(self):
self.stack1 = []
self.stack2 = []
def appendTail(self, value: int) -> None:
self.stack1.append(value)
def deleteHead(self) -> int:
if len(self.stack2) != 0: #第二个栈中有数据
return self.stack2.pop()
elif len(self.stack1) == 0: #队列中没有任何元素
return -1
while len(self.stack1) > 0: #第二个栈中无数据且第一个栈不为空
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
时空复杂度
入队列操作只需要将数据入第一个栈,时间复杂度为 O(1)。
出队列操作时,最坏情况需要将第一个栈中的 n 个元素出栈后进入第二个栈,时间复杂度为 O(n)。
参考资料
《剑指 Offer(第2版)》,何海涛 著,电子工业出版社
相关文章
- 消息队列RabbitMQ与Spring集成
- Laravel 运行队列处理器 queue:work 与 queue:listen 区别及 Windows 终端命令问题
- 【BZOJ1915】[Usaco2010 Open]奶牛的跳格子游戏 DP+单调队列
- Lumen 队列
- Java 并发编程学习笔记 理解CLH队列锁算法
- 数据结构之栈和队列
- BZOJ 1029 [JSOI2007]建筑抢修 (贪心 + 优先队列)
- RabbitMQ消息队列生产者和消费者
- Windows迁移打印机与打印队列
- DS | 冲刺阶段考点整理 —— 绪论、线性表、栈与队列、特殊矩阵、串
- java算法-单向队列
- 187、【栈与队列】leetcode ——42. 接雨水(C++版本)
- JavaScript引用类型之Array数组的栈方法与队列方法
- LinkedList的队列用法