3.2 佇列與環形緩衝#

概念說明#

佇列（queue）遵守 FIFO：從尾端加入（enqueue）、從頭端取出（dequeue）。用 Python list 實作會踩到效能陷阱：list.pop(0) 要把後面所有元素左移一格，是 O(n)。正確做法有兩種：直接用 collections.deque（兩端都是 O(1)），或自製環形緩衝（circular buffer）——這也是本節的重點。

環形緩衝的原理#

配置一塊長度 N 的陣列，用兩個索引標記：

head：隊首（下一個要取出的位置）
tail：隊尾（下一個要放入的位置）

加入時資料放進 tail 位置，tail = (tail + 1) % N；取出時拿走 head 位置的資料，head = (head + 1) % N。取模讓索引「繞圈」，用完的空格可以重複利用，不必搬動任何元素。

判斷空與滿：若 head == tail 表示空；為了區分滿，保留一格不用（(tail + 1) % N == head 表示滿），或另外維護 count 計數（本節採用後者，較直觀）。

Python 實作#

class CircularQueue:
    def __init__(self, capacity):
        self._buf = [None] * capacity
        self._head = 0
        self._count = 0

    def __len__(self):
        return self._count

    def is_empty(self):
        return self._count == 0

    def is_full(self):
        return self._count == len(self._buf)

    def enqueue(self, x):
        if self.is_full():
            raise OverflowError("佇列已滿")
        tail = (self._head + self._count) % len(self._buf)
        self._buf[tail] = x
        self._count += 1

    def dequeue(self):
        if self.is_empty():
            raise IndexError("佇列為空")
        val = self._buf[self._head]
        self._buf[self._head] = None
        self._head = (self._head + 1) % len(self._buf)
        self._count -= 1
        return val

    def __repr__(self):
        order = [(self._head + i) % len(self._buf) for i in range(self._count)]
        return f"CircularQueue({[self._buf[i] for i in order]})"

q = CircularQueue(4)
for x in [1, 2, 3, 4]:
    q.enqueue(x)
print(q.dequeue())   # 1
q.enqueue(5)         # 5 繞回開頭的空格
print(q)             # [2, 3, 4, 5]
print(q.dequeue())   # 2

deque 與環形緩衝的比較#

from collections import deque

dq = deque(maxlen=5)     # 內建雙向佇列，滿了自動丟棄最舊
for x in [1, 2, 3, 4, 5, 6, 7]:
    dq.append(x)
print(dq)                # deque([3, 4, 5, 6, 7])

deque(maxlen=N) 的行為正是「滑動視窗」：新資料進來、最舊的自動淘汰，常用於網路封包緩衝、即時監控資料流。自製環形緩衝的價值在於：(1) 記憶體完全固定、零動態配置，適合嵌入式與即時系統；(2) 生產者與消費者可以各自操作 head/tail，是多執行緒緩衝的基礎。

複雜度分析#

操作	CircularQueue	list	deque
enqueue	O(1)	`append` O(1)	O(1)
dequeue	O(1)	`pop(0)` O(n)	O(1)
空間	固定 O(N)	O(n)	分塊 O(n)

環形緩衝取模運算取代了搬移，是「用固定空間換持續吞吐」的典範。

練習#

在 CircularQueue 加入 grow()：滿了自動加倍容量並把資料依邏輯順序搬到新陣列，說明搬移時為什麼不能直接複製原始陣列。
用 deque(maxlen=N) 實作「最近 60 秒的請求數」滑動視窗統計（搭配時間戳記）。
環形緩衝若不保留計數、也不留空格，head == tail 時無法區分空與滿。請查資料並說明三種常見解法。