python队列的基本操作,python中队列的定义

　　这篇文章给大家带来了一些关于python的知识，主要介绍了队列在习题中的应用，包括如何使用两个堆栈实现一个队列，如何使用两个队列实现一个堆栈，如何判断堆栈中元素的连续性。希望对你有帮助。

　　推荐：python教程

　　00-1010我们学习了队列的相关概念及其实现，同时了解了队列在实际问题中的广泛应用。本节的主要目的是通过队列相关的习题进一步加深对队列的理解，同时可以利用队列降低一些复杂问题求解的时间复杂度。

　　00-1010[问题]给定两个堆栈，仅使用堆栈的基本操作来实现队列。

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

　　[算法]

　　排队：

　　将元素压入堆栈stack_1

　　出列出列：

　　如果堆栈stack_2不为空：

　　Stack_2栈顶元素栈

　　否则：

　　依次弹出stack_1中的所有元素，并将它们压入stack_2。

　　Stack_2栈顶元素栈

　　[代码]

　　班级队列：

　　def __init__(self):

　　self.stack_1=Stack()

　　self.stack_2=Stack()

　　定义入队(自身，数据):

　　self.stack_1.push(数据)

　　定义出列(自身):

　　if self.stack_2.isempty():

　　而不是self.stack_1.isempty():

　　self . stack _ 2 . push(self . stack _ 1 . pop())

　　自我。stack_2。pop()[时空复杂度]s队列时间复杂度为O(1)。如果stack_2不为空，那么队列时间复杂度为O(1)。如果stack_2为空，则需要将元素从stack_1转移到stack_2。然而，由于stack _ 2中已转移元素的数量等于出列元素的数量，所以出列被分摊。

　　n>。

2. 使用两个队列实现一个栈

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

　　[算法]

 算法运行过程需要始终保持其中一个队列为空，用作临时队列
 入栈 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)

3. 栈中元素连续性判断

　　[思路] 由于栈中可能存在奇数个元素，因此为了正确判断，首次需要将栈中元素反转，栈顶元素变为栈底，然后依次出栈，进行判断。

　　[算法]

 栈 stack 中所有元素依次出栈，并插入队列 queue 中
 队列 queue 中所有元素出队，并入栈 stack
  while 栈 stack 不为空：
   栈顶元素 e1 出栈，并插入队列 queue 中
   如果栈 stack 不为空：
     栈顶元素 e2 出栈，并插入队列 queue 中
     如果 e1-e2!=1：
       返回 False，跳出循环
 队列 queue 中所有元素出队，并入栈 stack

　　

def check_stack_pair(stack):
　　 queue = Queue()
　　 flag = True
　　 # 反转栈中元素
　　 while not stack.isempty():
　　 queue.enqueue(stack.pop())
　　 while not queue.isempty():
　　 stack.push(queue.dequeue())
　　 while not stack.isempty():
　　 e1 = stack.pop()
　　 queue.enqueue(e1)
　　 if not stack.isempty():
　　 e2 = stack.pop()
　　 queue.enqueue(e2)
　　 if abs(e1-e2) != 1:
　　 flag = False
　　 break
　　 while not queue.isempty():
　　 stack.push(queue.dequeue())
　　 return flag

4. 重新排列队列中元素顺序

　　[思路] 通过获取队列的前半部分，然后利用栈的反转特性，可以实现重排操作，如下图所示：

　　[算法]

 如果队列 queue 中的元素数为偶数：
   half=queue.size//2
 否则：
   half=queue.size//2+1
 1. 将队列 queue 的前半部分元素依次出队并入栈 stack
 2. 栈 stack 中元素出栈并入队 queue
 3. 将队列 queue 中在步骤 1中未出队的另一部分元素依次出队并插入队尾
 4. 将队列 queue 的前半部分元素依次出队并入栈 stack
 5. 将栈 stack 和队列 queue 中的元素交替弹出并入队
 6. 如果栈 stack 非空：
   栈 stack 中元素出栈并入队

　　

def queue_order(queue):
　　 stack = Stack()
　　 size = queue.size if size % 2 == 0:
　　 half = queue.size//2
　　 else:
　　 half = queue.size//2 + 1
　　 res = queue.size - half for i in range(half):
　　 stack.push(queue.dequeue())
　　 while not stack.isempty():
　　 queue.enqueue(stack.pop())
　　 for i in range(res):
　　 queue.enqueue(queue.dequeue())
　　 for i in range(half):
　　 stack.push(queue.dequeue())
　　 for i in range(res):
　　 queue.enqueue(stack.pop())
　　 queue.enqueue(queue.dequeue())
　　 if not stack.isempty():
　　 queue.enqueue(stack.pop())

5. 反转队列中前 m 个元素的顺序

　　[思路] 结合 [问题4] 我们可以发现，此题就是 [问题4] 的前 3 步，如下图所示：

　　[算法]

 1. 将队列 queue 的前 m 个元素依次出队并入栈 stack
 2. 栈 stack 中元素出栈并入队 queue
 3. 将队列 queue 中在步骤 1中未出队的另一部分元素依次出队并插入队尾

　　

def reverse_m_element(queue, m):
　　 stack = Stack()
　　 size = queue.size if queue.isempty() or m>size:
　　 return
　　 for i in range(m):
　　 stack.push(queue.dequeue())
　　 while not stack.isempty():
　　 queue.enqueue(stack.pop())
　　 for i in range(size-m):
　　 queue.enqueue(queue.dequeue())

　　推荐学习：python教程以上就是一起来分析Python队列相关应用与习题的详细内容，更多请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。