LeetCode 232:用栈实现队列

苦逼的码农

共 4331字,需浏览 9分钟

 ·

2021-10-29 19:24

往期回顾

三分钟基础:什么是时间|空间复杂度

三分钟基础:什么是数组

三分钟基础:什么是链表

三分钟基础之链表训练:环形链表

三分钟基础之链表训练:环形链表升级版

三分钟基础之链表训练:链表相交

三分钟基础:什么是栈|队列

三分钟基础之栈训练:删除字符串中的所有相邻重复项

三分钟基础之栈训练:用栈实现队列


今天用栈实现队列这道题,是考察对”栈和队列理解程度“的好题。


放心,在实际工作的时候,不是脑残十级,几乎不会提出这样奇怪的需求


话不多说,直接开整。




   LeetCode 232:用栈实现队列


题意


仅使用两个栈实现先入先出队列,队列支持一般队列支持的所有操作

  • void push(int x):将元素 x 推到队列的末尾。

  • int pop():从队列的开头移除并返回元素。

  • int peek():返回队列开头的元素。

  • boolean empty():如果队列为空,返回 true;否则,返回 false。


示例



提示


  • 1 <= x <= 9

  • 最多调用 100 次 push、pop、peek 和 empty

  • 假设所有操作都是有效的(eg. 一个空的队列不会调用 pop 或者 peek 操作)


题目解析


水题,难度简单,主要考察对栈和队列的理解能力


如果对栈和队列还不熟悉,看一下下面这篇文章,某帅比写的:


呔!“栈”住,队列!


仔细来看,主要涉及 4 种常规操作:


  • 入队 push

  • 出队 pop

  • 判空 empty

  • 取队首元素 peek


知道了要求,剩下就是如何用栈模拟队列。


队列是一种先入先出(FIFO)的数据结构,而栈是一种后入先出(LIFO)的数据结构,所以一个栈绝对满足不了队列的 FIFO 的特性。


比如 1 2 3,队列 1 2 3 进,应该 1 2 3 出,但是 1 2 3 进了栈,出来以后会成 3 2 1,和 1 2 3 是相反的,所以再需要一个栈,把 3 2 1 返成 1 2 3。


因此这里需要两个栈,分别是输入栈和输出栈


输入栈来反转元素的入队顺序,元素入只能从输入栈进(push)。


输出栈用来存储元素的正常顺序,元素出只能从输出栈出(pop、peek)。


图解


首先初始化输入栈和输出栈。



def __init__(self):    # 初始化输入栈和输出栈    self.inStack = []    self.outStack = []

push(x) ,入队操作,直接压入输入栈即可。


比如 push(1)、push(2)。



def push(self, x: int) -> None:    # 有新元素进来,进入输入栈    self.inStack.append(x)


push 操作,每个元素入栈的时间复杂度为 O(1),队列长度为 n,所以时间复杂度为 O(n)。因为需要额外的栈来存储队列中的元素,所以空间复杂度为 O(n)


pop(), 出队操作,如果输出栈不为空的话,直接扔出栈顶元素,输出栈为空的话,那把输入栈的所有元素压入输出栈中,然后再扔出栈顶元素。



def pop(self) -> int:    # 如果为空    if self.empty():        return None    # 如果输出栈不为空,返回输出栈中的元素    if self.outStack:        return self.outStack.pop()    # 输出栈为空,将输入栈的元素压入输出栈    else:        while self.inStack:            val = self.inStack.pop()            self.outStack.append(val)        return self.outStack.pop()


pop 操作的时间复杂度为 O(n),空间复杂度为 O(n)。


empty(),判空操作。判空很简单,输入栈和输出栈都为空,则队列为空,否则队列不为空。



def empty(self) -> bool:      # 两个栈都为空,队列才为空      if not(self.inStack or self.outStack):          return True
return False

这个没啥好说的,做了一步判断,时间复杂度为 O(1),空间复杂度均为 O(n)。


