13、链式队列的实现

队列这东西，说白了就是「先来后到」。你想想看，生活中排队买票、食堂打饭，哪个不是先排的先走？在程序里，队列也是这个道理。今天咱们聊聊链式队列——用链表实现的队列。

我个人习惯，能用数组就用数组，毕竟简单。但有些场景，数组真不行。比如你事先不知道要存多少数据，或者数据量忽大忽小。这时候，链式队列就派上用场了。

13.1 链式队列的节点定义

链式队列的节点，其实就是一个单向链表的节点。每个节点存一个数据，再加一个指向下一个节点的指针。

我见过不少新手，上来就定义节点，结果忘了队列本身还需要两个指针——队头指针和队尾指针。嗯，这里要注意：队列结构体和节点结构体，是两码事。

// 链式队列的节点
typedef struct QueueNode {
    int data;                   // 数据域
    struct QueueNode *next;     // 指针域，指向下一个节点
} QueueNode;

// 链式队列结构体
typedef struct {
    QueueNode *front;           // 队头指针
    QueueNode *rear;            // 队尾指针
    int size;                   // 队列长度，方便统计
} LinkedQueue;

为什么队列结构体里要单独放 front 和 rear？

你想啊，如果只用一个头指针，入队的时候你得从头遍历到尾，每次都是 O(n) 的复杂度。这效率，谁受得了？所以咱们用两个指针，front 指向队头（出队用），rear 指向队尾（入队用）。

至于 size，这个看个人习惯。我建议加上，因为很多时候你需要知道队列里有多少元素。每次遍历链表去数，太傻了。

13.2 链式队列的入队与出队

入队操作，说白了就是在链表尾部加个新节点。出队操作，就是把链表头部的节点删掉。

先看入队：

// 入队
int enQueue(LinkedQueue *queue, int value) {
    if (queue == NULL) return -1;   // 空队列，直接返回
    
    // 创建新节点
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if (newNode == NULL) return -1; // 内存分配失败
    
    newNode->data = value;
    newNode->next = NULL;
    
    // 如果队列为空，新节点既是队头也是队尾
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        // 正常情况：挂到队尾后面
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    
    queue->size++;
    return 0;
}

这里有个细节，我当年踩过坑：空队列的情况要单独处理。如果队列是空的，front 和 rear 都是 NULL。这时候入队，你得让 front 和 rear 都指向新节点。否则，后面出队的时候 front 还是 NULL，一访问就崩。

再看一出队：

// 出队
int deQueue(LinkedQueue *queue, int *value) {
    if (queue == NULL || queue->front == NULL) {
        return -1;  // 队列为空，出队失败
    }
    
    QueueNode *temp = queue->front;  // 暂存队头节点
    *value = temp->data;             // 取出数据
    
    queue->front = temp->next;       // 队头后移
    
    // 如果出队后队列空了，rear 也要置空
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    free(temp);  // 释放原队头节点
    queue->size--;
    return 0;
}

出队的时候，我习惯用二级指针或者返回值来传出数据。上面这个写法，是把数据通过 value 指针传出来，返回值表示成功还是失败。这样更安全。

我曾经见过有人直接返回节点指针，让调用者自己去取数据。结果调用者忘了 free，内存泄漏了。嗯，这种事，能避免就避免。

13.3 链式队列的销毁

销毁队列，就是把所有节点都释放掉。这个操作看似简单，但有个坑：你不能先释放 front，再去找 next。因为 front 一释放，你就找不到 next 了。

正确的做法是：用一个临时指针，先保存下一个节点，再释放当前节点。

// 销毁队列
void destroyQueue(LinkedQueue *queue) {
    if (queue == NULL) return;
    
    QueueNode *current = queue->front;
    while (current != NULL) {
        QueueNode *next = current->next;  // 先保存下一个节点
        free(current);                     // 释放当前节点
        current = next;                    // 移动到下一个
    }
    
    // 重置队列状态
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

销毁之后，记得把 front 和 rear 都置 NULL，size 归零。不然别人拿着这个队列结构体继续用，会出大问题。

13.4 链式队列的完整代码

把上面几段拼起来，就是一个完整的链式队列实现。我一般还会加一个打印函数，方便调试。

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

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

typedef struct {
    QueueNode *front;
    QueueNode *rear;
    int size;
} LinkedQueue;

// 初始化队列
void initQueue(LinkedQueue *queue) {
    if (queue == NULL) return;
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

// 入队
int enQueue(LinkedQueue *queue, int value) {
    if (queue == NULL) return -1;
    
    QueueNode *newNode = (QueueNode *)malloc(sizeof(QueueNode));
    if (newNode == NULL) return -1;
    
    newNode->data = value;
    newNode->next = NULL;
    
    if (queue->rear == NULL) {
        queue->front = newNode;
        queue->rear = newNode;
    } else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
    
    queue->size++;
    return 0;
}

// 出队
int deQueue(LinkedQueue *queue, int *value) {
    if (queue == NULL || queue->front == NULL) {
        return -1;
    }
    
    QueueNode *temp = queue->front;
    *value = temp->data;
    
    queue->front = temp->next;
    if (queue->front == NULL) {
        queue->rear = NULL;
    }
    
    free(temp);
    queue->size--;
    return 0;
}

// 销毁队列
void destroyQueue(LinkedQueue *queue) {
    if (queue == NULL) return;
    
    QueueNode *current = queue->front;
    while (current != NULL) {
        QueueNode *next = current->next;
        free(current);
        current = next;
    }
    
    queue->front = NULL;
    queue->rear = NULL;
    queue->size = 0;
}

// 打印队列（调试用）
void printQueue(LinkedQueue *queue) {
    if (queue == NULL || queue->front == NULL) {
        printf("队列为空\n");
        return;
    }
    
    printf("队列内容（队头→队尾）：");
    QueueNode *current = queue->front;
    while (current != NULL) {
        printf("%d ", current->data);
        current = current->next;
    }
    printf("\n");
}

13.5 链式队列的核心逻辑图

下面这张图，把链式队列的入队、出队、销毁流程串起来了。你看一遍，应该就能理解整个数据流向。

13.6 链式队列 vs 顺序队列

最后，我整理了一个对比表。你在实际项目中选哪种，可以参考这个。

对比项	链式队列	顺序队列（数组）
空间分配	动态分配，按需增长	固定大小，可能溢出或浪费
入队/出队	O(1)，无扩容开销	O(1)，但扩容时 O(n)
内存碎片	有，频繁 malloc/free	无，连续内存
缓存友好	不友好，节点分散	友好，连续访问
适用场景	数据量不确定、频繁增删	数据量固定、性能要求高

我个人建议：嵌入式系统里，如果内存够用、数据量可控，优先用顺序队列。链式队列虽然灵活，但 malloc 和 free 的开销，在实时性要求高的场景下，可能会成为瓶颈。不过话说回来，如果你要处理的数据量变化很大，或者你不知道最大会有多少数据，那链式队列就是你的不二之选。

---

公众号:蓝海资料掘金营，微信deep3321