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

  • Z时代
  • 2024-01-10
  • 分类：综合

python

题目

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

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

  • 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 == []

更多Python编程题，等你来挑战：Python编程题汇总（持续更新中……）

以上是 Python编程题33--用栈实现队列 的全部内容， 来源链接： utcz.com/z/389043.html

回到顶部