队列

真题练习

直接考察不是很多，偶尔在选择题考察相关概念，另外要留意 循环队列 往年在解答题中考察过。

定义与基本操作

队列是一种遵循 先入先出 (FIFO, First In First Out) 原则的线性数据结构。元素在队尾添加，在队首删除。

基本操作

enqueue(element): 将元素添加到队列的尾部。
dequeue(): 从队列的头部移除并返回元素。如果队列为空，此操作可能会返回特定的值或引发错误。
front() 或 peek(): 返回队首的元素但不移除它。
isEmpty(): 判断队列是否为空。
size(): 返回队列中元素的数量。

存储实现

顺序队列

顺序队列通常是指使用固定大小的数组来存储队列中的元素。在顺序队列中，通常有两个指标：一个是队头（front），另一个是队尾（rear）。当插入（入队）或删除（出队）元素时，这两个指标会移动。

顺序队列有一个明显的问题：随着时间的推移，队列中的元素可能向数组的末尾移动，即使队列并不满，也可能无法再插入新的元素，因为队尾已经达到了数组的末尾。这种现象称为 假溢出。

循环队列

为了解决上述问题，可以使用 循环队列（也称为环形队列）。循环队列 是顺序队列的一个变种，它把数组视为一个循环的结构。当队尾指标达到数组的最后一个位置并且还需要进一步移动时，它会回到数组的起始位置。

需要注意的是，在 循环队列 中需要牺牲一个存储单元以区分队空和队满的情况。

当 front == rear 时，队列为空；
当 (rear + 1) % MAX_SIZE == front 时，队列为满；
当前元素个数为 $(rear-front+MAX_SIZE)\bmod MAX_SIZE$ ，可用容量为 MAX_SIZE - 1。
定义
入队
出队
首尾元素
判断队列空或满

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front, rear;
} CircularQueue;

// 初始化队列
void initQueue(CircularQueue* q) {
    q->front = q->rear = 0;
}

// 入队操作
bool enqueue(CircularQueue* q, int value) {
    if (isFull(q)) return false;
    q->data[q->rear] = value;
    q->rear = (q->rear + 1) % MAX_SIZE;
    return true;
}

// 出队操作
bool dequeue(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE;
    return true;
}

// 获取队首元素
bool front(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[q->front];
    return true;
}

// 获取队尾元素
bool rear(CircularQueue* q, int* value) {
    if (isEmpty(q)) return false;
    *value = q->data[(q->rear - 1 + MAX_SIZE) % MAX_SIZE];
    return true;
}

// 判断队列是否为空
bool isEmpty(CircularQueue* q) {
    return q->front == q->rear;
}

// 判断队列是否满
bool isFull(CircularQueue* q) {
    return (q->rear + 1) % MAX_SIZE == q->front;
}

循环队列的指针语义

本页的约定是 front 指向当前队头元素的位置，rear 指向下一个可写入的位置。因此入队时先写 data[rear] 再移动 rear，出队时先读 data[front] 再移动 front；两者都使用模运算，物理下标回绕并不改变逻辑上的先进先出次序。

保留一个空单元并不是唯一实现方案，也可额外维护元素个数来区分队空和队满；但二者不能混用。做题时若题设给出 front、rear 的初值或问队列长度，应先写明它们各自指向“有效元素”还是“下一可用位置”，再套用相应公式。链式队列出队后若删掉最后一个有效结点，必须把 rear 同步重置到头结点，否则后续入队会连接到已释放结点。

链式队列

链式队列 是使用 链表结构 来实现的队列。它充分利用了链表的动态性质，允许队列在运行时 动态增长或缩小，不存在顺序存储中需要预先分配空间的问题。

链式队列通常包含三个指针：

头结点（head）
- 始终存在，不存放有效数据，只是一个哨兵结点。
- 主要作用：简化出队操作（避免删除第一个结点时单独处理）。
队头指针（front）
- 固定指向头结点。
- 注意：front 不直接指向第一个有效结点，而是 指向头结点。
- 因此，真正的队头元素在 front->next。
队尾指针（rear）
- 始终指向最后一个有效结点。
- 如果队列为空，rear == front == head。

链式队列一般使用 单链表 来实现，入队和出队操作可以基于队头和队尾指针实现：

入队（enqueue）：在队尾插入新元素。由于维护了 尾指针，因此只需 O(1) 时间。
出队（dequeue）：在队头删除元素。由于维护了 头指针，因此只需 O(1) 时间。

循环队列的入队、出队同样可以做到 $O(1)$ ，且无需移动元素；链式队列的主要优势是不受固定数组容量限制，代价是每个结点需要额外的指针空间。

定义
入队
出队
判空

// 结点定义
typedef struct QNode {
    int data;               // 数据域
    struct QNode *next;     // 指针域
} QNode;

// 链式队列结构
typedef struct {
    QNode *front;   // 队头指针 (指向头结点)
    QNode *rear;    // 队尾指针 (指向队尾结点)
} LinkQueue;

// 初始化队列（带头结点）
void InitQueue(LinkQueue *Q) {
    QNode *head = (QNode *)malloc(sizeof(QNode));  // 申请头结点
    head->next = NULL;
    Q->front = Q->rear = head;  // front、rear 都指向头结点
}

// 入队操作
void EnQueue(LinkQueue *Q, int x) {
    QNode *node = (QNode *)malloc(sizeof(QNode));
    node->data = x;
    node->next = NULL;

    Q->rear->next = node;   // 新结点挂在队尾
    Q->rear = node;         // 更新队尾指针
}

// 出队操作
int DeQueue(LinkQueue *Q, int *x) {
    if (IsEmpty(*Q)) return 0;  // 队空

    QNode *p = Q->front->next;  // 队头第一个有效结点
    *x = p->data;
    Q->front->next = p->next;   // 删除结点

    if (Q->rear == p) {         // 如果队尾被删空了
        Q->rear = Q->front;     // rear 重新指向头结点
    }
    free(p);
    return 1;
}

// 判断队列是否为空
int IsEmpty(LinkQueue Q) {
    return Q.front == Q.rear;
}

队列长度、假溢出与边界操作

在本页“队头指向当前首元素、队尾指向下一个可写位置”的循环队列约定下，长度为

\operatorname{length}=(rear-front+\operatorname{MAX_SIZE})\bmod\operatorname{MAX_SIZE}.

这个公式的结果范围是 $0$ 到 $\operatorname{MAX_SIZE}-1$ ，正好对应保留一个空单元的实现。若改为额外维护元素个数 $count$ ，那么可把全部 $\operatorname{MAX_SIZE}$ 个单元都用于存放数据，队空由 $count=0$ 判断、队满由 $count=\operatorname{MAX_SIZE}$ 判断；此时不能再把 $front=rear$ 同时解释成两种状态。

普通顺序队列的假溢出来自数组下标只向右移动，而不是内存真的放满。把未用的前部单元整体搬移到开头可以暂时解决，但一次搬移要 $O(n)$ 时间，频繁出入队会产生大量无谓移动；循环队列用取模复用这些位置，入队和出队均保持 $O(1)$ 。

链式队列的空队列是最容易漏掉的边界：带头结点实现中，删除最后一个有效结点后，队尾指针必须回到头结点；否则下一次入队会接到已释放结点之后。若是不带头结点的实现，出队删掉最后一个结点时则要把队头、队尾都置为空。两种实现的判空条件不同，先确认指针指向的是哨兵还是有效结点再写代码。