您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C >> 關於C

C 語言實現循環佇列：連續儲存、O(1) 入隊出隊完整教學

編輯：關於C

循環佇列基本概念

佇列遵循先進先出 (FIFO)。連續儲存（陣列）實現時，為避免資料搬移，採用環狀緩衝區：head 指向隊頭元素，tail 指向隊尾下一個可寫入位置。滿/空判斷犧牲一個儲存格：

空：head == tail
滿：(tail + 1) % capacity == head

實際可用容量 = capacity - 1。

資料結構定義

typedef struct {
    int *data;      // 動態陣列
    int capacity;   // 總大小（含犧牲格）
    int head;       // 隊頭索引
    int tail;       // 隊尾下一個索引
} CircularQueue;

核心操作實現

// 建立佇列，capacity 為想要的最大元素數，內部 +1
CircularQueue *cq_create(int capacity) {
    CircularQueue *q = malloc(sizeof(CircularQueue));
    q->capacity = capacity + 1;
    q->data = malloc(q->capacity * sizeof(int));
    q->head = q->tail = 0;
    return q;
}

// 入隊
int cq_enqueue(CircularQueue *q, int value) {
    if (cq_is_full(q)) return -1; // 失敗
    q->data[q->tail] = value;
    q->tail = (q->tail + 1) % q->capacity;
    return 0;
}

// 出隊
int cq_dequeue(CircularQueue *q) {
    if (cq_is_empty(q)) return -1;
    q->head = (q->head + 1) % q->capacity;
    return 0;
}

// 取隊頭值（不移除）
int cq_front(CircularQueue *q, int *out) {
    if (cq_is_empty(q)) return -1;
    *out = q->data[q->head];
    return 0;
}

// 狀態檢查
int cq_is_empty(CircularQueue *q) { return q->head == q->tail; }
int cq_is_full(CircularQueue *q) { return (q->tail + 1) % q->capacity == q->head; }
int cq_size(CircularQueue *q) { return (q->tail - q->head + q->capacity) % q->capacity; }

// 釋放
void cq_destroy(CircularQueue *q) {
    free(q->data);
    free(q);
}

除錯視覺化函數

void cq_debug(CircularQueue *q) {
    printf("=== Queue Debug ===\n");
    printf("cap=%d head=%d tail=%d size=%d\n", q->capacity, q->head, q->tail, cq_size(q));
    for (int i = 0; i < q->capacity; i++) {
        int is_head = (i == q->head);
        int is_tail = (i == q->tail);
        printf("[%2d] %5d %s%s\n", i, q->data[i],
               is_head ? "←HEAD" : "",
               is_tail ? "←TAIL" : "");
    }
    printf("===================\n");
}

完整測試程式

int main() {
    CircularQueue *q = cq_create(5); // 實際可存 5 個
    int val = 100;

    printf("--- 入隊測試 ---\n");
    while (cq_enqueue(q, val++) == 0) {
        printf("Enqueue %d, size=%d\n", val-1, cq_size(q));
    }
    cq_debug(q); // 應顯示滿

    printf("--- 出隊測試 ---\n");
    int out;
    while (cq_front(q, &out) == 0) {
        printf("Front=%d, ", out);
        cq_dequeue(q);
        printf("size=%d\n", cq_size(q));
    }
    cq_debug(q); // 應顯示空

    cq_destroy(q);
    return 0;
}

輸出範例

--- 入隊測試 ---
Enqueue 100, size=1
Enqueue 101, size=2
Enqueue 102, size=3
Enqueue 103, size=4
Enqueue 104, size=5
=== Queue Debug ===
cap=6 head=0 tail=5 size=5
[ 0]   100 ←HEAD
[ 1]   101
[ 2]   102
[ 3]   103
[ 4]   104
[ 5]     0 ←TAIL
===================
--- 出隊測試 ---
Front=100, size=4
Front=101, size=3
Front=102, size=2
Front=103, size=1
Front=104, size=0
=== Queue Debug ===
cap=6 head=5 tail=5 size=0
[ 0]   100
[ 1]   101
[ 2]   102
[ 3]   103
[ 4]   104
[ 5]     0 ←HEAD←TAIL
===================