【一天一道Leetcode】用栈实现队列
共 2689字,需浏览 6分钟
·
2021-03-08 08:36
本篇推文共计2000个字,阅读时间约3分钟。
01
题目描述
题目描述:
请你仅使用两个栈实现先入先出队列。队列应当支持一般队列的支持的所有操作
(push、pop、peek、empty):
实现 MyQueue 类:
void push(int x) 将元素 x 推到队列的末尾
int pop() 从队列的开头移除并返回元素
int peek() 返回队列开头的元素
boolean empty() 如果队列为空,返回 true ;否则,返回 false
示例如下:
输入:
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出:
[null, null, null, 1, 1, false]
解释:
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (最左边的数字在队列前面)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false
02
代码分析
由题目描述可知
栈和队列是两种基本的数据结构,同为容器类型。两者根本的区别在于:
栈stack:后进先出
队列queue:先进先出
由于此题要求
用两个先进后出的栈实现一个先进先出的队列
我们可以将
一个栈当作输入栈,用于压入push传入的数据;
另外一个栈做为输出栈用于pop和peek操作;
如下图所示,
向输入栈push元素1,即代表向队列从右到左输入1
向输入栈push元素2,即代表向队列从右到左输入2
每次需要执行pop或peek之前,输入栈需要向输出栈移入元素,根据栈先进后出的原则,输出栈最先进入栈的元素是2,最后进入栈的元素是1
执行peek操作时,需要返回队列开头的元素,即返回在输出栈最上面的元素1
执行pop操作时,需要先从队列移除开头元素,再返回队列剩下的元素,即输出栈上面的元素1出栈,也就是代表队列中开头元素1从左边出列,此时队列只剩下元素2
当执行empty操作时候,即判断输入栈和输出栈是否为空,若为空则返回true,如下所示,输入输出栈没有元素,则返回true
如下所示,输入输出栈还有元素2,则返回false
因此我们的代码为
class MyQueue(object):
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, x):
self.stack1.append(x)
def pop(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self):
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2[-1]
def empty(self):
return not self.stack1 and not self.stack2
![](https://filescdn.proginn.com/c00d9042b0c2c69291d259d917422a8c/6f61af2c18b0e97b1d7e2c01e376268b.webp)
【年终总结】你好2021,再见2020。
![](https://filescdn.proginn.com/ce29be5ca571d463154f56e1afdf498c/73f93be31f2df725189736a95acea9c8.webp)
【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台
![](https://filescdn.proginn.com/81e0e5fe9d695e16c2361d961498062d/5beb41e56c4bfaa4220feb6893732002.webp)
【秋招纪实录】一篇特别正经的【腾讯】求职经验分享
![](https://filescdn.proginn.com/8e0bbddacdd6aabe6112d913050e856c/a4f67385fe71c99f990999dd1fb75266.webp)
【一天一道Leetcode】矩阵不可变
![](https://filescdn.proginn.com/09dfe1bac39a66ff851bd10d61d07172/cb48f18592a4a04ceb6c840b51f22ab5.webp)
【一天一道Leetcode】比特位计数
![](https://filescdn.proginn.com/e2d0937a3537a5d83cc43162fedf1a8d/4cd3e2b12e8f3e8e7e2a96769b0897b8.webp)
【一天一道Leetcode】套信封问题
你与世界
只差一个
公众号