C 語言實現鏈式隊列 ADT：完整代碼與關鍵缺陷分析

前言

隊列是基礎數據結構之一，本文提供一個基於鏈表的隊列 ADT 完整實現，包含創建、入隊、出隊、遍歷、銷毀等操作，並深度分析代碼中存在的內存洩漏、邏輯錯誤與不規範之處，作為學習參考與代碼審查練習。

一、ADT 接口設計

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

typedef struct Queue {
    int size;
    struct Node *first;
    struct Node *end;
} *Queue;

// 核心操作
Queue CreatEmptyQueue(void);
int isEmpty(Queue q);
int isFull(Queue q);
int QueueIn(Queue q, int data);
int QueueOut(Queue q, int *data);
void printQueue(Queue q);
void destoryQueue(Queue q);

二、完整實現代碼（含註釋）

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>

#define MAX_SIZE 10

Queue CreatEmptyQueue() {
    Queue q = malloc(sizeof(struct Queue));
    if (!q) { perror("malloc queue"); exit(EXIT_FAILURE); }
    q->size = 0;
    q->first = q->end = NULL;
    return q;
}

int isEmpty(Queue q) { return q->size <= 0; }
int isFull(Queue q)  { return q->size >= MAX_SIZE; }

int QueueIn(Queue q, int data) {
    assert(q);
    if (isFull(q)) { fprintf(stderr, "Queue full\n"); return -1; }

    Node p = malloc(sizeof(struct Node));
    if (!p) { perror("malloc node"); return -1; }
    p->data = data;
    p->next = NULL;

    if (isEmpty(q)) {
        q->first = q->end = p;
    } else {
        q->end->next = p;
        q->end = p;
    }
    q->size++;
    return 0;
}

int QueueOut(Queue q, int *data) {
    assert(q && data);
    if (isEmpty(q)) { fprintf(stderr, "Queue empty\n"); return -1; }

    Node p = q->first;
    *data = p->data;
    q->first = p->next;
    q->size--;
    if (isEmpty(q)) q->end = NULL;  // 關鍵：最後一個節點出隊後 end 置 NULL
    free(p);
    return 0;
}

void printQueue(Queue q) {
    assert(q);
    printf("size=%d: ", q->size);
    for (Node p = q->first; p; p = p->next)
        printf("%d ", p->data);
    putchar('\n');
}

void destoryQueue(Queue q) {
    assert(q);
    Node p = q->first, next;
    while (p) {
        next = p->next;
        free(p);
        p = next;
    }
    free(q);  // 僅釋放隊列頭結構，調用者需自行置 NULL
}

三、main 測試用例

int main() {
    Queue q = CreatEmptyQueue();
    int data;

    // 空隊列出隊
    if (QueueOut(q, &data) == 0) printf("out: %d\n", data);
    else puts("empty queue");

    // 入隊超過 MAX_SIZE
    for (int i = 0; i < MAX_SIZE + 5; i++)
        QueueIn(q, i * 5 + 10);

    printQueue(q);
    destoryQueue(q);
    return 0;
}

四、關鍵缺陷深度剖析 ⚠️

五、改進版接口建議

// 隱藏實現細節的不透明指針風格（.h）
typedef struct Queue *QueueHandle;

QueueHandle queue_create(int max_size);
void queue_destroy(QueueHandle *q);  // 雙重指針置空
int queue_push(QueueHandle q, int data);
int queue_pop(QueueHandle q, int *data);
int queue_size(QueueHandle q);
bool queue_empty(QueueHandle q);

總結

鏈式隊列實現看似簡單，實則暗藏 指針所有權轉移、邊界條件、錯誤處理策略、接口封裝 等工程核心課題。建議學習者：

1. 先寫出能跑通的版本
2. 再按上表逐項修復缺陷
3. 最後嘗試不透明指針封裝，體會 ADT 真正含義