考研全科复习

Appearance

408 ​

数据结构 ​

DS-03-02 队列的基本概念与实现（循环队列/链队列） ​

一、定位信息 ​

项目内容
所属圈层核心层
考点热度H级（高频重点） — 循环队列是408选择题的高频考点，判空/判满条件几乎隔年必考，大题中也常作为算法设计的基础数据结构出现，累计分值5–8分
前置知识回顾需掌握"线性表的基本概念"（DS-02-01）和"顺序存储与链式存储"（DS-02-02、DS-02-03），以及"栈的基本概念"（DS-03-01）用于对比理解
知识网络定位队列是另一种受限线性表（两端操作），与栈互为对比；循环队列是队列的标准实现方式，是广度优先搜索（BFS）、操作系统进程调度等知识的基础

二、知识点讲解 ​

2.1 队列的定义 ​

队列（Queue） 是只允许在一端（队尾，Rear）插入、在另一端（队头，Front）删除的线性表。

队列遵循 先进先出（FIFO, First In First Out）原则：最先入队的元素最先出队。

直观理解：队列就像排队买票——新来的人从队尾排起，队头的人先买到票离开。

例子：依次将 A、B、C 入队，然后执行两次出队操作：

  • 入队顺序：A → B → C（A在队头，C在队尾）
  • 第一次出队得到 A
  • 第二次出队得到 B
  • 队列中剩余：C

2.2 队列的基本操作 ​

操作功能时间复杂度
InitQueue(&Q)初始化空队列O(1)O(1)
EnQueue(&Q, e)元素 e 入队（队尾插入）O(1)O(1)
DeQueue(&Q, &e)队头元素出队，用 e 返回O(1)O(1)
GetHead(Q, &e)读取队头元素（不出队）O(1)O(1)
QueueEmpty(Q)判断队列是否为空O(1)O(1)

2.3 普通队列的问题 ​

用数组实现普通队列时，会出现**"假溢出"**问题：

随着不断入队和出队，front 和 rear 都向后移动。即使数组前面有空闲位置，rear 已经到达数组末尾，无法再入队——这就是"假溢出"。

解决方案：将数组首尾相连，形成循环队列。

2.4 循环队列 ​

循环队列 使用数组实现，通过取模运算将数组逻辑上首尾相连。

核心公式：

  • 入队：rear = (rear + 1) % MaxSize
  • 出队：front = (front + 1) % MaxSize
  • 队列长度：(rear - front + MaxSize) % MaxSize

关键问题：如何区分队空和队满？

方法一：牺牲一个存储单元

  • 队空条件：front == rear
  • 队满条件：(rear + 1) % MaxSize == front
  • 可用空间：MaxSize - 1 个

方法二：增设 size 变量

  • 用 size 记录元素个数
  • 队空：size == 0
  • 队满：size == MaxSize

方法三：增设 tag 标志

  • tag = 0 表示最近一次操作是删除（可导致队空）
  • tag = 1 表示最近一次操作是插入（可导致队满）
  • 队空：front == rear && tag == 0
  • 队满：front == rear && tag == 1

408考试重点：方法一（牺牲一个空间）是最常考的方式，必须熟练掌握。

c
#define MaxSize 100           // 队列最大容量

typedef struct {
    ElemType data[MaxSize];   // 存放队列元素的数组
    int front;                // 队头指针，指向队头元素
    int rear;                 // 队尾指针，指向队尾元素的下一个位置
} SqQueue;

// 初始化：队头队尾都指向0
void InitQueue(SqQueue &Q) {
    Q.front = 0;              // 队头指针
    Q.rear = 0;               // 队尾指针
}

// 判空：队头等于队尾
bool QueueEmpty(SqQueue Q) {
    return Q.front == Q.rear; // 两指针相等则队列为空
}

// 判满：牺牲一个空间，rear的下一个位置是front
bool QueueFull(SqQueue Q) {
    return (Q.rear + 1) % MaxSize == Q.front;
}

// 入队
bool EnQueue(SqQueue &Q, ElemType e) {
    if (QueueFull(Q))         // 队满，无法入队
        return false;
    Q.data[Q.rear] = e;       // 元素放入队尾位置
    Q.rear = (Q.rear + 1) % MaxSize; // 队尾指针循环后移
    return true;
}

// 出队
bool DeQueue(SqQueue &Q, ElemType &e) {
    if (QueueEmpty(Q))        // 队空，无法出队
        return false;
    e = Q.data[Q.front];      // 取出队头元素
    Q.front = (Q.front + 1) % MaxSize; // 队头指针循环后移
    return true;
}

