演算法系列 · 第 9 關 · 資料結構

佇列 Queue

先進先出,像排隊買珍奶 —— 尾端排進來、前端走出去。公平,而且兩端都 O(1)。

佇列有兩個開口:新元素從尾端(rear)排進來(enqueue),要拿就從前端(front)拿走最早進來的那個(dequeue)。誰先來、誰先走 —— 這叫先進先出(FIFO,First In First Out),就是排隊。只要用對工具(deque),兩端進出都是 O(1)。

核心觀念:先進先出 FIFO

兩個開口 —— 尾端 rear 進、前端 front 出。跟堆疊「只有一個開口」不同。

enqueue(入隊) —— 新元素排到尾端。

dequeue(出隊) —— 從前端拿走最早進來的那個。

peek / front(看頭) —— 看最前面是誰,但不拿走。

先進先出(FIFO) —— 誰先來誰先走,公平排隊。

一句話記住堆疊 vs 佇列:堆疊是「一個口、後進先出」(疊盤子),佇列是「兩個口、先進先出」(排隊)。深度優先 DFS 用堆疊,廣度優先 BFS 用佇列。

為什麼一定要用 deque?(重要)

用 list 當佇列有陷阱 —— enqueue 用 append(尾端,O(1))沒問題;但 dequeue 若用 pop(0)(從頭拿),會逼後面每一格往前搬一格 → O(n)!

資料一多,pop(0) 就是效能殺手 —— 這是新手最常踩的雷。

collections.deque 才是正解 —— 它是雙端佇列,兩端 append / popleft 都是 O(1)。

要執行緒安全或跨程序 —— 還有 queue.Queue、multiprocessing.Queue(範例 7)。

複雜度

O(1)enqueue / dequeue(用 deque) —— 尾端進、前端出,都一步到位。

O(n)用 list.pop(0) 當出隊 —— 每拿一個,後面全部往前補一格。常見雷,別這樣寫。

O(n)空間 —— n 個元素就要 n 格。

什麼時候用佇列?任務排程 / 工作佇列、廣度優先搜尋 BFS、印表機列印順序、訊息佇列、緩衝區 —— 任何「先來先服務」的場景。

用生活比喻它

🧋

排隊買珍奶

先排的先買到,新來的乖乖排最後面。沒有人可以插隊(不然就不是佇列了)。

🖨️

印表機列印佇列

先送出的文件先印,後送的排後面等。

🎢

排隊玩設施

照抵達順序上車,一批一批來,先到先玩。

🎮 enqueue / dequeue 排隊

按 enqueue 把「待入隊」最左邊那個排到尾端,dequeue 從前端拿走最早進來的,peek 看一眼最前面。綠色是 front(下一個要走的)、紫色是 rear(剛排進來的)。看清楚:進出是兩頭,先進的先出。

◀ front 前端(dequeue 從這出)rear 尾端(enqueue 從這進)▶

待入隊(enqueue 拿最左邊)

10 個程式碼範例(Python)

從 deque 正解、Queue class,到 BFS、環形佇列、滑動視窗、優先佇列預告等應用。

常見陷阱

❌ 用 list.pop(0) 當出隊 —— O(n) 效能雷,改用 deque.popleft()。

❌ dequeue / front 前沒檢查空佇列 —— 對空的 popleft() 會 IndexError,先 if q:。

❌ 搞混 front / rear —— 用 deque 要 append 進(rear)、popleft 出(front);若寫成 append + pop 就變堆疊了。

❌ 需要後進先出卻用佇列 —— 那要的是堆疊(上一頁),別搞反。

🎯 換你了(先別急著查答案)

A. 依序 enqueue(1)、enqueue(2)、dequeue()、enqueue(3)、dequeue(),最後佇列剩什麼?front 是誰?
B. 為什麼 deque.popleft() 是 O(1),而 list.pop(0) 是 O(n)?差在哪裡?
C. 挑戰:堆疊和佇列都能「裝東西再拿出來」,但拿出來的順序差在哪?各舉一個真實情境。

把答案打到對話裡,我幫你對。