數據結構：鏈隊列（Linked Queue）C語言完整實現

編輯：關於C語言

數據結構：鏈隊列（Linked Queue）C語言完整實現

鏈隊列是隊列的鏈式存儲結構，本質是僅允許表頭刪除、表尾插入的單鏈表。為了操作統一便捷，引入頭結點，空隊列時頭尾指針均指向頭結點。本文提供規範、完整的 C 語言實現，涵蓋初始化、銷毀、清空、判空、求長、取首尾、入隊、出隊、遍歷等全套操作。

一、類型定義

typedef int QElemType;

typedef struct QNode {
    QElemType data;
    struct QNode* next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;  // 隊頭指針（指向頭結點）
    QueuePtr rear;   // 隊尾指針（指向最後一個數據結點）
} LinkQueue;

二、核心操作實現

1. 初始化（帶頭結點）

void Init_LinkQueue(LinkQueue* Q) {
    QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
    if (!head) exit(EXIT_FAILURE);
    head->next = NULL;
    Q->front = Q->rear = head;  // 空隊列：頭尾均指向頭結點
}

2. 銷毀隊列（釋放所有結點含頭結點）

void Destroy_LinkQueue(LinkQueue* Q) {
    while (Q->front) {
        QueuePtr p = Q->front;
        Q->front = Q->front->next;
        free(p);
    }
    Q->rear = NULL;
}

3. 清空隊列（保留頭結點）

void Clear_LinkQueue(LinkQueue* Q) {
    // 釋放所有數據結點
    QueuePtr p = Q->front->next;
    while (p) {
        QueuePtr tmp = p;
        p = p->next;
        free(tmp);
    }
    Q->front->next = NULL;
    Q->rear = Q->front;  // 恢復空隊列狀態
}

4. 判空

int IsEmpty_LinkQueue(const LinkQueue* Q) {
    return Q->front == Q->rear;
}

5. 求長度

int GetLength_LinkQueue(const LinkQueue* Q) {
    int count = 0;
    QueuePtr p = Q->front->next;  // 跳過頭結點
    while (p) {
        ++count;
        p = p->next;
    }
    return count;
}

6. 取隊首元素

int GetHead_LinkQueue(const LinkQueue* Q, QElemType* x) {
    if (IsEmpty_LinkQueue(Q)) return 0;
    *x = Q->front->next->data;
    return 1;
}

7. 取隊尾元素

int GetRear_LinkQueue(const LinkQueue* Q, QElemType* x) {
    if (IsEmpty_LinkQueue(Q)) return 0;
    *x = Q->rear->data;
    return 1;
}

8. 入隊（尾插法）

int En_LinkQueue(LinkQueue* Q, QElemType x) {
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode));
    if (!p) return 0;
    p->data = x;
    p->next = NULL;
    Q->rear->next = p;
    Q->rear = p;
    return 1;
}

9. 出隊（頭刪法，跳過頭結點）

int De_LinkQueue(LinkQueue* Q, QElemType* x) {
    if (IsEmpty_LinkQueue(Q)) return 0;
    QueuePtr p = Q->front->next;  // 首個數據結點
    *x = p->data;
    Q->front->next = p->next;
    if (p->next == NULL)  // 刪除後隊列變空
        Q->rear = Q->front;
    free(p);
    return 1;
}

10. 遍歷輸出

void Print_LinkQueue(const LinkQueue* Q) {
    if (IsEmpty_LinkQueue(Q)) {
        printf("Queue empty\n");
        return;
    }
    QueuePtr p = Q->front->next;
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

三、測試主程序

int main(void) {
    LinkQueue Q;
    Init_LinkQueue(&Q);
    QElemType val;
    
    for (int i = 1; i <= 5; ++i) En_LinkQueue(&Q, i * 10);
    Print_LinkQueue(&Q);  // 10 20 30 40 50
    printf("Length: %d\n", GetLength_LinkQueue(&Q));
    
    GetHead_LinkQueue(&Q, &val); printf("Head: %d\n", val); // 10
    GetRear_LinkQueue(&Q, &val); printf("Rear: %d\n", val); // 50
    
    De_LinkQueue(&Q, &val); printf("Dequeue: %d\n", val); // 10
    Print_LinkQueue(&Q);  // 20 30 40 50
    
    Destroy_LinkQueue(&Q);
    return 0;
}

四、鏈隊列 vs 循環順序隊列對比

特性	鏈隊列	循環順序隊列
存儲結構	鏈表，動態分配	數組，固定大小
空間利用率	無內部碎片，有指針開銷	MAXSIZE-1，無指針開銷
擴容能力	天然支持，受限於內存	需重新分配數組並拷貝
隨機訪問	O(n)	O(1)
適用場景	長度難預估、頻繁增減、嵌入式	長度可預估、高性能、緩存友好