peek(),取队列的首元素,和 pop() 的操作差不多。唯一的区别是,pop 是删掉了队首元素,而 peek 只是看队首元素。


def peek(self) -> int:    # 使用已有的函数 pop    res = self.pop()    # pop 函数弹出了 res,所以要再添加回去    self.outStack.append(res)      return res


队列的首元素使用已有的 pop 函数,时间复杂度和空间复杂度和 pop 一样,时间复杂度和空间复杂度都为 O(n)。


代码实现


Python 代码实现


class MyQueue:
def __init__(self): """ Initialize your data structure here. """ # 初始化输入栈和输出栈 self.inStack = [] self.outStack = []
def push(self, x: int) -> None: """ Push element x to the back of queue. """ # 有新元素进来,进入输入栈 self.inStack.append(x)
def pop(self) -> int: """ Removes the element from in front of queue and returns that element. """        # 如果为空 if self.empty(): return None
# 如果输出栈不为空,返回输出栈中的元素 if self.outStack: return self.outStack.pop() # 输出栈为空,将输入栈的元素压入输出栈 else: while self.inStack: val = self.inStack.pop() self.outStack.append(val) return self.outStack.pop()
def peek(self) -> int: """ Get the front element. """ # 使用已有的函数 pop res = self.pop() # pop 函数弹出了 res,所以要再添加回去 self.outStack.append(res)
return res

def empty(self) -> bool: """ Returns whether the queue is empty. """ # 两个栈都为空,队列才为空 if not(self.inStack or self.outStack): return True
return False


# Your MyQueue object will be instantiated and called as such:# obj = MyQueue()# obj.push(x)# param_2 = obj.pop()# param_3 = obj.peek()# param_4 = obj.empty()


Java 代码实现


class MyQueue {
Stack stack1; Stack stack2;
/** Initialize your data structure here. */ public MyQueue() { stack1 = new Stack<>(); // 负责进栈 stack2 = new Stack<>(); // 负责出栈 } /** Push element x to the back of queue. */ public void push(int x) { stack1.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { dumpStack1(); return stack2.pop(); } /** Get the front element. */ public int peek() { dumpStack1(); return stack2.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return stack1.isEmpty() && stack2.isEmpty(); }
// 如果stack2为空,那么将stack1中的元素全部放到stack2中 private void dumpStack1(){ if (stack2.isEmpty()){ while (!stack1.isEmpty()){ stack2.push(stack1.pop()); } } }}
/** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */


图解栈实现队列到这就结束啦,是不是很简单呐,只要熟悉栈和队列就一定会。

最后,欢迎加入帅地的知识星球,帅地会在星球知无不言,无论是 offer 选择,职业规划还是学习路线,帅地都会在 48 小时以内答复你的问题,并且根据你自身的情况,为你量身定制学习路线
同时超全学习攻略也已经更新好了,小白跟着帅地的学习攻略学就行了
各类学习资料,项目资料都会提供给大家。
而且你有任何的疑惑,帅地都会答复你,并且星球里也有一群和你相同年龄的小伙伴在奋斗,都是未来的卷王
帅地会在星球会提供如下服务
1、【一对一咨询服务】48 小时以内超详细回答你的任何问题,包括写作等等,这是知识星球最重要的功能。最近一周就回答了十几个 offer 选择,校招等学习路线问题。
2、【学习攻略】校招这方面比较有经验,帅地会提供完整的学习攻略,并且随着时间的积累,这份攻略会越来越完善哦。
3、简历修改,项目等学习资源,offer 收割机嘉宾分享等等。
目前星球是专注于校招,在校生学习指导这块,一定可以让你少走弯路,已经有 670+ 位小伙伴加入,这里还有一些 20 元的优惠卷,如果你信的过帅地,那么欢迎你的加入。

点击阅读原文可以了解详情


浏览 37
点赞
评论
收藏
分享

手机扫一扫分享

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

手机扫一扫分享

分享
举报