Python 列表 append + pop(0) 可模擬佇列 (FIFO),但 pop(0) 為 O(n)。本文先示範教學版列表實作,再介紹 collections.deque 真正的 O(1) 雙端佇列。
#!/usr/bin/env python
queue = []
def enQ():
queue.append(input('Enter new string: ').strip())
def deQ():
if not queue:
print('Cannot pop from an empty queue!')
else:
print('Removed [', queue.pop(0), ']')
def viewQ():
print(queue)
CMDs = {'e': enQ, 'd': deQ, 'v': viewQ}
def showmenu():
prompt = """
(E)nqueue
(D)equeue
(V)iew
(Q)uit
Enter choice: """
while True:
while True:
try:
choice = input(prompt).strip()[0].lower()
except (EOFError, KeyboardInterrupt, IndexError):
choice = 'q'
print(f'\nYou picked: [{choice}]')
if choice not in 'devq':
print('Invalid option, try again')
else:
break
if choice == 'q':
break
CMDs[choice]()
if __name__ == '__main__':
showmenu()
列表底層為動態陣列,pop(0) 需將所有元素前移。資料量大時嚴重拖慢效能。
from collections import deque
q = deque(maxlen=100) # 可選最大長度,自動丟棄舊資料
q.append('a') # 右側加入 (enqueue)
q.appendleft('b') # 左側加入
q.pop() # 右側彈出
q.popleft() # 左側彈出 (dequeue) - O(1)
q.extend(['x','y']) # 批次加入
q.rotate(3) # 循環旋轉
| 實作 | enqueue | dequeue | 記憶體 | 適用場景 |
|---|---|---|---|---|
| list + pop(0) | O(1) | O(n) | 低 | 教學、極小資料量 |
| collections.deque | O(1) | O(1) | 中 | 生產環境、高頻佇列 |
| queue.Queue | O(1) | O(1) | 中 | 多執行緒安全、阻塞操作 |
| asyncio.Queue | O(1) | O(1) | 中 | 非同步協程 |
import queue, threading, time
q = queue.Queue(maxsize=10)
def producer():
for i in range(20):
q.put(f'item-{i}')
time.sleep(0.1)
q.put(None) # 停止信號
def consumer():
while True:
item = q.get()
if item is None:
break
print(f'Consumed {item}')
q.task_done()
threading.Thread(target=producer).start()
threading.Thread(target=consumer).start()