数据结构其实很简单(四): 队列——顺序队列、环形队列与链式队列

文章摘要队列是另一种操作受限的线性表只允许在队尾插入、队头删除核心是先进先出FIFOFirst In First Out。本文用 C 语言逐一拆解队列的几种实现顺序队列、环形队列、链式队列重点讲解顺序队列的假溢出问题及环形队列的取模解法并对比环形队列与链式队列的选型帮助嵌入式开发者理解消息队列、串口缓冲、任务调度背后的原理。文章目录文章摘要本栏系列文章其他专栏精品文章前言一、队列的定义二、队列的基本操作三、顺序队列数组实现四、环形队列Circular Queue五、链式队列1. 数据结构定义2. 基本操作实现六、环形队列与链式队列的对比七、队列在嵌入式中的应用八、总结本栏系列文章学透CANFD看这个就行(四): 错误帧、位填充、采样点与通信负荷其他专栏精品文章CSDN高赞项目工程训练竞赛之垃圾分类垃圾桶前言上一篇我们讲了栈后进先出这一篇进入它的镜像结构——队列先进先出。栈是后进先出队列正好反过来。队列在嵌入式里几乎无处不在串口接收缓冲、消息队列、RTOS 就绪队列全都是它。本文用 C 语言把队列的几种实现逐一拆开。一、队列的定义队列是一种操作受限的线性表只允许在一端进行插入操作队尾在另一端进行删除操作队头。这种特性称为先进先出FIFOFirst In First Out。打个比方就像排队买票先来的人排在前面先买到票离开后来的人排在后面后买到票。这就是队列的典型行为。二、队列的基本操作操作说明类比Enqueue入队在队尾添加一个元素新来的人站到队伍最后面Dequeue出队从队头取出一个元素排在最前面的人买完票离开辅助操作is_empty()判断队列是否为空is_full()判断队列是否已满三、顺序队列数组实现用数组实现队列需要两个指针head 指向队头tail 指向队尾。#defineMAX_SIZE512structpoint{introw,col,predecessor;}queue[MAX_SIZE];inthead0,tail0;voidenqueue(structpointp){queue[tail]p;tail;}structpointdequeue(void){head;returnqueue[head-1];}intis_empty(void){returnheadtail;}问题顺序队列有个严重缺陷——head 和 tail 指针一直在增大出队元素占用的空间不能重复利用导致**“假溢出”**。四、环形队列Circular Queue为了解决空间浪费问题把数组想象成一个首尾相接的圆环。环形队列的关键是取模运算// 入队voidenqueue(structpointp){if((tail1)%MAX_SIZEhead)return;// 队列已满queue[tail]p;tail(tail1)%MAX_SIZE;}// 出队structpointdequeue(void){if(headtail)returnerror;// 队列为空structpointpqueue[head];head(head1)%MAX_SIZE;returnp;}通过(tail 1) % MAX_SIZE和(head 1) % MAX_SIZE指针到达数组末尾后会自动绕回开头数组就转起来了。五、链式队列链式队列就是用链表实现的队列队头在链表头部队尾在链表尾部。入队Enqueue在队尾插入出队Dequeue在队头删除。链式队列的结构示意图front rear ↓ ↓ ┌───────┬──────┐ ┌───────┬──────┐ ┌───────┬──────┐ │ data │ next │──→│ data │ next │──→│ data │ next │──→ NULL └───────┴──────┘ └───────┴──────┘ └───────┴──────┘ (队头) (队尾)1. 数据结构定义// 队列节点结构体typedefstructQNode{intdata;// 数据域structQNode*next;// 指针域指向下一个节点}QNode;// 链式队列结构体typedefstruct{QNode*front;// 队头指针QNode*rear;// 队尾指针intcount;// 队列中元素个数}LinkQueue;2. 基本操作实现// 初始化voidInitQueue(LinkQueue*Q){Q-frontNULL;Q-rearNULL;Q-count0;}// 入队voidEnQueue(LinkQueue*Q,inte){QNode*node(QNode*)malloc(sizeof(QNode));node-datae;node-nextNULL;if(Q-rearNULL){// 队列为空Q-frontnode;Q-rearnode;}else{Q-rear-nextnode;// 新节点接到队尾Q-rearnode;// 更新队尾指针}Q-count;}// 出队intDeQueue(LinkQueue*Q){if(Q-frontNULL){printf(队列为空\n);return-1;}QNode*tempQ-front;intdatatemp-data;Q-fronttemp-next;// 队头后移if(Q-frontNULL)// 队列已空Q-rearNULL;free(temp);Q-count--;returndata;}// 打印队列voidPrintQueue(LinkQueue Q){QNode*pQ.front;printf(队列);while(p!NULL){printf(%d ,p-data);pp-next;}printf(\n);}intmain(){LinkQueue Q;InitQueue(Q);EnQueue(Q,10);EnQueue(Q,20);EnQueue(Q,30);PrintQueue(Q);// 输出10 20 30printf(出队%d\n,DeQueue(Q));// 输出10printf(出队%d\n,DeQueue(Q));// 输出20PrintQueue(Q);// 输出30return0;}六、环形队列与链式队列的对比对比项环形队列数组实现链式队列内存分配静态分配大小固定动态分配灵活扩展空间利用率可能浪费预分配过大无浪费但每个节点多一个指针入队/出队时间复杂度O(1)O(1)队列满条件(tail1)%MAX_SIZEhead内存耗尽适用场景数据量可预估内存受限数据量不确定需要灵活扩展七、队列在嵌入式中的应用在 MCU 开发中链式队列常用于消息队列不同任务之间通过链式队列传递消息串口接收缓冲区接收不定长数据时链式队列可以动态扩展事件队列存储待处理的事件按顺序处理任务调度RTOS 中的就绪队列注意事项在资源受限的 MCU 上动态内存分配malloc/free可能导致内存碎片需要谨慎使用如果数据量可预估建议用环形队列替代链式队列在中断中操作链式队列时需要加临界区保护八、总结本文把队列的几种实现串成了一条清晰的主线队列的定义操作受限的线性表队尾入队、队头出队核心是FIFO先进先出。顺序队列head/tail 只增不减存在**“假溢出”**问题——出队空间无法复用。环形队列用取模运算让数组首尾相接解决假溢出入队出队都是 O(1)。链式队列用 front/rear 两个指针队头删除、队尾插入动态扩展。选型数据量可预估、内存受限选环形队列数据量不确定选链式队列。记住一句话栈是后进先出队列是先进先出两者是一对镜像结构。搞懂了队列下一篇我们进入一个人人都会用、但大有学问的结构——串字符串去讲讲 KMP 模式匹配。