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

文章摘要

队列是另一种操作受限的线性表，只允许在队尾插入、队头删除，核心是"先进先出"（FIFO，First In First Out）。本文用 C 语言逐一拆解队列的几种实现：顺序队列、环形队列、链式队列，重点讲解顺序队列的"假溢出"问题及环形队列的取模解法，并对比环形队列与链式队列的选型，帮助嵌入式开发者理解消息队列、串口缓冲、任务调度背后的原理。

本栏系列文章

学透CANFD看这个就行(四): 错误帧、位填充、采样点与通信负荷

其他专栏精品文章

CSDN高赞项目：工程训练竞赛之垃圾分类垃圾桶

前言

上一篇我们讲了栈（后进先出），这一篇进入它的"镜像"结构——队列（先进先出）。栈是后进先出，队列正好反过来。队列在嵌入式里几乎无处不在：串口接收缓冲、消息队列、RTOS 就绪队列，全都是它。本文用 C 语言把队列的几种实现逐一拆开。

一、队列的定义

队列是一种操作受限的线性表，只允许在一端进行插入操作（队尾），在另一端进行删除操作（队头）。这种特性称为先进先出（FIFO，First In First Out）。
打个比方：就像排队买票，先来的人排在前面，先买到票离开；后来的人排在后面，后买到票。这就是队列的典型行为。

二、队列的基本操作

辅助操作：

• 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;}

六、环形队列与链式队列的对比

七、队列在嵌入式中的应用

在 MCU 开发中，链式队列常用于：

• 消息队列：不同任务之间通过链式队列传递消息
• 串口接收缓冲区：接收不定长数据时，链式队列可以动态扩展
• 事件队列：存储待处理的事件，按顺序处理
• 任务调度：RTOS 中的就绪队列

注意事项：

• 在资源受限的 MCU 上，动态内存分配（malloc/free）可能导致内存碎片，需要谨慎使用
• 如果数据量可预估，建议用环形队列替代链式队列
• 在中断中操作链式队列时，需要加临界区保护

八、总结

本文把队列的几种实现串成了一条清晰的主线：

1. 队列的定义：操作受限的线性表，队尾入队、队头出队，核心是FIFO（先进先出）。
2. 顺序队列：head/tail 只增不减，存在**“假溢出”**问题——出队空间无法复用。
3. 环形队列：用取模运算让数组首尾相接，解决假溢出，入队出队都是 O(1)。
4. 链式队列：用 front/rear 两个指针，队头删除、队尾插入，动态扩展。
5. 选型：数据量可预估、内存受限选环形队列；数据量不确定选链式队列。

记住一句话：栈是"后进先出"，队列是"先进先出"，两者是一对镜像结构。搞懂了队列，下一篇我们进入一个"人人都会用、但大有学问"的结构——串（字符串），去讲讲 KMP 模式匹配。