共计 1996 个字符,预计需要花费 5 分钟才能阅读完成。
剑指 Offer 09. 用两个栈实现队列
题目来源:力扣(LeetCode)https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
题目
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead 操作返回 -1)
示例 1:
输入:["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出:[null,null,3,-1]
示例 2:
输入:["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
提示:
- 1 <= values <= 10000
- 最多会对 appendTail、deleteHead 进行 10000 次调用
解题思路
思路:栈
题目要求我们使用栈来实现队列,那么开始之前,先大致说下 栈 和 队列 , 栈 的特性是先进后出,而 队列 是先进先出。
那么要实现队列,这里需要所需的两个栈,其中一个栈(stack1)支持插入操作,而另外一个栈(stack2)支持删除操作。
根据栈先进后出的特性,往 stack1 栈中插入元素,这里最底部的元素相当于队列首元素,但是栈无法直接删除栈底元素。所以引入 stack2 栈,借助 stack2 实现倒序,那么 stack1 原本处于栈底的元素则成为 stack2 的栈顶元素。具体的思路如下:
- 初始化变量
stack1
和stack2
,stack1
支持插入操作,stack2
支持删除操作。 -
插入元素函数实现:
- 将元素插入
stack1
栈中
- 将元素插入
-
删除元素函数实现,这里分为以下几种情况:
- 当
stack1
存在元素(不为空),但是stack2
为空时,将stack1
的元素放入stack2
中,实现倒序。返回stack2
栈顶元素。 - 当
stack2
不为空的情况下,那么直接返回stack2
的栈顶元素即可。 - 当
stack1
和stack2
都为空的情况下,返回-1
- 当
以示例 2 为例:
输入:["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出:[null,-1,null,null,5,2]
关于方法实现的图解如下:
具体的代码实现如下。
代码实现
class CQueue:
def __init__(self):
"""初始化 stack1 和 stack2 两个栈"""
self.stack1 = []
self.stack2 = []
def appendTail(self, value: int) -> None:
"""插入元素"""
# 将元素插入 stack1 栈中
self.stack1.append(value)
def deleteHead(self) -> int:
"""删除元素"""
# 这里分情况处理
# stack2 为空,但是 stack1 不为空,# 将 stack1 的元素转移到 stack2 中
if not self.stack2:
while self.stack1:
self.stack2.append(self.stack1.pop())
# stack2 存在元素,直接返回栈顶元素
if self.stack2:
del_ele = self.stack2.pop()
return del_ele
# stack1 和 stack2 都为空的情况下,返回 -1
return -1
# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()
实现结果
总结
- 题目要求使用两个栈辅助实现队列,因为根据栈先进后出的特性,单独一个栈,栈底元素就相当于队列首元素(而队列的特性是先进先出),而栈无法直接删除栈底元素,所以需要引入第二个栈。
-
具体的设计思路:
- 维护两个栈
stack1
和stack2
,初始化为空; -
stack1
支持插入操作,而stack2
支持删除操作。 -
插入函数的实现:
- 直接将元素插入
stack1
中;
- 直接将元素插入
-
删除函数实现,分为以下情况:
- 当
stack2
为空,而stack1
存在元素时,将stack1
的元素转移到stack2
中。此时stack2
的栈顶元素就相当于stack1
的栈底元素(也就是队列首元素) - 当
stack2
不为空的时候,直接返回栈顶元素; - 当
stack1
和stack2
都为空时,直接返回-1
。
- 当
- 维护两个栈
文章原创,欢迎关注点赞。微信公众号《书所集录》同步更新,同样欢迎关注。
正文完