C 語言鏈表實作隊列（動態記憶體版）

鏈式隊列優勢

• 無固定容量限制（受限於記憶體）。
• 無需預留空位區分滿/空，head==NULL 即為空。
• 出隊直接釋放頭節點，head 移至下一節點。

關鍵設計：虛擬頭節點

引入一個不存資料的 head 節點，tail 指向最後一個有效節點。
空隊列：head->next == NULL 且 tail == head。
入隊：tail->next = new_node; tail = new_node;
出隊：tmp = head->next; head->next = tmp->next; if (!head->next) tail = head; free(tmp);

完整程式碼

/*************************************************************************
> File Name: linkqueue.c
> Author: Baniel Gao
> Mail: createchance@163.com
> Blog: blog.csdn.net/createchance
> Created Time: Fri 20 Dec 2013 01:53:21 PM CST
***********************************************************************/
#include <stdio.h>
#include <stdlib.h>

typedef struct Node {
    int data;
    struct Node *next;
} Node;

typedef struct {
    int capacity;
    int size;
    Node *head; // 虛擬頭節點
    Node *tail;
} LinkQueue;

Node *node_create(int val) {
    Node *n = malloc(sizeof(Node));
    n->data = val; n->next = NULL;
    return n;
}

LinkQueue *lq_init(int cap) {
    LinkQueue *q = malloc(sizeof(LinkQueue));
    q->capacity = cap; q->size = 0;
    q->head = node_create(0); // dummy
    q->tail = q->head;
    return q;
}

int lq_is_full(LinkQueue *q) { return q->size == q->capacity; }
int lq_is_empty(LinkQueue *q) { return q->size == 0; }

int lq_enqueue(LinkQueue *q, int val) {
    if (lq_is_full(q)) return -1;
    Node *n = node_create(val);
    q->tail->next = n;
    q->tail = n;
    q->size++;
    return 0;
}

int lq_dequeue(LinkQueue *q, int *out) {
    if (lq_is_empty(q)) return -1;
    Node *tmp = q->head->next;
    *out = tmp->data;
    q->head->next = tmp->next;
    if (!q->head->next) q->tail = q->head; // 變空
    free(tmp);
    q->size--;
    return 0;
}

void lq_free(LinkQueue *q) {
    Node *cur = q->head;
    while (cur) { Node *nxt = cur->next; free(cur); cur = nxt; }
    free(q);
}

int main() {
    LinkQueue *q = lq_init(10);
    int val = 100;
    while (lq_enqueue(q, val++) == 0);
    int x;
    while (lq_dequeue(q, &x) == 0) printf("%5d", x);
    putchar('\n');
    lq_free(q);
    return 0;
}

執行結果

100  101  102  103  104  105  106  107  108  109

與陣列隊列比較

常見錯誤避坑

• 出隊未更新 tail：刪除最後一節點時必須 tail = head，否則下次入隊會接在已釋放記憶體後 → 段錯誤。
• 虛擬頭節點資料誤用：head->data 無意義，勿讀寫。
• 未檢查 malloc 失敗：生產碼需處理 NULL 回傳。