2.队列：先进先出的线性数据结构

一、什么是队列？

队列（Queue）是一种 ** 先进先出（FIFO, First In First Out）** 的线性数据结构，它只允许在一端进行插入操作（队尾），在另一端进行删除操作（队头）。

简单来说，队列就像一个 “两端开口的管道”：

• 最先进入队列的元素，会最先被取出；
• 最后进入队列的元素，会最后被取出。

二、队列的核心结构

队列的本质是一段连续内存 + 两个指针：

• 连续内存：用于存储队列中的元素，通常用数组实现；
• 队头指针（front）：指向队列的第一个元素；
• 队尾指针（rear）：指向队列的最后一个元素的下一个位置。

对应的 C 语言代码定义如下：

#define MAX_SIZE 100 // 队列的最大容量 // 队列的结构体定义 typedef struct { int data[MAX_SIZE]; // 连续内存，存储队列元素 int front; // 队头指针 int rear; // 队尾指针 } Queue;

三、队列的基本操作

队列的核心操作有两个：入队（Enqueue）和出队（Dequeue），这两个操作的时间复杂度都是O(1)（常数时间），因为它们不需要遍历整个队列，只需要操作队头和队尾指针。

1. 入队（Enqueue）：队尾添加元素

入队操作是将元素添加到队尾，步骤如下：

1. 判满：如果队尾指针等于MAX_SIZE，说明队列已满，无法再添加元素；
2. 先写入，再自增：将元素写入到队尾指针指向的位置，然后将队尾指针加 1。

代码实现：

// 入队操作 int enqueue(Queue *q, int value) { // 判满：队尾指针到达最大容量 if (q->rear == MAX_SIZE) { printf("队列已满，无法入队！\n"); return -1; } // 先写入元素，再自增队尾指针 q->data[q->rear++] = value; return 0; }

2. 出队（Dequeue）：队头取出元素

出队操作是将队头元素取出，步骤如下：

1. 判空：如果队头指针等于队尾指针，说明队列为空，无法再取出元素；
2. 先读取，再自增：先读取队头元素，然后将队头指针加 1。

代码实现：

// 出队操作 int dequeue(Queue *q) { // 判空：队头指针等于队尾指针表示空队列 if (q->front == q->rear) { printf("队列为空，无法出队！\n"); return -1; } // 先读取队头元素，再自增队头指针 return q->data[q->front++]; }

四、队列的初始化

在使用队列之前，需要先初始化队列，将队头指针和队尾指针都设置为0，表示队列为空。

代码实现：

// 初始化队列 void initQueue(Queue *q) { q->front = 0; // 队头指针归位到0 q->rear = 0; // 队尾指针归位到0 }

五、队列的问题：假溢出

普通队列存在一个明显的问题：假溢出。

当队尾指针到达MAX_SIZE时，即使队头前面还有空位，也无法再入队新的元素，因为队尾指针已经无法继续自增。

例如：

• 队列容量为 5，元素入队后，rear指针到达 5；
• 出队后，front指针移动到 2，此时队头前面还有 2 个空位；
• 但rear指针已经到达 5，无法再入队新的元素，这就是假溢出。

六、解决方案：循环队列（Ring Buffer）

为了解决假溢出问题，我们可以使用循环队列，通过取模运算让队尾指针绕回队列头部，重复使用队头前面的空位。

1. 循环队列的核心逻辑

• 队尾指针绕回：rear = (rear + 1) % MAX_SIZE；
• 判满条件：(rear + 1) % MAX_SIZE == front；
• 判空条件：front == rear（和普通队列一致）。

2. 循环队列的代码实现

// 循环队列入队操作 int enqueueRing(Queue *q, int value) { // 判满：(rear + 1) % MAX_SIZE == front if ((q->rear + 1) % MAX_SIZE == q->front) { printf("循环队列已满，无法入队！\n"); return -1; } // 先写入元素，再绕回队尾指针 q->data[q->rear] = value; q->rear = (q->rear + 1) % MAX_SIZE; return 0; } // 循环队列出队操作 int dequeueRing(Queue *q) { // 判空：front == rear if (q->front == q->rear) { printf("循环队列为空，无法出队！\n"); return -1; } // 先读取队头元素，再绕回队头指针 int value = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; return value; }

七、队列的扩展操作

除了基本的入队和出队，队列还可以实现以下扩展操作：

1. 查看队头元素（Peek）

不弹出队头元素，只读取队头的值：

// 查看队头元素 int peek(Queue *q) { if (q->front == q->rear) { printf("队列为空，无队头元素！\n"); return -1; } return q->data[q->front]; }

2. 判断队列是否为空

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

3. 判断队列是否已满

// 判断队列是否已满（普通队列） int isFull(Queue *q) { return q->rear == MAX_SIZE; } // 判断循环队列是否已满 int isFullRing(Queue *q) { return (q->rear + 1) % MAX_SIZE == q->front; }

4. 清空队列

