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