C語言實現循環隊列：動態擴容、記憶體佈局與完整介面

編輯：關於C語言

C語言實現循環隊列：動態擴容、記憶體佈局與完整介面

C++ 有 std::queue，C 語言需自建。本文提供生產級循環隊列實現：環狀緩衝區佈局、O(1) 入隊/出隊、動態擴容（數據搬移策略）、空滿判別、首尾元素存取，代碼結構清晰，可直接嵌入嵌入式/系統專案。

資料結構設計

typedef int QueueElem;

typedef struct {
    int front;      // 隊頭索引（指向首元素）
    int rear;       // 隊尾索引（指向末元素下一位）
    int capacity;   // 容量（元素數）
    QueueElem* elems; // 動態陣列
} Queue;

不變量：0 ≤ front, rear < capacity，size = (rear - front + capacity) % capacity，empty ⇔ front == rear，full ⇔ (rear+1)%capacity == front（犧牲一格區分空滿）。

核心操作實現

初始化與銷毀

void queueInit(Queue* q, int capacity) {
    q->front = q->rear = 0;
    q->capacity = capacity;
    q->elems = (QueueElem*)malloc(capacity * sizeof(QueueElem));
}

void queueDestroy(Queue* q) {
    free(q->elems);
    q->elems = NULL;
    q->front = q->rear = q->capacity = 0;
}

空/大小查詢

bool queueEmpty(const Queue* q) { return q->front == q->rear; }
int queueSize(const Queue* q) {
    return (q->rear - q->front + q->capacity) % q->capacity;
}

入隊（含動態擴容）

void queuePush(Queue* q, QueueElem x) {
    // 判滿並擴容
    if ((q->rear + 1) % q->capacity == q->front) {
        int newCap = q->capacity * 2;
        QueueElem* tmp = (QueueElem*)malloc(newCap * sizeof(QueueElem));
        if (!tmp) return;  // 擴容失敗策略：可改為報錯/中止
        
        if (q->front < q->rear) {
            // 數據連續：單次 memcpy
            memcpy(tmp, q->elems + q->front, queueSize(q) * sizeof(QueueElem));
            q->rear = queueSize(q);
        } else if (q->front > q->rear) {
            // 數據環繞：兩段 memcpy
            int firstSeg = q->capacity - q->front;
            memcpy(tmp, q->elems + q->front, firstSeg * sizeof(QueueElem));
            memcpy(tmp + firstSeg, q->elems, q->rear * sizeof(QueueElem));
            q->rear = queueSize(q);
        }
        q->front = 0;
        free(q->elems);
        q->elems = tmp;
        q->capacity = newCap;
    }
    
    q->elems[q->rear] = x;
    q->rear = (q->rear + 1) % q->capacity;
}

出隊與首尾存取

void queuePop(Queue* q) {
    if (queueEmpty(q)) return;
    q->front = (q->front + 1) % q->capacity;
}

QueueElem queueFront(const Queue* q) { return q->elems[q->front]; }
QueueElem queueBack(const Queue* q) {
    int idx = (q->rear - 1 + q->capacity) % q->capacity;
    return q->elems[idx];
}

記憶體佈局圖解

容量 8，front=5, rear=3 (size=6)
索引:  0   1   2   3   4   5   6   7
數據: [F] [G] [ ] [ ] [ ] [A] [B] [C] [D] [E]
          ↑               ↑
        rear=3          front=5
邏輯順序: A B C D E F G