掌握队列的先进先出特性、顺序队列的假溢出、循环队列的判空判满，以及链式队列的入队和出队实现。

# 一、队列的定义与基本操作

队列（Queue）是只允许在一端插入、在另一端删除的线性表。插入的一端称为队尾，删除的一端称为队头。入队和出队遵循先进先出（FIFO, First In First Out）原则。

若元素按 $a,b,c$ 的次序依次入队，且期间不出队，则出队次序为 $a,b,c$ 。

操作	含义
InitQueue	初始化空队列
QueueEmpty	判断队列是否为空
EnQueue(Q, x)	将 $x$ 插入队尾
DeQueue(Q, x)	删除队头并用 $x$ 返回其值
GetHead(Q, x)	读取队头但不删除
DestroyQueue	释放队列资源

只要维护了队头和队尾位置，入队、出队和读队头都应为 $O(1)$ 。

# 二、顺序队列与假溢出

顺序队列可用数组保存元素，并用 front 和 rear 记录队头、队尾。若出队后不移动剩余元素，rear 会不断向数组末端移动；即使数组前部已有空单元，rear 到达末端时仍无法入队，这称为假溢出。

假溢出不是内存真的装满，而是线性数组的未使用前部空间不能复用。简单地让每次出队都搬移后继元素能解决空间问题，但出队将变成 $O(n)$ ，破坏队列操作的常数时间目标。

# 三、循环队列

循环队列把长度为 MAX_SIZE 的数组视作首尾相连的环，指针按模 MAX_SIZE 回绕。以下采用 “front 指向队头元素，rear 指向下一个可插入位置，并牺牲一个单元” 的约定：

$\begin{aligned} &\text{队空：}\quad front=rear,\\ &\text{队满：}\quad (rear+1)\bmod MAX\_SIZE=front,\\ &\text{队长：}\quad (rear-front+MAX\_SIZE)\bmod MAX\_SIZE. \end{aligned}$

因此容量为 MAX_SIZE 的数组最多保存 MAX_SIZE - 1 个元素。

1
2
3

flowchart LR
    F[front：队头元素] --> A[a] --> B[b] --> C[c] --> R[rear：下一可写位置]
    R -.取模回绕.-> F

#include <stdbool.h>

#define MAX_SIZE 100
typedef int ElemType;

typedef struct {
    ElemType data[MAX_SIZE];
    int front;
    int rear;
} SqQueue;

void InitQueue(SqQueue *Q) {
    Q->front = Q->rear = 0;
}

bool QueueEmpty(const SqQueue *Q) {
    return Q->front == Q->rear;
}

bool QueueFull(const SqQueue *Q) {
    return (Q->rear + 1) % MAX_SIZE == Q->front;
}

int QueueLength(const SqQueue *Q) {
    return (Q->rear - Q->front + MAX_SIZE) % MAX_SIZE;
}

入队在 rear 所指单元写入，再移动 rear；出队读取 front 所指单元，再移动 front。

bool EnQueue(SqQueue *Q, ElemType x) {
    if (QueueFull(Q)) {
        return false;
    }

    Q->data[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAX_SIZE;
    return true;
}

bool DeQueue(SqQueue *Q, ElemType *x) {
    if (QueueEmpty(Q)) {
        return false;
    }

    *x = Q->data[Q->front];
    Q->front = (Q->front + 1) % MAX_SIZE;
    return true;
}

bool GetHead(const SqQueue *Q, ElemType *x) {
    if (QueueEmpty(Q)) {
        return false;
    }
    *x = Q->data[Q->front];
    return true;
}

循环队列并不一定非要 “牺牲一个单元”。也可以额外维护 size，或设置 tag 记录最后一次操作；此时队满和队空的判定不同。答题必须以题目给出的 front、rear 含义和辅助变量为准。

# 四、链式队列

链式队列通常使用带头结点的单链表，front 指向头结点，rear 指向最后一个有效结点。空队列满足 front == rear，真实队头元素是 front->next。

#include <stdbool.h>
#include <stdlib.h>

typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode;

typedef struct {
    QNode *front;
    QNode *rear;
} LinkQueue;

bool InitLinkQueue(LinkQueue *Q) {
    QNode *head = malloc(sizeof(QNode));
    if (head == NULL) {
        return false;
    }

    head->next = NULL;
    Q->front = Q->rear = head;
    return true;
}

入队只需把新结点链接到 rear 后面并更新 rear：

bool LinkEnQueue(LinkQueue *Q, ElemType x) {
    QNode *node = malloc(sizeof(QNode));
    if (node == NULL) {
        return false;
    }

    node->data = x;
    node->next = NULL;
    Q->rear->next = node;
    Q->rear = node;
    return true;
}

出队删除 head 后的第一个有效结点。若删除的是唯一结点，必须令 rear 回到头结点：

bool LinkDeQueue(LinkQueue *Q, ElemType *x) {
    if (Q->front == Q->rear) {
        return false;
    }

    QNode *node = Q->front->next;
    *x = node->data;
    Q->front->next = node->next;
    if (Q->rear == node) {
        Q->rear = Q->front;
    }
    free(node);
    return true;
}

这两个指针均已维护时，链式队列入队、出队均为 $O(1)$ 。若不维护 rear，入队需要遍历链表到末尾，会退化为 $O(n)$ 。

# 五、双端队列

双端队列（Deque）允许在两端插入和删除，可同时支持队头、队尾的进出操作。它不是普通 FIFO 队列的等价替换：普通队列只允许队尾入、队头出；双端队列的操作集合更大。循环数组或双向链表都可实现双端队列。

例题 3.2：循环队列的容量

循环队列数组长度为 8，采用牺牲一个单元的约定。队列最多能容纳多少元素？若 front == 6、rear == 2，队列中有多少元素？

【解】 最多容纳 $8-1=7$ 个元素。当前长度为

$(2-6+8)\bmod8=4.$

这里的数组下标依次经过 $6,7,0,1$ ，正体现了循环回绕。

# 六、考场检查清单

队列是 FIFO：队尾入、队头出。
顺序队列的假溢出源于 rear 单向移动，循环队列用取模回绕解决。
牺牲一个单元时，队满是 (rear + 1) % MAX_SIZE == front，最大容量少 1。
链式队列删除最后一个结点后，rear 必须回指 front。
front、rear 指向队头元素、队尾元素还是下一可写位置，会直接改变所有判定式。

# 一、队列的定义与基本操作

# 二、顺序队列与假溢出

# 三、循环队列

# 四、链式队列

# 五、双端队列

# 六、考场检查清单

第1章 绪论

2-1 线性表的定义和基本操作

第1章绪论