链式队列

为什么需要链式队列

队列是一种**先进先出（FIFO, First In First Out）**的线性数据结构。生活中排队买票就是典型的队列——先到的人先服务，后到的人排在队尾。

在操作系统的进程调度、网络数据包缓冲、BFS 广度优先搜索等场景中，队列都是核心结构。408 考研中，队列与栈并列为重点章节，链式队列则是队列最常见的链式存储实现。

相比于顺序队列（循环队列），链式队列不会出现假溢出问题，且队列长度可以动态变化，不需要预先分配固定大小的空间。

核心思想

链式队列的核心特点：

FIFO 原则：只能从队尾（rear）插入，从队头（front）删除
两个指针：front 指向队头结点（或头结点），rear 指向队尾结点
带头结点：通常设置一个头结点，使空队列和非空队列的操作统一

结点与队列的定义：

// 链式队列结点
typedef struct LinkNode {
    int data;
    struct LinkNode *next;
} LinkNode;

// 链式队列（带头结点）
typedef struct {
    LinkNode *front;  // 队头指针，指向头结点
    LinkNode *rear;   // 队尾指针，指向最后一个元素
} LinkQueue;

队列状态示意：

空队列:   front -> [头结点] <- rear
                     next=NULL

非空队列: front -> [头结点] -> [a₁] -> [a₂] -> [a₃] <- rear
                                                  next=NULL

判空条件：Q.front == Q.rear（即 front 和 rear 都指向头结点）。

交互可视化

通过下方的交互动画，你可以逐步观察链式队列的执行过程：

加载可视化中...

操作详解

入队操作

在队尾插入新元素，需要修改 rear 指针。

关键步骤：

创建新结点，赋值
将新结点插入到队尾结点之后
rear 指向新结点

// 入队（带头结点）
bool EnQueue(LinkQueue *Q, int x) {
    LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));
    if (s == NULL) return false;  // 内存分配失败
    s->data = x;
    s->next = NULL;
    Q->rear->next = s;  // 新结点插入到 rear 之后
    Q->rear = s;         // 修改队尾指针
    return true;
}

出队操作

删除队头元素（头结点之后的第一个结点），需要注意队列中只剩一个元素时要同时修改 rear。

关键步骤：

判断队列是否为空
取出队头结点（头结点的下一个结点）
修改头结点的 next 指针
若删除后队列为空，需将 rear 重新指向头结点
释放被删结点，表长减 1

// 出队（带头结点）
bool DeQueue(LinkQueue *Q, int *x) {
    if (Q->front == Q->rear) return false;  // 队空
    LinkNode *p = Q->front->next;  // p 指向队头元素
    *x = p->data;
    Q->front->next = p->next;      // 修改头结点 next
    if (Q->rear == p)              // 若原队列只有一个结点
        Q->rear = Q->front;        // rear 指回头结点
    free(p);
    return true;
}

复杂度分析

操作	时间复杂度	说明
入队	O(1)	直接在 rear 后插入
出队	O(1)	直接删除 front 后的结点
取队头元素	O(1)	访问 front->next->data
判空	O(1)	比较 front 与 rear

空间复杂度：O(n)，每个元素需要额外存储一个指针域。

考研高频考点

⭐ 链式队列的判空条件：Q.front == Q.rear（选择题高频）
⭐ 出队时只剩一个元素需要同时修改 rear 指针（代码题易错点）
⭐ 链式队列 vs 循环队列的优缺点对比（简答题常考）
⭐ 带头结点与不带头结点的链式队列操作差异（选择题/代码题）
队列在层序遍历（BFS）中的应用（算法题必备）
队列的 FIFO 特性与栈的 LIFO 特性对比（概念题）

交互体验

前往完整可视化页面 →

巩固练习

刷题平台即将推出，敬请期待...

链式队列 ​

为什么需要链式队列 ​

核心思想 ​

交互可视化 ​

操作详解 ​

入队操作 ​

出队操作 ​

复杂度分析 ​

考研高频考点 ​

相关文章