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

文章摘要队列是另一种操作受限的线性表只允许在队尾插入、队头删除核心是先进先出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 模式匹配。

企业数字化 ERP 产品动态

相关推荐

MinerU 4.0 正式发布：让复杂文档成为 Agent 可用的知识基础设施

MinerU 是上海人工智能实验室 OpenDataLab 团队开源的智能文档解析工具，也是开源社区中最受欢迎的复杂文档解析工具之一。它面向 PDF、图片、办公文档、网页、电子书等复杂文档，提供结构化解析与内容提取能力。目前，MinerU 已获得超过 8 万 G… · 2026/11/3 2:22:23

透视每一个请求：OpenRouter ai-sdk-provider调试模式echo_upstream_body实战

【免费下载链接】ai-sdk-provider The OpenRouter provider for the Vercel AI SDK contains support for hundreds of models through the OpenRouter chat and completion APIs. 项目地址： https://gitcode.com/gh_mirrors/ai/ai-sdk-provider 点击查看免费下载 … · 2026/11/3 2:21:23

模拟舵机、数码（数字）舵机、无刷大扭矩舵机区别

核心定义1.模拟舵机（模拟电机舵机） 最早一代舵机，接收 PWM 信号，持续通电检测偏差，有偏差就不停修正。 ✅优点：价格便宜、电路简单，入门 RC 小车、小型模型够用； ❌缺点：… · 2026/11/3 2:21:23

仓库越大越乱？一家郑州五金批发商的“仓库翻身仗“

一、凌晨一点，老板还在仓库里找一颗螺丝郑州某五金行业的老板，曾经有个外号叫"仓库里的夜猫子"。仓库两千平，货架一排接一排，五金工具、机电配件、紧固件加起来三万多个品项。客户一个电话要某个型号的轴承，… · 2026/11/3 2:47:27

html+css基础：30、伸缩盒模型(伸缩项目--伸/缩，flex复合属性，项目排序与单独对齐，案例)

伸缩盒模型的伸缩项目--伸/缩，flex复合属性，项目排序与单独对齐，案例等：Ⅰ、伸缩盒模型的伸缩项目--伸：flex-grow: 0;其一、代码为：其二、结果为：Ⅱ、伸缩盒模型的伸缩项目--缩：flex… · 2026/11/3 2:47:27

内网安全第一道闸：为什么你的网络总被 “陌生人“ 混进来？

引言做过网络 / 安全的都知道，内网失守往往不是防火墙没配好，而是门没看住—— 员工把个人手机、无线路由、不知名摄像头偷偷插进交换机，一台带病毒的工作站随意接入，双网卡电脑绕过隔离直连互联网…… 等你发现时，数… · 2026/11/3 2:47:27

FA_CNN卷积神经网络十九---模型选择、欠拟合与过拟合

FA：Formular and Algorithm，CNN：Convoluation Neural Network 1. 写在前面：为什么用多项式讲模型选择在深度学习中，"模型选择"听起来抽象，但它的本质问题非常朴素：给定一份数据&… · 2026/11/3 2:47:27

经验丰富的汽车安装车载手机互联苹果Carplay和华为Hicar哪家专业

最近好几个朋友都问我，车子上想装个CarPlay或者HiCar，到底去哪里弄靠谱。说真的，我太懂这种纠结了。我自己那台车，当初就是冲着车机互联去的，结果在路边店装完，先是连不上，后来好不容易连上了&a… · 2026/11/3 2:47:27

GitLab 私有化部署太吃内存：只留仓库和合并请求

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