看這個就夠了

一、python隊列在數(shù)據(jù)結(jié)構(gòu)算法類應(yīng)用：

Python標準庫中包含了四種隊列，分別是queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque

Python的Queue模塊中提供了同步的、線程安全的隊列類，包括FIFO（先入先出)隊列Queue，LIFO（后入先出）隊列LifoQueue，和優(yōu)先級隊列PriorityQueue。

還有一種常用，也是我覺得最好用的是deque，雙邊隊列

相比于list實現(xiàn)的隊列，deque實現(xiàn)擁有更低的時間和空間復(fù)雜度。list實現(xiàn)在出隊（pop）和插入（insert）時的空間復(fù)雜度大約為O(n)，deque在出隊（pop）和入隊（append）時的時間復(fù)雜度是O(1)。

所以deque更有優(yōu)越性 而且deque既可以表示隊列 又可以表示棧 實在是太方便了。

除了C、java中常見的函數(shù)外，支持in操作符、rotate(1)、rotate(-1)、copy()、extend()、extendleft()、index()、insert()、remove()、reverse。

舉個例子：

調(diào)整數(shù)組順序使奇數(shù)位于偶數(shù)前面

輸入一個整數(shù)數(shù)組，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序，使得所有奇數(shù)在數(shù)組的前半部分，所有偶數(shù)在數(shù)組的后半部分。

示例：

輸入：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)

再舉個實現(xiàn)單調(diào)隊列的例子：

請定義一個隊列并實現(xiàn)函數(shù) max_value 得到隊列里的最大值，要求函數(shù)max_value、push_back 和 pop_front 的均攤時間復(fù)雜度都是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]

#單調(diào)棧寫法
#均攤時間復(fù)雜度是O(1)
import queue
class 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 -1

    def 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 -1
        ans = self.q.get()
        if ans == self.dq[0]:
            self.dq.popleft()
        return ans

二、python隊列在線程間交換數(shù)據(jù)應(yīng)用

當(dāng)我做單調(diào)隊列的時候，遇到過一個問題：

import queue
q = queue.Queue()
if q:
    ans = q.get()
    print(ans)

這段程序結(jié)果竟然是死循環(huán)，或者說一直被阻塞（后來才知道）

這個問題和上面有點相似：Queue.get（）默認的也是阻塞方式讀取數(shù)據(jù)，隊列為空時，不會拋出 except Queue.Empty ，而是進入阻塞直至超時。

想要解決這個問題，必須加上block=False 的參數(shù)。

同理，Queue.put（）默認有 block = True 和 timeout 兩個參數(shù)。

如下代碼的結(jié)果并不是10個A，而是會混雜B。

import Queue
       q = Queue.Queue(10)
       for i in range(10):
               myData = 'A'
               q.put(myData)
               myData = 'B'

當(dāng) block = True 時，寫入是阻塞式的，阻塞時間由 timeout 肯定。正由于阻塞，才致使了后來的賦值污染了處于阻塞狀態(tài)的數(shù)據(jù)。Queue.put（）方法加上 block=False 的參數(shù)，便可解決這個隱蔽的問題。但要注意，非阻塞方式寫隊列，當(dāng)隊列滿時會拋出 exception Queue.Full 的異常。