郑州企业网站优化服务哪家好,做阿里网站卖东西赚钱,网站制作前景,开锁公司网站源码图均为手绘,代码基于vs2022实现 系列文章目录
数据结构初探: 顺序表 数据结构初探:链表之单链表篇 数据结构初探:链表之双向链表篇 链表特别篇:链表经典算法问题 数据结构:栈篇 文章目录 系列文章目录前言一.队列的概念和结构1.1概念一、动态内存管理优势二、操作效率与安全性… 图均为手绘,代码基于vs2022实现 系列文章目录
数据结构初探: 顺序表 数据结构初探:链表之单链表篇 数据结构初探:链表之双向链表篇 链表特别篇:链表经典算法问题 数据结构:栈篇 文章目录 系列文章目录前言一.队列的概念和结构1.1概念一、动态内存管理优势二、操作效率与安全性 1.2结构 二.准备工作1.Queue.h:2.Queue.c:3.test.c: 三.队列的数据操作的实现(增删查改)1.Queue.h:2.Queue.c:2.1队列的初始化;2.2队列的销毁2.3队列节点的创建2.4队列的插入(入队)2.5队列的删除(出队)2.6返回元素个数2.7判断队列为空2.8返回队列的队头元素,即要出队的元素2.9返回队列的队尾元素,即入队的元素2.10完整代码 3.test.c 四.队列的优缺点**队列的优点****队列的缺点****实际应用中的取舍建议** 总结 前言
在计算机科学的世界中高效管理先来后到的秩序往往能解决许多复杂问题。无论是操作系统调度任务、网络请求排队处理还是生活中常见的点餐叫号系统背后都离不开一个看似简单却至关重要的数据结构——队列Queue。
队列的核心理念如同我们日常生活中的排队规则先到者先服务First In, First Out,即FIFO。这种看似朴素的思想却在算法设计、系统架构甚至高并发场景中扮演着关键角色。它既可以是算法题中巧妙的解题工具也能成为分布式系统中缓解流量洪峰的利器。
本文将带您深入队列的运作机制从基础概念到实际应用从手写实现到性能优化我们不仅会剖析队列的「先进先出」特性还会探讨循环队列进阶形态。无论您是初探数据结构的新手还是希望温故知新的开发者相信都能通过本文重新发现队列的独特魅力。 一.队列的概念和结构
1.1概念
队列只允许在一端进行插入数据操作在另一端进行删除数据操作的特殊线性表队列具有先进先出FIFO(First In First Out) 入队列进行插入操作的一端称为队尾 (rear) 出队列进行删除操作的一端称为队头(front)
队列既可以用数组实现,也可以用链表实现,但是在一般情况下,我们会选择使用链表进行实现 但是为什么呢?
一、动态内存管理优势 按需扩容 链表节点动态分配内存队列长度无需预先声明上限。当数据规模不可预知时如网络请求队列链表可避免数组的「空间预分配浪费」或「频繁扩容」问题。 避免假溢出问题 数组实现的循环队列需要预留一个空位判断队满实际可用空间为MAX_SIZE-1而链表天然支持动态增长无此限制。但是在学习中我们使用数组实现循环队列会使得逻辑更加清晰明了,为了更好理解,我会在栈和队列特别篇:经典算法问题中为大家讲解其中的好处 二、操作效率与安全性 稳定的时间复杂度 链表的入队O(1)和出队O(1)操作无需像动态数组那样触发内存拷贝性能可预测性更强。 内存碎片化更低 频繁的数组扩容/缩容可能产生内存碎片而链表的节点分散存储能更灵活利用内存空隙。 无数据搬迁开销 数组出队时若采用「非循环」结构需移动元素链表只需修改指针指向无数据搬移成本。
1.2结构
整体图结构如图: 首先我们是以链表实现,所以我们需要节点结构体:
//队列节点的创建;
typedef struct QueueNode
{QDataType data;//存储数据struct QueueNode* next;//下一个节点地址
}QNode;队列的创建:
//队列的传参节点;队列的结构;
typedef struct Queue
{QNode* head;//队头QNode* tail;//队尾int size;//有效数据个数
}Queue;上面这种方式可以减少我们传参过多导致混乱的问题; 让我们继续来实现队列的数据操作;
二.准备工作
创建对应的三个文件夹:
1.Queue.h:
用于存储顺序表的结构和增删查改函数声明,以及对应的库函数;
2.Queue.c:
用于函数的实现;
3.test.c:
用于测试和修改; ps:2和3,均要包含头文件1,即(#includeQueue.h).
三.队列的数据操作的实现(增删查改)
1.Queue.h:
#pragma once#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.htypedef int QDataType;
//队列节点的创建;
typedef struct QueueNode
{QDataType data;struct QueueNode* next;
}QNode;
//队列的传参节点;队列的结构;
typedef struct Queue
{QNode* head;QNode* tail;int size;
}Queue;
//初始化
void QueueInit(Queue* pq);
//销毁
void QueueDestroy(Queue* pq);
//创建新节点
QNode* CreateNode(QDataType x);
//插入
void QueuePush(Queue* pq, QDataType x);
//删除
void QueuePop(Queue* pq);
//返回有效数据个数
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//返回头元素
QDataType QueueFront(Queue* pq);
//返回尾元素
QDataType QueueBack(Queue* pq);如何实现呢,我们往下看;
2.Queue.c:
2.1队列的初始化;
//还是老问题,修改结构体内部变量,一级指针即可
void QueueInit(Queue* pq)
{assert(pq);//防止传空pq-head pq-tail NULL;//全部初始化为空,即空队列pq-size 0;
}2.2队列的销毁
void QueueDestroy(Queue* pq)
{assert(pq);//从头开始QNode* cur pq-head;while (cur)//不断往下释放,直到全部销毁{QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;//恢复至初始化pq-size 0;
}2.3队列节点的创建
QNode* CreateNode(QDataType x)
{//动态开辟空间分配QNode* newNode (QNode*)malloc(sizeof(QNode));if (newNode NULL)//判断是否开辟成功{perror(malloc fail);return NULL;}newNode-data x;//存储数据newNode-next NULL;//下一个节点指向置空
//方便多次复用return newNode;//返回
}2.4队列的插入(入队)
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode CreateNode(x);if (pq-head NULL)//头尾都为空才能说明真的为空{assert(pq-tail NULL);pq-head pq-tail newNode;//头尾都指向新节点}else//其他情况{pq-tail-next newNode;//在尾节点后链接pq-tail newNode;//更新尾}pq-size;//有效数据个数,更新个数;
}2.5队列的删除(出队)
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq-head ! NULL);//这里有两种代码逻辑://一.//QNode* next pq-head-next;//free(pq-head);//pq-head next;//if (pq-head NULL)//{// pq-tail NULL;//}//二.if (pq-head-next NULL)//如果只有一个节点{free(pq-head);//直接释放并且归零pq-head pq-tail NULL;}else{//有多个节点,则记录节点下一个,释放节点QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;//更新有效数据个数
}2.6返回元素个数
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}2.7判断队列为空
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;//用size判断是否为空,要保证size不出问题;//return pq-head NULL pq-tail NULL;
}2.8返回队列的队头元素,即要出队的元素
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}2.9返回队列的队尾元素,即入队的元素
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}2.10完整代码
#define _CRT_SECURE_NO_WARNINGS 1#includeQueue.h//队列的初始化;
void QueueInit(Queue* pq)
{assert(pq);pq-head pq-tail NULL;pq-size 0;
}//队列的销毁;
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur pq-head;while (cur){QNode* next cur-next;free(cur);cur next;}pq-head pq-tail NULL;pq-size 0;
}//队列节点的创建;
QNode* CreateNode(QDataType x)
{QNode* newNode (QNode*)malloc(sizeof(QNode));if (newNode NULL){perror(malloc fail);return NULL;}newNode-data x;newNode-next NULL;return newNode;
}//队列的插入(入队);
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newNode CreateNode(x);if (pq-head NULL){assert(pq-tail NULL);pq-head pq-tail newNode;}else{pq-tail-next newNode;pq-tail newNode;}pq-size;
}//队列的删除(出队);
void QueuePop(Queue* pq)
{assert(pq);//assert(!QueueEmpty(pq));assert(pq-head ! NULL);//QNode* next pq-head-next;//free(pq-head);//pq-head next;//if (pq-head NULL)//{// pq-tail NULL;//}if (pq-head-next NULL){free(pq-head);pq-head pq-tail NULL;}else{QNode* next pq-head-next;free(pq-head);pq-head next;}pq-size--;
}//返回元素个数;
int QueueSize(Queue* pq)
{assert(pq);return pq-size;
}//判断队列为空;
bool QueueEmpty(Queue* pq)
{assert(pq);return pq-size 0;//用size判断是否为空,要保证size不出问题;//return pq-head NULL pq-tail NULL;
}//返回队列的队头元素,即要出队的元素;
QDataType QueueFront(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-head-data;
}//返回队列的队尾元素,即入队的元素;
QDataType QueueBack(Queue* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq-tail-data;
}我们现在已经学会如何对数据进行在队列中的操作了,让我们来测试一下
3.test.c
#define _CRT_SECURE_NO_WARNINGS 1#includeQueue.hint main()
{Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);QueuePush(q, 5);while (!QueueEmpty(q)){printf(%d , QueueFront(q));QueuePop(q);}printf(\n);QueueDestroy(q);return 0;
}四.队列的优缺点
队列的优点 天然的顺序公平性 FIFO原则严格遵循先进先出规则适用于需要保证公平性的场景如打印任务排队、客服呼叫系统。操作可预测所有元素的处理顺序完全透明易于调试和逻辑追踪。 高效的基础操作 时间复杂度稳定入队enqueue和出队dequeue操作均为 O(1)数组循环队列/链表实现。低资源消耗内存连续访问数组或指针操作链表均对硬件友好。 缓冲与解耦能力 流量削峰应对突发请求时作为缓冲区避免系统过载如消息队列Kafka。生产者-消费者解耦平衡不同模块的处理速度差异如多线程任务分发。 灵活的扩展性 多形态实现可通过不同底层结构数组、链表或变形循环队列、优先队列适配需求。支持泛型数据可存储任意数据类型如C语言中的void*指针。 队列的缺点 访问限制 无法随机访问只能操作队头/队尾元素查找中间元素需遍历队列时间复杂度 O(n)。修改成本高若需调整元素顺序如插队必须重建队列或使用其他数据结构。 实现依赖的局限性 实现方式缺点静态数组固定容量导致空间浪费或溢出风险动态链表内存碎片化、节点分配开销循环队列需预留空位判断队满可用空间为n-1 并发场景挑战 线程安全问题多线程同时操作需加锁互斥锁/信号量增加复杂度。性能权衡锁机制可能导致吞吐量下降可通过无锁队列优化但实现难度高。 内存管理成本 动态扩展开销链表实现的频繁内存分配/释放可能引发性能抖动。缓存不友好链表节点非连续存储降低CPU缓存命中率数组更优。 实际应用中的取舍建议 优先队列的替代方案 当需要按优先级处理元素时标准队列无法满足需求需改用堆Heap或优先队列。 资源受限场景的优化 嵌入式系统中静态数组循环队列可避免动态内存分配的开销。 高并发场景的增强 使用无锁队列如环形缓冲区原子操作或任务分片提升吞吐量。 总结
队列如同数字世界中的秩序守护者用最朴素的「先进先出」法则在混乱中建立规则。从算法面试中巧解BFS问题到分布式系统中承载百万级消息的洪流这种数据结构以简洁的哲学应对着复杂的挑战。它教会我们高效的系统往往不是消灭等待而是优雅地管理等待。
通过数组与链表的实现对比我们看到了数据结构设计的权衡艺术——静态实现追求极致的性能可控动态实现拥抱灵活的资源适配。无论是循环队列的精妙取模还是链式节点的精准跳转最终都服务于同一个目标在正确的时间以正确的方式处理正确的请求。
当你再次面对需要顺序公平性的场景时不妨让队列成为你的隐形协作者。而在未来的探索中可以继续深入
横向扩展双端队列Deque如何突破FIFO限制纵向深入优先队列Priority Queue怎样用堆重塑出队规则工程实践Kafka/RabbitMQ等消息队列如何解决分布式一致性难题
队列的魅力恰在于它既是入门数据结构的基石又是构建复杂系统的核心齿轮。正如交响乐团的指挥掌控节奏学会驾驭队列的开发者终将在秩序的韵律中写出优雅的技术乐章。