數據結構：循環順序隊列（單空槽法）C語言實現

編輯：關於C語言

數據結構：循環順序隊列（單空槽法）C語言實現

循環隊列是順序隊列的經典改進，通過「少用一個存儲單元」來區分「隊滿」與「隊空」狀態，避免額外標誌位或計數器。本文給出完整、規範的 C 語言實現，包含初始化、銷毀、入隊、出隊、查長度、取隊首隊尾、遍歷輸出等核心操作。

一、類型定義

#define MAXSIZE 100
typedef int ElemType;

typedef struct {
    ElemType* data;  // 動態數組基址
    int front;       // 隊首索引
    int rear;        // 隊尾索引（指向下一個插入位置）
} SqQueue;

二、核心操作實現

1. 初始化

void Init_SqQueue(SqQueue* Q) {
    Q->data = (ElemType*)malloc(MAXSIZE * sizeof(ElemType));
    if (!Q->data) exit(EXIT_FAILURE);
    Q->front = Q->rear = 0;
}

2. 銷毀

void Destroy_SqQueue(SqQueue* Q) {
    if (Q->data) {
        free(Q->data);
        Q->data = NULL;
    }
    Q->front = Q->rear = 0;
}

3. 清空

void Clear_SqQueue(SqQueue* Q) {
    Q->front = Q->rear = 0;
}

4. 判空

int IsEmpty_SqQueue(const SqQueue* Q) {
    return Q->rear == Q->front;
}

5. 判滿（關鍵：單空槽法）

int IsFull_SqQueue(const SqQueue* Q) {
    return (Q->rear + 1) % MAXSIZE == Q->front;
}

6. 獲取長度

int GetLength_SqQueue(const SqQueue* Q) {
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE;
}

7. 取隊首元素

int GetHead_SqQueue(const SqQueue* Q, ElemType* x) {
    if (IsEmpty_SqQueue(Q)) return 0;
    *x = Q->data[Q->front];
    return 1;
}

8. 取隊尾元素

int GetRear_SqQueue(const SqQueue* Q, ElemType* x) {
    if (IsEmpty_SqQueue(Q)) return 0;
    int idx = (Q->rear - 1 + MAXSIZE) % MAXSIZE;
    *x = Q->data[idx];
    return 1;
}

9. 入隊

int En_SqQueue(SqQueue* Q, ElemType x) {
    if (IsFull_SqQueue(Q)) return 0;
    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return 1;
}

10. 出隊

int De_SqQueue(SqQueue* Q, ElemType* x) {
    if (IsEmpty_SqQueue(Q)) return 0;
    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
    return 1;
}

11. 遍歷輸出

void Print_SqQueue(const SqQueue* Q) {
    if (IsEmpty_SqQueue(Q)) {
        printf("Queue empty\n");
        return;
    }
    int i = Q->front;
    int len = GetLength_SqQueue(Q);
    while (len--) {
        printf("%d ", Q->data[i]);
        i = (i + 1) % MAXSIZE;
    }
    printf("\n");
}

三、測試主程序

int main(void) {
    SqQueue Q;
    Init_SqQueue(&Q);
    ElemType val;
    
    for (int i = 1; i <= 5; ++i) En_SqQueue(&Q, i * 10);
    Print_SqQueue(&Q);          // 10 20 30 40 50
    printf("Length: %d\n", GetLength_SqQueue(&Q)); // 5
    
    De_SqQueue(&Q, &val); printf("Dequeue: %d\n", val); // 10
    GetHead_SqQueue(&Q, &val); printf("Head: %d\n", val); // 20
    GetRear_SqQueue(&Q, &val); printf("Rear: %d\n", val); // 50
    
    Destroy_SqQueue(&Q);
    return 0;
}

四、單空槽法 vs 計數器法對比

特性	單空槽法	計數器法
空間利用率	MAXSIZE-1	MAXSIZE
判滿判空邏輯	索引運算	直接比較 count
並發友好度	需額外鎖保護 front/rear	count 原子操作較易
代碼複雜度	稍高（模運算）	直觀簡單

五、常見錯誤避坑

malloc 大小錯誤：原文 malloc(sizeof(SqQueue) * MAXSIZE) 錯誤，應為 sizeof(ElemType) * MAXSIZE。
未檢查 malloc 返回值：分配失敗直接解引用導致崩潰。
出隊/取值未判空：直接訪問數組越界。
模運算負數處理：(rear - 1 + MAXSIZE) % MAXSIZE 確保非負。
銷毀後未置空指針：殘留懸空指針，二次 free 風險。