靜態循環隊列完整實現：環狀緩衝區設計與操作詳解

為何需要循環隊列？

普通順序隊列「假上溢」：尾指針達陣列末尾時，即使前方有空閒空間也無法入隊。循環隊列將陣列首尾相連成環，front、rear 以模運算環繞，充分利用空間。

關鍵設計決策

• 空間犧牲一元素：約定 (rear+1)%N == front 為「滿」，rear == front 為「空」，避免狀態模糊
• 陣列大小 N：實際可存 N-1 個元素
• 指針語義：
  • front：指向隊頭元素
  • rear：指向隊尾元素下一個位置（永遠空著）

完整 C 實現（含詳細註解）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define CAP 5  // 實際容量 4

typedef struct {
    int *base;   // 動態陣列基址
    int front;   // 隊頭索引
    int rear;    // 隊尾下一索引
} CirQueue;

void init(CirQueue *q) {
    q->base = malloc(CAP * sizeof(int));
    q->front = q->rear = 0;
}

bool is_full(CirQueue *q) {
    return (q->rear + 1) % CAP == q->front;
}

bool is_empty(CirQueue *q) {
    return q->rear == q->front;
}

bool enqueue(CirQueue *q, int val) {
    if (is_full(q)) return false;
    q->base[q->rear] = val;
    q->rear = (q->rear + 1) % CAP;
    return true;
}

bool dequeue(CirQueue *q, int *out) {
    if (is_empty(q)) return false;
    *out = q->base[q->front];
    q->front = (q->front + 1) % CAP;
    return true;
}

void traverse(CirQueue *q) {
    if (is_empty(q)) { puts("empty"); return; }
    for (int i = q->front; i != q->rear; i = (i + 1) % CAP)
        printf("%d ", q->base[i]);
    putchar('\n');
}

int length(CirQueue *q) {
    return (q->rear - q->front + CAP) % CAP;
}

int main() {
    CirQueue q; init(&q);
    enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); enqueue(&q, 4);
    traverse(&q);           // 1 2 3 4
    int v; dequeue(&q, &v); // v=1
    traverse(&q);           // 2 3 4
    printf("len=%d\n", length(&q)); // 3
    free(q.base);
    return 0;
}

操作流程圖解

初始: front=0, rear=0, base=[_,_,_,_,_]
enqueue(1): base[0]=1, rear=1
enqueue(2): base[1]=2, rear=2
enqueue(3): base[2]=3, rear=3
enqueue(4): base[3]=4, rear=4  (滿: (4+1)%5==0)
dequeue(): 取 base[0]=1, front=1
enqueue(5): base[4]=5, rear=0  (環繞)
狀態: front=1, rear=0, base=[_,1,2,3,4,5] → 有效 2,3,4,5

常見錯誤與避坑

1. 忘記取模 % CAP 導致索引越界
2. 判斷滿/空條件寫反
3. rear 指向「下一位置」而非「最後元素」，遍歷條件 i != rear
4. 動態分配失敗未檢查 NULL
5. 多執行緒環境無鎖操作導致競態（需原子操作或鎖）

應用場景

• 嵌入式中斷與主迴圈數據交換（環狀緩衝區）
• 網路封包重組、流控窗口
• 音訊/視訊串流解碼緩衝
• 任務調度器就緒隊列