将队头指针和队尾指针都重置为0，表示队列为空：

// 清空队列 void clearQueue(Queue *q) { q->front = 0; q->rear = 0; }

八、完整代码示例

#include <stdio.h> #define MAX_SIZE 5 // 队列容量设置为5，方便测试假溢出 // 队列的结构体定义 typedef struct { int data[MAX_SIZE]; int front; int rear; } Queue; // 初始化队列 void initQueue(Queue *q) { q->front = 0; q->rear = 0; } // 普通队列入队 int enqueue(Queue *q, int value) { if (q->rear == MAX_SIZE) { printf("普通队列已满，无法入队！\n"); return -1; } q->data[q->rear++] = value; return 0; } // 普通队列出队 int dequeue(Queue *q) { if (q->front == q->rear) { printf("普通队列为空，无法出队！\n"); return -1; } return q->data[q->front++]; } // 循环队列入队 int enqueueRing(Queue *q, int value) { if ((q->rear + 1) % MAX_SIZE == q->front) { printf("循环队列已满，无法入队！\n"); return -1; } q->data[q->rear] = value; q->rear = (q->rear + 1) % MAX_SIZE; return 0; } // 循环队列出队 int dequeueRing(Queue *q) { if (q->front == q->rear) { printf("循环队列为空，无法出队！\n"); return -1; } int value = q->data[q->front]; q->front = (q->front + 1) % MAX_SIZE; return value; } // 查看队头元素 int peek(Queue *q) { if (q->front == q->rear) { printf("队列为空，无队头元素！\n"); return -1; } return q->data[q->front]; } int main() { Queue q; initQueue(&q); // 测试普通队列的假溢出 printf("=== 测试普通队列 ===\n"); enqueue(&q, 10); enqueue(&q, 20); enqueue(&q, 30); enqueue(&q, 40); enqueue(&q, 50); enqueue(&q, 60); // 普通队列已满，无法入队 printf("出队元素：%d\n", dequeue(&q)); // 输出10 printf("出队元素：%d\n", dequeue(&q)); // 输出20 printf("队头元素：%d\n", peek(&q)); // 输出30 printf("队头指针：%d，队尾指针：%d\n", q.front, q.rear); // 输出2,5 // 测试循环队列 printf("\n=== 测试循环队列 ===\n"); initQueue(&q); // 重新初始化队列 enqueueRing(&q, 10); enqueueRing(&q, 20); enqueueRing(&q, 30); enqueueRing(&q, 40); enqueueRing(&q, 50); // 循环队列已满，无法入队 printf("出队元素：%d\n", dequeueRing(&q)); // 输出10 printf("出队元素：%d\n", dequeueRing(&q)); // 输出20 enqueueRing(&q, 60); // 循环队列可以入队，因为队头前面有空位 enqueueRing(&q, 70); // 循环队列可以入队 printf("出队元素：%d\n", dequeueRing(&q)); // 输出30 printf("出队元素：%d\n", dequeueRing(&q)); // 输出40 printf("出队元素：%d\n", dequeueRing(&q)); // 输出50 printf("出队元素：%d\n", dequeueRing(&q)); // 输出60 printf("出队元素：%d\n", dequeueRing(&q)); // 输出70 printf("队列为空：%s\n", (q.front == q.rear) ? "是" : "否"); // 输出是 return 0; }

九、队列的实际应用场景

队列在实际开发中应用非常广泛，常见场景包括：

1. 任务队列：如线程池的任务调度，先提交的任务先执行；
2. 消息队列：如 RabbitMQ、Kafka，实现异步通信和削峰填谷；
3. 广度优先搜索（BFS）：遍历图或树时的临时存储；
4. 缓冲区：如键盘缓冲区、网络缓冲区，先输入的内容先处理；
5. 操作系统调度：如进程调度、作业调度，先到达的进程先执行。
6. 限流系统：通过队列控制请求速率，避免系统过载；
7. 日志系统：使用队列异步存储日志，提高系统性能。

十、队列的扩展类型

除了普通队列和循环队列，队列还有以下扩展类型：

1. 双端队列（Deque）：允许在队头和队尾同时进行插入和删除操作；
2. 优先队列（Priority Queue）：元素按照优先级排序，优先级高的先出队；
3. 阻塞队列（Blocking Queue）：当队列满时，入队操作会阻塞；当队列空时，出队操作会阻塞；
4. 并发队列（Concurrent Queue）：支持多线程安全的队列操作。

十一、总结

队列是一种非常基础且重要的数据结构，它的核心特点是先进先出，通过连续内存 + 队头队尾指针实现，基本操作的时间复杂度为O(1)。

普通队列存在假溢出问题，通过循环队列可以解决，循环队列通过取模运算让队尾指针绕回队列头部，重复使用队头前面的空位。

在实际应用中，队列的使用场景非常广泛，是算法和开发中不可或缺的基础工具。

希望这篇文章能帮助你深入理解队列的原理和实现！