C 語言實作循環佇列：完整程式碼與運作原理

資料結構定義

#define MAX_SIZE 50
typedef int ElementType;

typedef struct {
    ElementType data[MAX_SIZE];
    int front;  // 指向隊頭元素
    int rear;   // 指向隊尾元素的下一個位置
} CirQueue;

採用環狀陣列，front == rear 表示空，(rear + 1) % MAX_SIZE == front 表示滿（犧牲一格區分）。

核心操作實作

初始化

void init_queue(CirQueue *q) {
    q->front = q->rear = 0;
}

判斷空/滿

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

入隊

bool enqueue(CirQueue *q, ElementType x) {
    if (is_full(q)) return false;
    q->data[q->rear] = x;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

出隊

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

取隊頭/隊尾（不移除）

bool peek_front(const CirQueue *q, ElementType *out) {
    if (is_empty(q)) return false;
    *out = q->data[q->front];
    return true;
}

bool peek_rear(const CirQueue *q, ElementType *out) {
    if (is_empty(q)) return false;
    int idx = (q->rear - 1 + MAX_SIZE) % MAX_SIZE;
    *out = q->data[idx];
    return true;
}

取得長度

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

完整測試主程式

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

#define MAX_SIZE 50
typedef int ElementType;

typedef struct { ElementType data[MAX_SIZE]; int front, rear; } CirQueue;

// ... 上述所有函數定義 ...

int main(void) {
    CirQueue q;
    init_queue(&q);

    printf("依序入隊 10, 20, 30, 40, 50\n");
    for (int i = 10; i <= 50; i += 10) enqueue(&q, i);
    printf("隊列長度: %d\n", length(&q));

    ElementType val;
    printf("隊頭: "); peek_front(&q, &val); printf("%d\n", val);
    printf("隊尾: "); peek_rear(&q, &val); printf("%d\n", val);

    printf("出隊兩個: ");
    dequeue(&q, &val); printf("%d ", val);
    dequeue(&q, &val); printf("%d\n", val);

    printf("入隊 60, 70\n");
    enqueue(&q, 60); enqueue(&q, 70);
    printf("目前隊列內容 (front→rear): ");
    for (int i = q.front; i != q.rear; i = (i + 1) % MAX_SIZE)
        printf("%d ", q.data[i]);
    printf("\n");

    return 0;
}

執行結果示例

依序入隊 10, 20, 30, 40, 50
隊列長度: 5
隊頭: 10
隊尾: 50
出隊兩個: 10 20
入隊 60, 70
目前隊列內容 (front→rear): 30 40 50 60 70

關鍵優勢與注意事項

• O(1) 入隊/出隊，無資料搬移
• 固定記憶體配置，適合嵌入式/即時系統
• 犧牲一格空間區分滿/空，或改用 count 計數器
• 非執行緒安全，多執行緒需加鎖或使用無鎖環形緩衝區