Python队列的练习题有什么

发布时间：2022-03-31 14:18 所属栏目：13 来源：互联网

导读：这篇文章主要为大家展示了Python队列的练习题有哪些，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下Python队列的练习题有哪些这篇文章吧。 1. 使用两个栈实现一个队列 [问题] 给定两个栈，仅使用栈的基本操作实

　　这篇文章主要为大家展示了“Python队列的练习题有哪些”，内容简而易懂，条理清晰，希望能够帮助大家解决疑惑，下面让小编带领大家一起研究并学习一下“Python队列的练习题有哪些”这篇文章吧。

　　1. 使用两个栈实现一个队列
　　[问题] 给定两个栈，仅使用栈的基本操作实现一个队列。

　　[思路] 解决此问题的关键在于栈的反转特性，入栈的一系列元素在出栈时会以相反的顺序返回。因此，使用两个栈就可以实现元素以相同的顺序返回(反转的元素序列再次反转后就会得到原始顺序)。具体操作如下图所示：

　　Python队列的练习题有哪些

　　[算法]

　　入队 enqueue：
　　将元素推入栈 stack_1
　　出队 dequeue：
　　如果栈 stack_2 不为空：
　　 stack_2 栈顶元素出栈
　　否则：
　　将所有元素依次从 stack_1 弹出并压入 stack_2
　　 stack_2 栈顶元素出栈

　　[代码]

　　class Queue:
　　    def __init__(self):
　　        self.stack_1 = Stack()
　　        self.stack_2 = Stack()
　　    def enqueue(self, data):
　　        self.stack_1.push(data)
　　    def dequeue(self):
　　        if self.stack_2.isempty():
　　            while not self.stack_1.isempty():
　　                self.stack_2.push(self.stack_1.pop())
　　        return self.stack_2.pop()

　　2. 使用两个队列实现一个栈
　　[问题] 给定两个队列，仅使用队列的基本操作实现一个栈。

　　[思路] 由于队列并不具备反转顺序的特性，入队顺序即为元素的出队顺序。因此想要获取最后一个入队的元素，需要首先将之前所有元素出队。因此为了使用两个队列实现栈，我们需要将其中一个队列 store_queue 用于存储元素，另一个队列 temp_queue 则用来保存为了获取最后一个元素而保存临时出队的元素。push 操作将给定元素入队到存储队列 store_queue 中；pop 操作首先把存储队列 store_queue 中除最后一个元素外的所有元素都转移到临时队列 temp_queue 中，然后存储队列 store_queue 中的最后一个元素出队并返回。具体操作如下图所示：

　　Python队列的练习题有哪些

　　[算法]

　　算法运行过程需要始终保持其中一个队列为空，用作临时队列
　　入栈 push：在非空队列中插入元素 data。
　　若队列 queue_1 为空：
　　将 data 插入队列 queue_2 中
　　否则：
　　将 data 插入队列 queue_1 中
　　出栈 pop：将队列中的前n−1 个元素插入另一队列，删除并返回最后一个元素
　　若队列 queue_1 不为空：
　　将队列 queue_1 的前n−1 个元素插入 queue_2，然后 queue_1 的最后一个元素出队并返回
　　若队列 queue_2 不为空：
　　将队列 queue_2 的前 n−1 个元素插入 queue_1，然后 queue_2 的最后一个元素出队并返回

　　[代码]

　　class Stack:
　　    def __init__(self):
　　        self.queue_1 = Queue()
　　        self.queue_2 = Queue()
　　    def isempty(self):
　　        return self.queue_1.isempty() and self.queue_2.isempty()
　　    def push(self, data):
　　        if self.queue_2.isempty():
　　            self.queue_1.enqueue(data)
　　        else:
　　            self.queue_2.enqueue(data)
　　    def pop(self):
　　        if self.isempty():
　　            raise IndexError("Stack is empty")
　　        elif self.queue_2.isempty():
　　            while not self.queue_1.isempty():
　　                p = self.queue_1.dequeue()
　　                if self.queue_1.isempty():
　　                    return p
　　                self.queue_2.enqueue(p)
　　        else:
　　            while not self.queue_2.isempty():
　　                p = self.queue_2.dequeue()
　　                if self.queue_2.isempty():
　　                    return p
　　                self.queue_1.enqueue(p)
　　[时空复杂度] push 操作的时间复杂度为O(1)，由于 pop 操作时，都需要将所有元素从一个队列转移到另一队列，因此时间复杂度O(n)。

（编辑：ASP站长网）