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

发布时间:2026/11/23 1:46:18

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)。普通队列存在假溢出问题通过循环队列可以解决循环队列通过取模运算让队尾指针绕回队列头部重复使用队头前面的空位。在实际应用中队列的使用场景非常广泛是算法和开发中不可或缺的基础工具。希望这篇文章能帮助你深入理解队列的原理和实现
延伸阅读

更多相关文章

2026/11/23 1:46:18

Spring AI与MCP集成:三层架构设计实践与避坑指南

1. 项目概述:从“大仓库”到“三层架构”的MCP实践起点最近在折腾MCP(Model Context Protocol)和Spring AI,第一天我没急着去写那个Tool注解,而是先在一个大的单体代码仓库里,划出了清晰的三层边界。这听起…

2026/11/21 21:14:23

.NET Core微服务架构下JWT认证的实战设计与安全实践

1. 项目概述:一个现代化微服务架构的认证安全实践最近在重构一个基于 .NET Core 的微服务项目,项目代号“NetCoreKevin-DDD”。这个项目集成了领域驱动设计(DDD)、WebApi、AI智能体、MCP协议服务、SignalR实时通信以及Quartz定时任…

2026/11/23 1:43:03

红河蒙自高压电工证怎么考?良心建议告诉你实操关键点

红河蒙自高压电工证怎么考?良心建议告诉你实操关键点 你是不是正在为找不到工作发愁?特种作业证就是你进入一些高薪行业的敲门砖,尤其是像 红河蒙自高压电工证 这样的证书,直接决定了你能不能从事相关岗位。别再等了,现在就行动起来,掌握这…

2026/11/23 1:43:03

潮州a2电工证怎么考?外省证书能否转过来?官方报名入口全解析

潮州a2电工证怎么考?外省证书能否转过来?官方报名入口全解析 之前考的证在外省能不能转过来?这是很多电工朋友在报名潮州a2电工证前都会问的问题。如果你也有类似的疑问,那这篇内容正好为你详细解答,包括报名流程、证书转移、备考技巧以及…

2026/11/23 1:43:03

宣化低压电工证怎么考才不挂科 电子证书怎么领

宣化低压电工证怎么考才不挂科 电子证书怎么领 实操考试心里没底怕挂科?考低压电工证的时候,很多人都有这样的担忧。尤其是新手,面对各种设备和操作流程,不知道从哪里下手,更怕一不小心操作不当就被判定不合格。其实,只要你掌握了正确的方法,拿到…

2026/11/23 1:43:02

弱电工是否需要电工证在哪考?别再被中介忽悠了

弱电工是否需要电工证在哪考?别再被中介忽悠了 你是不是也在纠结, 弱电工是否需要电工证 ?又在四处打听“ 在哪考 ”?别急,这篇文章就帮你理清楚,不仅告诉你为什么必须考证,还会教你怎么避开那些坑人的中介,找到靠谱的报考渠道。…

2026/11/22 0:09:40

高压电工证还能年审吗良心建议来了,学历不高也能考!

高压电工证还能年审吗良心建议来了,学历不高也能考! 你是不是也担心,自己学历不高,根本报不上高压电工证?其实不然,现在政策已经非常明确, 高压电工证还能年审 ,而且只要符合条件, 学历不是门槛 , 良心建议…

2026/11/22 0:09:40

吴江的电工证免费培训怎么报名?官方报名入口全解析

吴江的电工证免费培训怎么报名?官方报名入口全解析 你急需特种作业证才能上岗找工作,但不知道从哪里下手?别急,现在就给你讲明白【吴江的电工证免费培训】到底怎么操作,以及怎么通过 官方报名入口…

2026/11/23 0:26:19

电工证复审肃州区的真实经历:别被中介坑了,自己搞定更靠谱

电工证复审肃州区的真实经历:别被中介坑了,自己搞定更靠谱 不知道去哪报名怕被中介坑?这几乎是每个需要办理或复审电工证的人的真实经历。尤其在肃州区,信息不透明、流程复杂、中介收费高又不靠谱,让很多电工从业者感到头疼。作为一个在应急管理和特种作…

2026/11/23 0:01:38

南宁哪里可以学电工证值不值得考?怕被中介坑?看这篇就够了

南宁哪里可以学电工证值不值得考?怕被中介坑?看这篇就够了 不知道去哪报名怕被中介坑?南宁哪里可以学电工证值不值得考?这是很多想考电工证的朋友最关心的问题。现实中,不少人在选择培训机构时被各种五花八门的广告信息搞得晕头转向,甚至被坑了钱还没拿…

2026/11/23 0:01:38

建设局特种工证怎么查全国通用的复审流程

建设局特种工证怎么查全国通用的复审流程 证书过期了不知道怎么复审延期,这是很多特种作业从业者常遇到的问题。尤其是在洛阳涧西区从事水利工程工作的你,特种作业操作证不仅是上岗的“通行证”,更是保障安全作业的法律底线。如果操作证过期了,不仅影响工…

2026/11/23 0:01:38

电工证跨考政策值不值得考?学历不高也能考的真相

电工证跨考政策值不值得考?学历不高也能考的真相 你是不是也觉得学历不够,报电工证怕被拒?别急,国家安全生产考试网明文规定, 电工证跨考政策 对学历门槛没有硬性限制,只要你年满18岁,身体健康,能通过实操考试,就能报考。关键是, 值不值得考…

2026/11/22 9:39:14

面向复杂光照与角度的宠物面部识别鲁棒性增强策略

在智慧养宠时代,基于视觉的宠物身份识别技术正逐步从实验室走向家庭应用。然而,与配合度高的人类不同,宠物是典型的“非合作生物识别对象”——它们不会主动配合摄像头调整姿态,更无法控制光照环境。实际应用中,我们常…

2026/11/22 5:39:03

SSM电子书店源码全解析:结构、原理、部署与排错实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

还想了解更多?直接咨询顾问

免费诊断 + 免费方案 + 透明报价。

全国咨询热线400-8866-253
免费获取方案
☎咨询二维码 ☎ ↑