Python编程题33--用栈实现队列

题目

栈和队列是常见的数据结构,栈的特点是 先进后出,而队列的特点是 先进先出

请使用 栈 模拟实现队列的下列操作:

  • push(x) -- 将元素 x 推到队列的末尾
  • pop() -- 从队列的开头移除并返回元素
  • peek() -- 返回队列开头的元素
  • empty() -- 判断队列是否为空

说明

  • 可以用 列表list 来模拟栈,但只允许使用栈的基本操作。
  • 假设每次调用 pop 和 peek 都能保证队列不为空。

实现思路1

  • 使用两个栈,一个作为输入栈 stack1 ,另一个作为输出栈 stack2
  • 每次 push 入队操作,直接把 待入队的新元素 入栈到 stack1 即可
  • 每次 pop 出队操作,stack2的栈顶就相当于队列的队头,直接从 stack2 弹出栈顶元素即可,如果 stack2 为空,那么就把 stack1 的所有元素导入到 stack2 中,最后再从 stack2 弹出数据
  • 每次 peek 获取队头元素操作,可以复用出队操作的实现,从而拿到队列开头的元素
  • 每次 empty 操作,则需判断 stack1 和 stack2 是否都为空

代码实现1

class MyQueue:

    def __init__(self):
        self.stack1 = []  # 输入栈
        self.stack2 = []  # 输出栈

    def push(self, x):
        self.stack1.append(x)

    def pop(self):
        if self.stack2 == []:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

    def peek(self):
        tmp = self.pop()
        self.stack2.append(tmp)
        return tmp

    def empty(self):
        return self.stack1 == [] and self.stack2 == []

实现思路2

  • 使用两个栈,一个作为辅助栈 stack1 ,另一个作为存放队列元素的栈 stack2
  • 每次 push 入队操作,需先把 stack2 中全部元素导入到 stack1 ,接着把 待入队的新元素 入栈到 stack1 ,最后把 stack1 中全部元素导入到 stack2,这样一来,stack2的栈顶就相当于队列的队头
  • 每次 pop 出队操作,直接从 stack2 弹出栈顶元素
  • 每次 peek 获取队头元素操作,直接从 stack2 获取栈顶元素
  • 每次 empty 操作,则只需判断 stack2 是否为空

代码实现2

class MyQueue:

    def __init__(self):
        self.stack1 = []  # 辅助栈
        self.stack2 = []  # 存放队列元素

    def push(self, x):
        while self.stack2:
            self.stack1.append(self.stack2.pop())
        self.stack1.append(x)
        while self.stack1:
            self.stack2.append(self.stack1.pop())

    def pop(self):
        return self.stack2.pop()

    def peek(self):
        return self.stack2[-1]

    def empty(self):
        return self.stack2 == []
上一篇:解决 vscode 中 nuget 插件无法获取包版本的问题


下一篇:LeetCode刷题day31