資料結構教學：C語言實作鏈式佇列完整指南

鏈式佇列：從節點定義到完整操作實作

鏈式佇列以鏈結串列實現先進先出（FIFO）資料結構，動態分配記憶體、無固定容量限制。本文完整呈現從結構定義、初始化、入隊、出隊到遍歷銷毀的完整實作。

資料結構定義

typedef int QElemType;

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

typedef struct {
    QueuePtr front; // 頭指標（指向哨兵節點）
    QueuePtr rear;  // 尾指標
} LinkQueue;

核心操作函數

• 初始化：建立哨兵節點，front 與 rear 均指向它
• 入隊：尾部插入新節點，更新 rear 指標
• 出隊：移除頭節點後的第一個節點，處理佇列變空情況
• 判斷空佇列：front == rear
• 獲取長度：遍歷計數
• 清空佇列：釋放所有資料節點，重置指標
• 列印佇列：遍歷輸出資料
• 取隊首元素：不移除，僅讀取

關鍵程式碼片段

void en_Queue(LinkQueue *q, QElemType e) {
    QueuePtr temp = (QueuePtr)malloc(sizeof(QNode));
    if (temp) {
        temp->data = e; temp->next = NULL;
        q->rear->next = temp; q->rear = temp;
    }
}

void de_Queue(LinkQueue *q, QElemType *e) {
    if (q->front == q->rear) return; // 空佇列
    QueuePtr temp = q->front->next;
    if (q->front->next == q->rear) q->rear = q->front; // 最後一個元素
    *e = temp->data;
    q->front->next = temp->next;
    free(temp);
}

主程式測試流程

int main() {
    LinkQueue q;
    create_Queue(&q); // 互動式建立佇列
    int top; top_Queue(&q, &top);
    printf("隊頭元素: %d\n", top);
    int len = getlength_Queue(&q);
    for (int i = 0; i < len; i++) {
        int k; de_Queue(&q, &k);
        printf("%d ", k);
    }
    clear(&q); return 0;
}

執行結果示意

設計重點總結

• 使用哨兵節點簡化邊界條件處理
• 動態記憶體管理需嚴謹配對 malloc/free
• 出隊時需處理佇列變空導致 rear 指標回歸的特殊情況
• 清空函數必須釋放哨兵節點記憶體

此實作為理解動態資料結構、指標操作與記憶體管理提供了紮實範例。