2023-06-23 05:36:59 来源:博客园
循环队列多用于通信数据缓存中,尤其是在双方设备接收数据与处理数据不同步的情况下,使用循环队列先缓存通信数据,然后按照时间戳数据出队作出相应的处理,是一种比较合适的做法,在嵌入式编程中亦是如此。使用循环队列的数据结构可以实现上述功能,在一些低端的编程平台手写一个循环队列既满足了功能需求又不会开销太多资源。
设计思想实现一个队列可以使用顺序表(数组)或链表实现。前者访问速度块,但是要占用连续的存储空间,适用于内存小但是速度要求较快的存储场合。后者访问速度慢但是基于链表式的结构,可以使用碎片内存,适用内存大,速度慢的场合。本文面向的编程平台是中低端MCU,时钟主频、RAM空间有限,因此选用顺序表来实现循环队列。关于顺序表实现循环队列的文章网上又很多,但是大多都基于一个明确的数据类型,如果在一个工程中两种完全不同的数据类型都想使用循环队列的数据结构就会使得相同的代码出现多次,导致代码冗余。泛类型循环队列的思想是将顺序表中每个节点都看作一个uint8_t*类型的指针,在队列初始化时,要传入节点占用空间字节数,对每个节点malloc一个相应的存储空间,当数据入队时使用memcpy函数将源地址字节数拷贝到目标地址即可,队列数据表的结构有点类似于哈希表,操作与定类型循环队列类似。
代码实现队列实现包含两个文件:queue.h和queue.cqueue.h:使用枚举自定义BOOL类型,C99标准之后包含stdbool.h可使用标准布尔型
(相关资料图)
typedef enum { FALSE, TRUE } BOOL;
宏定义顺序表中的节点类型
#define NODTETYPE uint8_t*
定义循环队列结构体
typedef struct Queue{uint32_t capacity; // 队列总容量uint32_t size; // 当前队列大小uint32_t front; // 队列头节点uint32_t rear; // 队列尾节点 NODTETYPE* data; //存储节点的顺序表} Queue;
接口函数
/* 初始化一个队列 */BOOL init_queue(Queue *queue,uint32_t _capacity,uint32_t DataWidth);/* 数据入队 */BOOL en_queue(Queue* _queue, NODTETYPE _data,uint32_t DataWidth);/*队列判空*/BOOL isempty_queue(Queue* _queue);/*队列判满*/BOOL isfull_queue(Queue* _queue);/* 数据出队 */NODTETYPE de_queue(Queue* _queue);/* 清空队列 */void clear_queue(Queue* _queue);
queue.c队列初始化,此处必须传入节点的数据占用字节数DataWidth,注意可用队列容量总是比传入参数_capacity小一,因为要判空和判满。
BOOL init_queue(Queue *queue,uint32_t _capacity,uint32_t DataWidth){ NODTETYPE *buff= (NODTETYPE*)malloc(_capacity*sizeof(NODTETYPE)); if(buff==NULL) return FALSE; for(int i=0;i<_capacity;i++) { NODTETYPE NodeTemp=(NODTETYPE)malloc(DataWidth); if(NodeTemp==NULL) return FALSE; else buff[i]=NodeTemp; } queue->data=buff; queue->capacity = _capacity; queue->size = 0; queue->front = 0; queue->rear = 0; return TRUE;}
数据节点入队
BOOL en_queue(Queue* _queue, NODTETYPE _data,uint32_t DataWidth){ BOOL isFull; isFull = isfull_queue(_queue); if (isFull == TRUE) { _queue->front = (_queue->front + 1) % _queue->capacity; } memcpy(_queue->data[_queue->rear], _data,DataWidth); _queue->rear = (_queue->rear + 1) % _queue->capacity; _queue->size++; return isFull;}
数据节点出队
NODTETYPE de_queue(Queue* _queue){ if (isempty_queue(_queue)) return NULL; NODTETYPE result = _queue->data[_queue->front]; _queue->front = (_queue->front + 1) % _queue->capacity; _queue->size--; return result;}
队列清空,但是不释放存储空间
void clear_queue(Queue* _queue){ _queue->front = _queue->rear = 0; _queue->size = 0;}
队列判空
BOOL isempty_queue(Queue* _queue){if (_queue->front == _queue->rear)return TRUE;elsereturn FALSE;}
队列判满
BOOL isfull_queue(Queue* _queue){if ((_queue->rear + 1) % _queue->capacity == _queue->front)return TRUE;elsereturn FALSE;}
队列清空并释放内存
void release_queue(Queue* _queue){ for(int i=0;i<_queue->capacity;i++) { free(_queue->data[i]); _queue->data[i]=NULL; } clear_queue(_queue); free(_queue); _queue = NULL;}
调用时入队时,要先将节点数据类型强制转化为uint8_t类型,传入形参,出队时获取一个uint8_t的指针,然后强制转换为定义的节点类型指针,之后就可以访问到出队节点的数据,举例如下:
#include "queue.h"typedef struct ClassTest //定义测试类型{ uint8_t a; uint16_t b; uint32_t c;}ClassTest;int main(int argc, char *argv[]){ Queue queue1; Queue queue2; init_queue(&queue1,100,sizeof (ClassTest)); init_queue(&queue2,200,1); //测试队列2就用uint8_t int i=0; uint8_t queue1_node=0; ClassTest queue2_node={0,0,0}; while(isfull_queue(&queue1)==FALSE) { queue1_node=i++; en_queue(&queue1,&queue1_node,sizeof (queue1_node)); } i=0; while(isfull_queue(&queue2)==FALSE) { queue2_node.a=i++; queue2_node.b=2*i; en_queue(&queue2,(uint8_t*)(&queue2_node),sizeof (queue2_node)); } while(isempty_queue(&queue1)==FALSE) { NODTETYPE node=de_queue(&queue1); printf("%d;",*((uint8_t*)(node))); } while(isempty_queue(&queue2)==FALSE) { NODTETYPE node=de_queue(&queue2); prinf("%d;",((ClassTest*)(node))->b); }}
标签:
- 加快虚拟仿真实训基地建设 启动职业学校信息化建设试点很必要
- “双减”后如何在满足学生多样需求方面做“加法”?
- 处于生理活跃期且心理发展不成熟 高校开设公共卫生必修课很必要
- 价格低于相应蔬菜零售价 西安投放约1万吨政府储备蔬菜
- 深受年轻消费群体所青睐 国潮风商品成为年货新选择
知识
- 他把银行卡卖给骗子,“黑吃黑”“截胡”十万元
- “老司机”4S店试驾豪车 结果油门当刹车撞了
- 新开工改造城镇老旧小区5.34万个
- 发动巡河志愿者2万余名 “用心护好每一条河”
- 假客服的套路:伪装成大平台客服,层层布局引人上钩
人物
- 浙江两轮核酸检测结果均为阴性 无新增本土阳性感染者
- 新疆阿克苏地区库车市发生4.1级地震 震源深度18千米
- 抵返哈尔滨人员须持48小时内核酸检测阴性证明
- 浙大紫金港校区已解封 有7337人有序离开该校区
- 2021年广东省第七届风筝锦标赛落幕
- 黑龙江讷河市启动全员核酸检测 目前讷河市全员核酸检测结果均为阴性
- 【同心粤港澳 携手大湾区】南头古城,搭建深港澳三地文化创意活动交流平台
- 重庆入河排污口整治工作推进至全市26个区县
- 四川省第二批政法队伍教育整顿:立案审查调查省级政法机关干警58人
- 长三角区域生态环境部门“云签约”长江大保护倡议书
- 古老长城重焕新生机
- 藏不住了!你同事里有许多“武林高手”……
- 浙江杭州2例无症状感染者系感染德尔塔变异株
- 喜马拉雅的深情和誓言
- 浪漫之城打造山海城一体新地标
- 让老年人更适应数字生活
- 内蒙古通辽市新增1例本土确诊病例、1例无症状感染者
- 徐州无新增确诊病例 核酸检测55515人结果均为阴性
- 甘肃培树“农家巧娘”增技能:返乡创业掌勺又“掌柜”
- 内蒙古通辽市科尔沁区一地调整为中风险地区
- 上海本轮疫情涉及闭环管理的医疗机构全面恢复门急诊
- 青年学生成艾滋病感染高发人群 “社会疫苗”如何打?
- 内蒙古满洲里新增本土确诊病例1例 当地开展第二轮大规模核酸检测
- 江西无新增本土确诊病例 上饶全面恢复正常生产生活秩序
- 中老铁路上会四国语言的列车长:用心维护中老友谊的桥梁
- 海南首次发现有环志的世界极危鸟种勺嘴鹬
- 一场“网络劝生者”和“网络劝死者”的战役
- 内蒙古通辽新增本土确诊和无症状感染者各1例 轨迹公布
- 江西中烟工业有限责任公司原总经理姚庆艳接受审查调查
- 宁夏45例新冠肺炎确诊病例均已治愈出院
- 内蒙古通辽市科尔沁区发现2名初筛阳性人员
- 生活在闹钟里的丈夫:自己迟一秒,渐冻症妻子就会多一分疼
- 辽宁新冠肺炎确诊病例零新增
- 11月28日16-24时,内蒙古新增本土确诊病例1例
- 奥密克戎毒株为何“需要关注”?现有防疫工具还有效吗?
- 黑龙江新增本土无症状感染者1例
- 这辈子一定要去趟这个公园 在这里“有种爱叫放手”
- 那年今日 | 一张漫画涨知识之11月29日
- 寒潮预警!我国中东部迎大范围降温 黑龙江等地降幅可达12℃
- 冷空气继续影响我国中东部 华北黄淮等地有雾和霾天气