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队尾添加元素入队操作是将元素添加到队尾步骤如下判满如果队尾指针等于MAX_SIZE说明队列已满无法再添加元素先写入再自增将元素写入到队尾指针指向的位置然后将队尾指针加 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。代码实现// 出队操作 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; }九、队列的实际应用场景队列在实际开发中应用非常广泛常见场景包括任务队列如线程池的任务调度先提交的任务先执行消息队列如 RabbitMQ、Kafka实现异步通信和削峰填谷广度优先搜索BFS遍历图或树时的临时存储缓冲区如键盘缓冲区、网络缓冲区先输入的内容先处理操作系统调度如进程调度、作业调度先到达的进程先执行。限流系统通过队列控制请求速率避免系统过载日志系统使用队列异步存储日志提高系统性能。十、队列的扩展类型除了普通队列和循环队列队列还有以下扩展类型双端队列Deque允许在队头和队尾同时进行插入和删除操作优先队列Priority Queue元素按照优先级排序优先级高的先出队阻塞队列Blocking Queue当队列满时入队操作会阻塞当队列空时出队操作会阻塞并发队列Concurrent Queue支持多线程安全的队列操作。十一、总结队列是一种非常基础且重要的数据结构它的核心特点是先进先出通过连续内存 队头队尾指针实现基本操作的时间复杂度为O(1)。普通队列存在假溢出问题通过循环队列可以解决循环队列通过取模运算让队尾指针绕回队列头部重复使用队头前面的空位。在实际应用中队列的使用场景非常广泛是算法和开发中不可或缺的基础工具。希望这篇文章能帮助你深入理解队列的原理和实现