環形隊列 (Circular/Ring Buffer) 是有界、FIFO、O(1) 入隊出隊、零內存碎片、極致緩存友好**的數據結構王者。本文從數組佈局與頭尾指針語義、偽滿/偽空判斷策略、動態擴容權衡、無鎖單生產單消費 (SPSC) 實現、C++ RAII 封裝、測試驗證矩陣**提供完整工程指南。
typedef struct {
int *buf; // 數據緩衝區
size_t cap; // 容量 (必須是 2 的冪次以利用位運算優化，或任意值用取模)
size_t head; // 隊頭索引 (下一個出隊位置)
size_t tail; // 隊尾索引 (下一個入隊位置)
// 可選：原子變量用於無鎖版
} RingQueue;
不變量：
head == tail(tail + 1) % cap == head (犧牲 1 個槽位區分滿/空) — 經典偽滿策略(tail - head + cap) % cap
RingQueue* rq_create(size_t capacity) {
RingQueue *q = malloc(sizeof(RingQueue));
if (!q) return NULL;
q->buf = malloc(capacity * sizeof(int));
if (!q->buf) { free(q); return NULL; }
q->cap = capacity;
q->head = q->tail = 0;
return q;
}
void rq_destroy(RingQueue *q) {
if (q) { free(q->buf); free(q); }
}
// 入隊：返回 0 成功，-1 滿
int rq_push(RingQueue *q, int val) {
if (!q) return -1;
size_t next_tail = (q->tail + 1) % q->cap;
if (next_tail == q->head) return -1; // 滿
q->buf[q->tail] = val;
q->tail = next_tail;
return 0;
}
// 出隊：返回 0 成功，-1 空
int rq_pop(RingQueue *q, int *out_val) {
if (!q || !out_val) return -1;
if (q->head == q->tail) return -1; // 空
*out_val = q->buf[q->head];
q->head = (q->head + 1) % q->cap;
return 0;
}
size_t rq_size(const RingQueue *q) {
return (q->tail - q->head + q->cap) % q->cap;
}
size_t rq_capacity(const RingQueue *q) {
return q->cap;
}
| 策略 | 空條件 | 滿條件 | 可用容量 | 優缺點 |
|---|---|---|---|---|
| 犧牲一槽位 (經典) | head == tail | (tail+1)%cap == head | cap - 1 | 最簡單，無額外變量，浪費 1 槽 |
| 額外 size 計數器 | size == 0 | size == cap | cap | 100% 利用率，需原子操作 size 變量 (併發開銷) |
| 標誌位 flag | head==tail && !flag | head==tail && flag | cap | 無 size 開銷，但 flag 讀寫需原子/鎖 |
推薦：單線程/鎖保護用 size 計數器 (代碼清晰、100% 利用率)；無鎖 SPSC 用 犧牲一槽位 (無共享變量、純指針 CAS-free)。
單生產者單消費者場景，head 僅消費者寫、生產者讀；tail 僅生產者寫、消費者讀。**無需 CAS**，僅需內存序保證可見性。
#include
typedef struct {
int *buf;
size_t cap;
_Atomic size_t head; // 消費者寫
_Atomic size_t tail; // 生產者寫
} LockFreeRingQueue;
// 生產者
int lfrq_push(LockFreeRingQueue *q, int val) {
size_t tail = atomic_load_explicit(&q->tail, memory_order_relaxed);
size_t next_tail = (tail + 1) % q->cap;
// 載入 head (acquire 序確保看到消費者最新 head)
size_t head = atomic_load_explicit(&q->head, memory_order_acquire);
if (next_tail == head) return -1; // 滿
q->buf[tail] = val; // 寫數據
// 發布 tail (release 序確保數據寫入對消費者可見)
atomic_store_explicit(&q->tail, next_tail, memory_order_release);
return 0;
}
// 消費者
int lfrq_pop(LockFreeRingQueue *q, int *out_val) {
size_t head = atomic_load_explicit(&q->head, memory_order_relaxed);
// 載入 tail (acquire 序確保看到生產者最新 tail)
size_t tail = atomic_load_explicit(&q->tail, memory_order_acquire);
if (head == tail) return -1; // 空
*out_val = q->buf[head]; // 讀數據
size_t next_head = (head + 1) % q->cap;
// 發布 head (release 序)
atomic_store_explicit(&q->head, next_head, memory_order_release);
return 0;
}
關鍵點：memory_order_acquire/release 構成 Release-Acquire 順序一致性，保證生產者寫入數據 -> 發布 tail -> 消費者讀取 tail -> 讀取數據 的有序性。relaxed 僅用於本線程讀取自身寫入的索引。
template
class RingBuffer {
T data_[N];
size_t head_ = 0, tail_ = 0, size_ = 0;
public:
bool push(const T& v) {
if (size_ == N) return false;
data_[tail_] = v;
tail_ = (tail_ + 1) % N;
++size_;
return true;
}
bool pop(T& out) {
if (size_ == 0) return false;
out = data_[head_];
head_ = (head_ + 1) % N;
--size_;
return true;
}
bool front(T& out) const { if (size_==0) return false; out=data_[head_]; return true; }
size_t size() const { return size_; }
size_t capacity() const { return N; }
bool empty() const { return size_ == 0; }
bool full() const { return size_ == N; }
void clear() { head_=tail_=size_=0; }
};
環形隊列通常不擴容** (破壞 O(1) 保證、指針失效、內存抖動)。若必須：
memcpy)。替代方案：預分配足夠大容量、或用 std::deque/boost::circular_buffer (支持擴容)。
| 測試 | 描述 | 驗證點 |
|---|---|---|
| 基本 FIFO | Push 1..N, Pop 驗證順序 | 邏輯正確性 |
| 環繞 | Push 滿, Pop 一半, Push 填滿, Pop 全部 | 索引環繞、偽滿判斷 |
| 邊界 | 空 Pop、滿 Push、容量 1 | 返回碼、不崩潰 |
| 併發 SPSC | 生產者線程 Push 100萬, 消費者 Pop 驗證無丟失/重複/順序 | 無鎖正確性、內存序 |
| 併發 MPMC | 多生產多消費 (加鎖版)，壓力測試 | 鎖競爭、死鎖自由 |
| 性能基準 | 單線程 Push/Pop 1億次 耗時、對比 std::queue | 常數因子、緩存命中 |
| 內存序驗證 | 編譯器屏障測試、TSAN/Helgrind 檢測 | 無數據競爭 |
cap & (cap - 1) == 0，用 & (cap - 1) 替代 % cap，消除除法指令。head 和 tail 分離至不同緩存行 (64 Bytes)，防止偽共享 導致多核性能崩塌。void* + 元素大小 或 C++ 模板支持任意類型 (需構造/析構)。push_n/pop_n 減少函數調用/原子操作開銷，利用 memcpy 向量化。環形隊列以「固定內存、頭尾指針追趕、模運算封閉」的極簡幾何邏輯，實現了理論最優的有界 FIFO 語義。掌握偽滿策略選擇、無鎖 SPSC 內存序模型、緩存行對齊防偽共享、批量向量化**四大工程精髓，即可在高性能網絡框架、實時音視頻管線、Lock-Free 數據交換、嵌入式中斷緩衝等核心鏈路中構建零拷貝、零鎖、零分配的高吞吐通道。
