Python 的 deque：比 list 快 100 倍的神奇列表（隊列）
python 中，list 是最常用的數據結構之一。當需要頻繁在頭部或尾部插入、刪除元素時，list 可能會變得很慢。
這時候，collections.deque（雙端隊列）就該使用這個了deque 。 在某些操作上，它甚至比 list 快 100 倍！
1. 什么是 deque？
deque（發音 "deck"）是 雙端隊列（Double-Ended Queue） 的縮寫。它允許你從兩端高效地添加或刪除元素，時間復雜度僅為 O(1)。
而 list 在頭部操作時，時間復雜度是 O(n)，因為它需要移動所有元素。這就是為什么 deque 在特定場景下比 list 快得多！
deque 的基本用法
from collections import deque # 創建一個 deque d = deque([1, 2, 3]) # deque([1, 2, 3]) # 從右側添加元素 d.append(4) # deque([1, 2, 3, 4]) # 從左側添加元素 d.appendleft(0) # deque([0, 1, 2, 3, 4]) # 從右側彈出元素 d.pop() # deque([0, 1, 2, 3]) # 從左側彈出元素 d.popleft() # deque([1, 2, 3])
2. deque vs list：性能對比
測試 1：頭部插入（appendleft 和 insert(0, x)）
import timeit
# 測試 deque 的 appendleft
def test_deque_appendleft():
d = deque()
for i in range(10000):
d.appendleft(i)
# 測試 list 的 insert(0, x)
def test_list_insert():
lst = []
for i in range(10000):
lst.insert(0, i)
# 測量時間
deque_time = timeit.timeit(test_deque_appendleft, number=1000)
list_time = timeit.timeit(test_list_insert, number=1000)
print(f"deque.appendleft:{deque_time:.4f}秒") # 輸出：0.4435秒
print(f"list.insert(0, x):{list_time:.4f}秒") # 輸出：14.7492秒
測試 2：頭部刪除（popleft 和 pop(0)）
from collections import deque
import timeit
def test_deque_popleft():
d = deque(range(10000))
for _ in range(10000):
d.popleft()
def test_list_pop0():
lst = list(range(10000))
for _ in range(10000):
lst.pop(0)
deque_time = timeit.timeit(test_deque_popleft, number=1000)
list_time = timeit.timeit(test_list_pop0, number=1000)
print(f"deque.popleft:{deque_time:.4f}秒") # 輸出：0.5152秒
print(f"list.pop(0):{list_time:.4f}秒") # 輸出：5.7043秒
3. deque 的進階用法
(1) 限制隊列長度（maxlen）
deque 可以設置最大長度，當隊列滿時，新元素加入會自動丟棄另一端的元素。
from collections import deque d = deque(maxlen=3) d.append(1) # deque([1]) d.append(2) # deque([1, 2]) d.append(3) # deque([1, 2, 3]) d.append(4) # deque([2, 3, 4])，最左邊的 1 被丟棄
適用場景：
- 滑動窗口計算
- 最近 N 條記錄存儲
(2) 旋轉隊列（rotate）
rotate(n) 可以讓隊列循環移動：
rotate(1)：向右移動 1 位rotate(-1)：向左移動 1 位
from collections import deque d = deque([1, 2, 3, 4, 5]) d.rotate(2) # deque([4, 5, 1, 2, 3]) d.rotate(-1) # deque([5, 1, 2, 3, 4])
適用場景：
- 輪播數據
- 循環緩沖區
(3) 線程安全（可用于多線程隊列）
deque 的 append、pop 等操作是線程安全的，適合用于多線程任務隊列。
from threading import Thread
from collections import deque
import time
queue = deque()
def producer():
for i in range(5):
queue.append(i)
time.sleep(0.1)
def consumer():
while True:
if queue:
print(queue.popleft())
time.sleep(0.1)
Thread(target=producer).start()
Thread(target=consumer).start()
4. 什么時候用 deque？什么時候用 list？
| 操作 | deque 效率 |
list 效率 |
推薦選擇 |
| 頭部插入/刪除 | ? O(1) | ?? O(n) | ? |
deque尾部插入/刪除 |
? O(1) | ? O(1) | 都可以 |
| 隨機訪問 | ?? O(n) | ? O(1) | ? list |
總結：
- 如果需要頻繁在頭部操作（如隊列、棧），用
deque。 - 如果需要隨機訪問元素（如
lst[1000]），用list。
deque 是 Python 中一個被低估的高性能數據結構。
在需要高效頭部操作的場景下，它比 list 快 100 倍！
適用于：
? 隊列（FIFO）
? 棧（LIFO）
? 滑動窗口計算
? 線程安全任務隊列
如果的代碼涉及大量 insert(0, x) 或 pop(0)，就換成 deque
浙公網安備 33010602011771號