爱站程序员基地一、python队列在数据结构算法类应用：
Python标准库中包含了四种队列，分别是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque
Python的Queue模块中提供了同步的、线程安全的队列类，包括FIFO（先入先出)队列Queue，LIFO（后入先出）队列LifoQueue，和优先级队列PriorityQueue。
还有一种常用，也是我觉得最好用的是deque，双边队列
相比于list实现的队列，deque实现拥有更低的时间和空间复杂度。list实现在出队（pop）和插入（insert）时的空间复杂度大约为O(n)，deque在出队（pop）和入队（append）时的时间复杂度是O(1)。
所以deque更有优越性 而且deque既可以表示队列 又可以表示栈 实在是太方便了。
除了C、java中常见的函数外，支持in操作符、rotate(1)、rotate(-1)、copy()、extend()、extendleft()、index()、insert()、remove()、reverse。
举个例子：
调整数组顺序使奇数位于偶数前面
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。
示例：
输入：nums = [1,2,3,4]输出：[1,3,2,4]注：[3,1,2,4] 也是正确的答案之一。
双端队列的做法：
class Solution:def exchange(self, nums: List[int]) -> List[int]:tmp = collections.deque()for num in nums:tmp.appendleft(num) if num % 2 ==1 else tmp.append(num)return list(tmp)
再举个实现单调队列的例子：
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：输入:["MaxQueue","push_back","push_back","max_value","pop_front","max_value"][[],[1],[2],[],[],[]]输出: [null,null,null,2,1,2]示例 2：输入:["MaxQueue","pop_front","max_value"][[],[],[]]输出: [null,-1,-1]
#单调栈写法#均摊时间复杂度是O(1)import queueclass MaxQueue:def __init__(self):self.dq = queue.deque()self.q = queue.Queue()def max_value(self) -> int:return self.dq[0] if self.dq else -1def push_back(self, value: int) -> None:while self.dq and self.dq[-1] < value:self.dq.pop()self.dq.append(value)self.q.put(value)def pop_front(self) -> int:if self.q == []: return -1ans = self.q.get()if ans == self.dq[0]:self.dq.popleft()return ans
二、python队列在线程间交换数据应用
当我做单调队列的时候，遇到过一个问题：
import queueq = queue.Queue()if q:ans = q.get()print(ans)
这段程序结果竟然是死循环，或者说一直被阻塞（后来才知道）
这个问题和上面有点相似：Queue.get（）默认的也是阻塞方式读取数据，队列为空时，不会抛出 except Queue.Empty ，而是进入阻塞直至超时。
想要解决这个问题，必须加上block=False 的参数。
同理，Queue.put（）默认有 block = True 和 timeout 两个参数。
如下代码的结果并不是10个A，而是会混杂B。
import Queueq = Queue.Queue(10)for i in range(10):myData = \'A\'q.put(myData)myData = \'B\'
当 block = True 时，写入是阻塞式的，阻塞时间由 timeout 肯定。正由于阻塞，才致使了后来的赋值污染了处于阻塞状态的数据。Queue.put（）方法加上 block=False 的参数，便可解决这个隐蔽的问题。但要注意，非阻塞方式写队列，当队列满时会抛出 exception Queue.Full 的异常。