// 求队列长度
int QueueLength(SqQueue Q) {
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

2.5 链队列 ​

链队列 使用单链表实现，同时设置队头指针和队尾指针。为操作统一，通常增设头节点。

c
typedef struct QNode {
    ElemType data;            // 数据域
    struct QNode *next;       // 指针域
} QNode, *QueuePtr;

typedef struct {
    QueuePtr front;           // 队头指针（指向头节点）
    QueuePtr rear;            // 队尾指针（指向队尾节点）
} LinkQueue;

// 初始化：创建头节点，front和rear都指向头节点
void InitQueue(LinkQueue &Q) {
    Q.front = Q.rear = (QNode*)malloc(sizeof(QNode)); // 创建头节点
    Q.front->next = NULL;     // 头节点的next为空
}

// 判空：front和rear都指向头节点
bool QueueEmpty(LinkQueue Q) {
    return Q.front == Q.rear; // 两指针都指向头节点则队空
}

// 入队：尾插法
void EnQueue(LinkQueue &Q, ElemType e) {
    QNode *p = (QNode*)malloc(sizeof(QNode)); // 分配新节点
    p->data = e;              // 设置数据域
    p->next = NULL;           // 新节点是新的队尾，next为空
    Q.rear->next = p;         // 原队尾节点的next指向新节点
    Q.rear = p;               // 更新队尾指针
}

// 出队：删除头节点的下一个节点
bool DeQueue(LinkQueue &Q, ElemType &e) {
    if (QueueEmpty(Q))        // 队空
        return false;
    QNode *p = Q.front->next; // p指向队头节点（头节点的下一个）
    e = p->data;              // 取出队头元素
    Q.front->next = p->next;  // 头节点的next跳过p
    if (Q.rear == p)          // 若出队的是最后一个元素
        Q.rear = Q.front;     // 队尾指针也要指向头节点（队列变空）
    free(p);                  // 释放队头节点
    return true;
}

注意：出队时需要特别判断"出队的是最后一个元素"的情况，此时需要将 rear 也指向头节点，否则 rear 会成为悬空指针。

三、记忆与理解辅助 ​

技巧1：队列核心口诀

"先进先出FIFO，队尾入队队头出；循环队列取模算，判空判满要分清"

技巧2：循环队列三种判空判满方法对比

方法队空条件队满条件空间利用率实现复杂度
牺牲一个空间front == rear(rear+1)%M == front(n−1)/n(n-1)/n低（最常考）
增设 sizesize == 0size == MaxSize100%100\%中
增设 tagfront==rear && tag==0front==rear && tag==1100%100\%中

技巧3：循环队列 vs 链队列对比表

比较项循环队列链队列
存储方式数组（连续空间）链表（离散空间）
空间大小固定容量（MaxSize）动态分配
判满需要特殊处理无需判满
判空front == rearfront == rear（都指向头节点）
入队/出队O(1)O(1)O(1)O(1)（含 malloc/free 实际略慢）
适用场景队列大小可预估队列大小不确定

技巧4：front 和 rear 的指向约定

循环队列中 front 和 rear 的含义需要特别注意：

  • front 指向队头元素的位置
  • rear 指向队尾元素的下一个位置（即下一个入队位置）
  • 这是最常见的约定，408考试中以此为准

四、例题与精解 ​

例题1（基础） ​

题目：循环队列的存储空间为 Q[0..20]（MaxSize=21），若当前 front=5，rear=10，则队列中元素个数为多少？经过连续5次出队和3次入队后，front 和 rear 的值分别是多少？

命题意图：考查循环队列长度计算和指针移动规则。

审题分析：

  • 已知：MaxSize=21，front=5，rear=10
  • 求解：队列元素个数；经过5次出队3次入队后的指针值

解题思路：

  • 队列长度公式：(rear−front+MaxSize)%MaxSize(rear - front + MaxSize) \% MaxSize
  • 出队：front = (front + 1) \% MaxSize，执行5次
  • 入队：rear = (rear + 1) \% MaxSize，执行3次

完整步骤：

  1. 队列元素个数： (10−5+21)%21=26%21=5(10 - 5 + 21) \% 21 = 26 \% 21 = 5 个元素

  2. 5次出队：

    • 第1次：front = (5+1)%21 = 6
    • 第2次：front = (6+1)%21 = 7
    • 第3次：front = (7+1)%21 = 8
    • 第4次：front = (8+1)%21 = 9
    • 第5次：front = (9+1)%21 = 10

  3. 3次入队：

    • 第1次：rear = (10+1)%21 = 11
    • 第2次：rear = (11+1)%21 = 12
    • 第3次：rear = (12+1)%21 = 13

  4. 最终结果：front = 10，rear = 13，元素个数 = (13−10+21)%21=3(13-10+21)\%21 = 3

方法反思：

  • 关键是记住循环队列指针移动用取模运算
  • 出队5次后 front 恰好等于原来的 rear（10），说明此时队列为空
  • 之后3次入队使得 rear=13，队列中现在有3个元素

例题2（中等） ​

题目：假设循环队列采用"牺牲一个存储单元"区分队空和队满，存储空间大小为 MaxSize。编写一个算法，返回循环队列中的元素个数。

命题意图：考查循环队列的结构特性和长度计算的推导能力。

审题分析：

  • 已知：循环队列采用牺牲一个空间的方式，front 指向队头元素，rear 指向队尾元素的下一个位置
  • 求解：编写函数返回队列元素个数

解题思路：

  • 考虑两种情况：rear >= front 和 rear < front（循环环绕）
  • 用取模运算统一处理

完整步骤：

c
// 返回循环队列Q中的元素个数
int QueueLength(SqQueue Q) {
    // 方法：(rear - front + MaxSize) % MaxSize
    // 当rear>=front时：rear-front 即为元素个数
    // 当rear<front时（环绕）：rear-front为负数，
    //   加MaxSize后取模得到正确值
    return (Q.rear - Q.front + MaxSize) % MaxSize;
}

验证：

  • 设 front=5, rear=10: (10−5+M)%M=5(10-5+M)\%M = 5 ✓
  • 设 front=18, rear=3 (MaxSize=21): (3−18+21)%21=6%21=6(3-18+21)\%21 = 6\%21 = 6 ✓（元素在位置18,19,0,1,2,3的"下一个"=共6个元素在18,19,0,1,2处）
  • 设 front=rear=5: (5−5+M)%M=0(5-5+M)\%M = 0 ✓（队空）

方法反思：

  • (rear - front + MaxSize) % MaxSize 是万能公式，无论 rear 和 front 谁大都能正确计算
  • + MaxSize 是为了防止 rear - front 为负数时取模出错（C语言中负数取模结果可能为负）
  • 此公式在408选择题中经常直接考查

五、考情分析 ​

分析维度内容
考查频次循环队列判空/判满条件近5年出现3次以上（选择题），队列长度计算也常考
常见题型选择题（判空判满条件辨析、指针值计算）、大题（队列相关算法设计）
分值占比选择题2分，大题可能与BFS等结合考查
命题趋势基本概念选择题保持稳定，趋势是将队列与其他知识点（如树的层序遍历、图的BFS）结合考查

注：以上频次基于大纲权重与通用命题规律推测，待真题分析后校准。

六、易错点提醒 ​

易错点1

  • 错误表现：循环队列判满时忘记取模，写成 rear+1 == front 而非 (rear+1)%MaxSize == front
  • 错误原因：忽略循环队列的"循环"特性，当 rear 在数组末尾时需要绕回开头
  • 正确做法：所有涉及 front/rear 移动的计算都必须用 % MaxSize

易错点2

  • 错误表现：链队列出队时忘记处理"最后一个元素出队"的特殊情况
  • 错误原因：出队后如果删除的是最后一个节点，rear 指针仍指向已释放的节点（悬空指针）
  • 正确做法：出队后检查 if (Q.rear == p)，若成立则将 rear 也指向头节点

易错点3

  • 错误表现：混淆"队列长度"和"队列容量"，或将牺牲的一个空间也算入元素个数
  • 错误原因：对"牺牲一个空间"的含义理解不透彻
  • 正确做法：牺牲一个空间意味着最多存储 MaxSize - 1 个元素，长度公式 (rear-front+MaxSize)%MaxSize 最大值为 MaxSize-1

易错点4

  • 错误表现：初始化时让 front = rear = 0，但后续操作中出队时不取模
  • 错误原因：对取模运算的必要性认识不足
  • 正确做法：每次 front/rear 变化后都必须取模，确保指针在 [0, MaxSize) 范围内

七、来源标注 ​

  • 依据2026考研统考大纲（408计算机学科专业基础综合）
  • 依据《数据结构（C语言版）》严蔚敏版
  • 依据《数据结构》王道考研辅导讲义

考研全科复习资料 - 基于2026考研统考大纲

仅供学习参考