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站长网) |
相关内容
网友评论
推荐文章
热点阅读