靜態循環隊列完整實現與核心操作詳解

循環隊列：解決「假上溢」的經典數據結構

順序隊列因頭尾指針單向移動，導致釋放空間無法重用，產生「假上溢」。循環隊列將存儲空間邏輯首尾相連成環，配合模運算實現指針循環，充分利用數組容量。

核心設計決策：犧牲一個元素區分滿/空

• 空條件：front == rear
• 滿條件：(rear + 1) % MAX_SIZE == front
• 此法下隊列實際可用容量為 MAX_SIZE - 1。

關鍵操作流程

完整 C 實現（含動態分配）

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

#define MAX_SIZE 5

typedef struct {
    int *base;   // 動態數組基址
    int front;   // 隊頭下標
    int rear;    // 隊尾下標
} Queue;

void init(Queue *q) {
    q->base = malloc(sizeof(int) * MAX_SIZE);
    if (!q->base) exit(EXIT_FAILURE);
    q->front = q->rear = 0;
}

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

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

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

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

void traverse(Queue *q) {
    if (is_empty(q)) { puts("隊列為空"); return; }
    printf("隊列元素：");
    for (int i = q->front; i != q->rear; i = (i + 1) % MAX_SIZE)
        printf("%d ", q->base[i]);
    putchar('\n');
}

int length(Queue *q) {
    int len = 0;
    for (int i = q->front; i != q->rear; i = (i + 1) % MAX_SIZE) len++;
    return len;
}

int main() {
    Queue q; init(&q);
    enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); enqueue(&q, 4);
    traverse(&q);          // 1 2 3 4
    int val;
    dequeue(&q, &val);     // 出隊 1
    printf("出隊: %d\n", val);
    traverse(&q);          // 2 3 4
    printf("長度: %d\n", length(&q));
    free(q.base);
    return 0;
}

常見誤區提醒

1. 指針僅在入/出隊時移動，遍歷、查長度等操作必須使用臨時變量迭代，不可修改 front/rear。
2. rear 指向「最後有效元素的下一個位置」，而非最後元素本身。
3. 動態分配數組時務必檢查 malloc 返回值，避免空指針解引用。

應用場景

所有涉及「先進先出」且數據流具備時間順序特性的場景：打印任務調度、網絡數據包緩衝、瀏覽器歷史記錄、生產者-消費者模型等。