C / C++ / 系统课时

用链表实现动态队列

用链表实现动态队列

数组队列容量固定或需要扩容时,链式队列可以按需申请节点。关键不是“把链表接起来”这么简单,而是同时维护队头和队尾,并正确处理第一次入队、最后一次出队这两个会改变空队列状态的边界。

学习目标

  • 理解链式队列中头指针、尾指针与 FIFO 规则的对应关系
  • 能用 C 语言实现入队、出队和释放操作
  • 能正确处理空队列、单节点队列以及内存申请失败

头尾指针各负责什么

链式队列通常让 front 指向队头节点,让 rear 指向队尾节点。出队只从 front 删除,入队只在 rear 后追加,因此两种操作都不需要从头遍历链表,正常情况下时间复杂度都是 O(1)O(1)。

空队列时有一个很重要的不变量:front == NULL 与 rear == NULL 必须同时成立。第一次入队后,两者都指向唯一节点;最后一个节点出队后,也必须把两者同时恢复为 NULL。

链式队列头尾指针与空队列状态变化

完整实现

下面的示例把队列状态封装在 Queue 中。enqueue 负责创建并挂接新节点,dequeue 负责移除队头,并通过返回值区分“成功出队”和“队列为空”。

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

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

typedef struct {
    Node *front;
    Node *rear;
} Queue;

void init_queue(Queue *queue) {
    queue->front = NULL;
    queue->rear = NULL;
}

int enqueue(Queue *queue, int value) {
    Node *node = malloc(sizeof(Node));
    if (node == NULL) {
        return 0;
    }

    node->value = value;
    node->next = NULL;

    if (queue->rear == NULL) {
        // 空队列第一次入队:队头和队尾都必须指向新节点。
        queue->front = node;
        queue->rear = node;
    } else {
        queue->rear->next = node;
        queue->rear = node;
    }

    return 1;
}

int dequeue(Queue *queue, int *out_value) {
    if (queue->front == NULL) {
        return 0;
    }

    Node *old_front = queue->front;
    *out_value = old_front->value;
    queue->front = old_front->next;

    if (queue->front == NULL) {
        // 删除最后一个节点后,rear 不能继续指向已释放内存。
        queue->rear = NULL;
    }

    free(old_front);
    return 1;
}

void destroy_queue(Queue *queue) {
    int ignored;
    while (dequeue(queue, &ignored)) {
    }
}

int main(void) {
    Queue queue;
    init_queue(&queue);

    if (!enqueue(&queue, 10) ||
        !enqueue(&queue, 20) ||
        !enqueue(&queue, 30)) {
        fprintf(stderr, "enqueue failed\n");
        destroy_queue(&queue);
        return 1;
    }

    int value;
    while (dequeue(&queue, &value)) {
        printf("%d\n", value);
    }

    printf("empty=%s\n",
           queue.front == NULL && queue.rear == NULL ? "yes" : "no");
    return 0;
}

预期输出

text
10
20
30
empty=yes

输出顺序验证了 FIFO:先进入的 10 最先离开。最后的 empty=yes 则验证了最后一次出队后,front 和 rear 都已经恢复为空指针。

两个最容易写错的边界

第一次入队时,不能只修改 rear。如果原队列为空,front 也必须指向新节点,否则后续出队会误判为空。

最后一次出队时,不能只让 front 变成 NULL。旧的 rear 仍指向已经 free 的节点,会形成悬空指针;下一次入队若继续访问 rear->next,就可能触发未定义行为。

什么时候适合链式队列

当元素数量难以预估、希望按需增长,而且能够接受每个节点额外保存一个指针的开销时,链式队列很合适。它不需要整体扩容,也不要求一段连续内存。

如果容量上限明确、元素数量很多且追求更好的缓存局部性,循环数组队列通常更省内存、更快。选择链式结构的核心理由,是动态容量与稳定的 O(1)O(1) 头尾操作,而不是“链表一定比数组高级”。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用链表实现动态队列

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通