【一天一道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




往期回顾

【年终总结】你好2021,再见2020。


【快速写好毕业论文】你不得不知晓的七个常用文献搜索平台


【秋招纪实录】一篇特别正经的【腾讯】求职经验分享


【一天一道Leetcode】矩阵不可变


【一天一道Leetcode】比特位计数


【一天一道Leetcode】套信封问题



☆ END ☆

你与世界

只差一个

公众号

浏览 36
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报