LeetCode-剑指-Offer-09-用两个栈实现队列-Python

30次阅读

共计 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 的栈顶元素。具体的思路如下:

  • 初始化变量 stack1stack2stack1 支持插入操作,stack2 支持删除操作。
  • 插入元素函数实现:

    • 将元素插入 stack1 栈中
  • 删除元素函数实现,这里分为以下几种情况:

    • stack1 存在元素(不为空),但是 stack2 为空时,将 stack1 的元素放入 stack2 中,实现倒序。返回 stack2 栈顶元素。
    • stack2 不为空的情况下,那么直接返回 stack2 的栈顶元素即可。
    • stack1stack2 都为空的情况下,返回 -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()

实现结果


总结


  • 题目要求使用两个栈辅助实现队列,因为根据栈先进后出的特性,单独一个栈,栈底元素就相当于队列首元素(而队列的特性是先进先出),而栈无法直接删除栈底元素,所以需要引入第二个栈。
  • 具体的设计思路:

    • 维护两个栈 stack1stack2,初始化为空;
    • stack1 支持插入操作,而 stack2 支持删除操作。
    • 插入函数的实现:

      • 直接将元素插入 stack1 中;
    • 删除函数实现,分为以下情况:

      • stack2 为空,而 stack1 存在元素时,将 stack1 的元素转移到 stack2 中。此时 stack2 的栈顶元素就相当于 stack1 的栈底元素(也就是队列首元素)
      • stack2 不为空的时候,直接返回栈顶元素;
      • stack1stack2 都为空时,直接返回 -1

文章原创,欢迎关注点赞。微信公众号《书所集录》同步更新,同样欢迎关注。

正文完
 0