news 2026/4/16 19:48:27

【转载】RTOS中队列、环形队列、优先级队列的实现及使用

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
【转载】RTOS中队列、环形队列、优先级队列的实现及使用

1. 什么是队列

队列（queue）是一种只能在一端插入元素、在另一端删除元素的数据结构，遵循「先入先出」（FIFO）的规则。

队列中有两个基本概念：

  • 队头指针（可变）：永远指向此队列的第一个数据元素；

  • 队尾指针（可变）：永远指向此队列的最后一个数据元素；

队列中的数据存储方式有两种：

① 基于静态连续内存（数组）存储，如图：② 基于动态内存（链表节点）存储，如图：

❝

后续都使用基于静态内存存储的队列讲解。

❞

队列提供两个统一的操作：

  • 「入队（enqueue）」

入队将一个元素添加到队尾，并将队尾指针+1后移，如图：

  • 「出队（dequeue）」

出队将从队头中取出一个元素，并将队头指针+1后移，如图：

2. 环形队列

2.1. 环形队列的特点

普通队列的入队操作将队尾指针后移+1，出队操作将队头指针后移+1，操作几次之后会发现队头指针和队尾指针都跑到缓冲区的尾部去了：这就导致了前面的内存空间全被浪费，如果要重新恢复使用，则需要进行元素和指针的移动：显然这种队列使用方式太不方便了，所以就诞生了环形队列：「不用搬移元素和指针，一直可以重复利用这段内存空间」。

2.2. 环形队列的实现

TencentOS-tiny中环形队列的实现在tos_ring_queue.h和tos_ring_queue.c中。

  1. typedefstructk_ring_queue_st {
  2. knl_obj_t knl_obj;
  4. uint16_t head;//队头指针
  5. uint16_t tail;//队尾指针
  6. size_t total;//记录队列中元素的个数
  8. uint8_t *pool;//队列底层的存储结构（一个数组）
  10. size_t item_size;//队列中每个元素的大小，单位：字节
  11. size_t item_cnt;//队列中可以容纳的元素数量
  12. } k_ring_q_t;
智能体编程go运行

环形队列初始化，将队头指针和队尾置0：

  1. __API__ k_err_t tos_ring_q_create(k_ring_q_t *ring_q, void *pool, size_t item_cnt, size_t item_size)
  2. {
  3. //省略了参数合法性检查代码
  4. ring_q->head =0u;
  5. ring_q->tail =0u;
  6. ring_q->total =0;
  8. ring_q->pool = (uint8_t *)pool;
  9. ring_q->item_size = item_size;
  10. ring_q->item_cnt = item_cnt;
  12. returnK_ERR_NONE;
  13. }
智能体编程go运行

判断环形队列是否为满或者为空：

  1. __API__inttos_ring_q_is_empty(k_ring_q_t *ring_q)
  2. {
  3. TOS_CPU_CPSR_ALLOC();
  4. intis_empty = K_FALSE;
  6. //省略了参数合法性检查代码
  7. TOS_CPU_INT_DISABLE();
  8. is_empty = (ring_q->total ==0? K_TRUE : K_FALSE);
  9. TOS_CPU_INT_ENABLE();
  11. returnis_empty;
  12. }
  14. __API__inttos_ring_q_is_full(k_ring_q_t *ring_q)
  15. {
  16. TOS_CPU_CPSR_ALLOC();
  17. intis_full = K_FALSE;
  19. //省略了参数合法性检查代码
  20. TOS_CPU_INT_DISABLE();
  21. is_full = (ring_q->total == ring_q->item_cnt ? K_TRUE : K_FALSE);
  22. TOS_CPU_INT_ENABLE();
  24. returnis_full;
  25. }
智能体编程go运行

环形队列入队操作的API如下：

__API__ k_err_t tos_ring_q_enqueue(k_ring_q_t *ring_q, void *item, size_t item_size);
智能体编程go运行

在此API中，入队操作的实现如下：

  1. __STATIC_INLINE__ void ring_q_item_increase(k_ring_q_t *ring_q)
  2. {
  3. ring_q->tail = RING_NEXT(ring_q, ring_q->tail);
  4. ++ring_q->total;
  5. }
智能体编程go运行

环形队列出队操作的API如下：

__API__ k_err_t tos_ring_q_dequeue(k_ring_q_t *ring_q, void *item, size_t *item_size);
智能体编程go运行

在此API中，出队操作的实现如下：

  1. __STATIC_INLINE__ void ring_q_item_decrease(k_ring_q_t *ring_q)
  2. {
  3. ring_q->head = RING_NEXT(ring_q, ring_q->head);
  4. --ring_q->total;
  5. }
智能体编程go运行

在入队和出队操作的时候都使用了 RING_NEXT 宏，用来获取在环形队列中的下一个位置：

#define RING_NEXT(ring_q, index) ((index +1) % ring_q->item_cnt)
智能体编程go运行
2.3. 环形队列使用Demo

编写如下的测试代码：

  1. #include <tos_k.h>
  3. typedefstruct item_st {
  4. inta;
  5. intb;
  6. intc;
  7. } item_t;
  9. #define RING_QUEUE_ITEM_MAX5
  11. uint8_t ring_q_buffer[RING_QUEUE_ITEM_MAX * sizeof(item_t)];
  13. k_ring_q_t ring_q;
  15. void entry_task_demo(void *arg)
  16. {
  17. k_err_t err;
  18. inti;
  19. item_t item;
  20. size_t item_size;
  22. //创建环形队列
  23. tos_ring_q_create(&ring_q, ring_q_buffer, RING_QUEUE_ITEM_MAX, sizeof(item_t));
  25. //数据入队
  26. for(i =0;i < RING_QUEUE_ITEM_MAX; i++)
  27. {
  28. item.a = i;
  29. item.b = i;
  30. item.c = i;
  32. err = tos_ring_q_enqueue(&ring_q, &item, sizeof(item_t));
  33. if(err == K_ERR_NONE)
  34. {
  35. printf("enqueue a item: %d %d %d\n", item.a, item.b, item.c);
  36. }
  37. else
  38. {
  39. printf("ring queue enqueue fail,err = %d\r\n", err);
  40. }
  41. }
  43. //队列满之后，继续入队
  44. err = tos_ring_q_enqueue(&ring_q, &item, sizeof(item_t));
  45. if(err == K_ERR_RING_Q_FULL)
  46. {
  47. printf("ring queue is full: %s\n", tos_ring_q_is_full(&ring_q) ?"TRUE":"FALSE");
  48. }
  49. else
  50. {
  51. printf("ring queue enqueue fail,err = %d\r\n", err);
  52. }
  54. //数据出队
  55. for(i =0; i < RING_QUEUE_ITEM_MAX; ++i)
  56. {
  57. err = tos_ring_q_dequeue(&ring_q, &item, &item_size);
  58. if(err == K_ERR_NONE)
  59. {
  60. printf("dequeue a item(%d bytes): %d %d %d\n", item_size, item.a, item.b, item.c);
  61. }
  62. else
  63. {
  64. printf("ring queue dequeue fail,err = %d\r\n", err);
  65. }
  66. }
  68. //没有数据后继续出队
  69. err = tos_ring_q_dequeue(&ring_q, &item, &item_size);
  70. if(err == K_ERR_RING_Q_EMPTY)
  71. {
  72. printf("ring queue is empty: %s\n", tos_ring_q_is_empty(&ring_q) ?"TRUE":"FALSE");
  73. }
  74. else
  75. {
  76. printf("ring queue dequeue fail,err = %d\r\n", err);
  77. }
  80. }
智能体编程go运行

运行结果如下：

3. 优先级队列

3.1. 优先级队列的特点

优先级队列也是一种基于队列的数据结构，但是它「不遵循FIFO」，而是按照每个元素的优先级进行出队：「最高优先级的先出队」。

3.2. 优先级队列的实现

TencentOS-tiny中环形队列的实现在tos_prio_queue.h和tos_prio_queue.c中。

优先级队列在数据入队的时候，会按照入队元素的优先级进行一次排序，「将优先级值最小（优先级最高的元素）放在队头」，出队的时候只需要取第一个元素即可。

正是因为这种特性，优先级队列的底层存储结构不能使用数组（排序太麻烦），而是使用了二项堆的数据结构。

❝

二项堆是一种二叉树集合的数据结构，在本文中不再深入讲解，有兴趣的读者可以自己搜索阅读。

❞

下面只给出优先级队列的API，「理解其规则，会用即可」。

  • 创建优先级队列

__API__ k_err_t tos_prio_q_create(k_prio_q_t *prio_q, void *mgr_array, void *pool, size_t item_cnt, size_t item_size);
智能体编程go运行

参数

描述

prio_q

优先级队列控制块指针

mgr_array

提供一块缓冲区用于内部管理

pool

队列的缓冲区

item_cnt

队列可容纳的元素数量

item_size

每个元素的大小，单位字节

其中用于内部管理的缓存区大小可以使用宏定义来计算，比如有5个元素的管理缓冲区大小：

uint8_t mgr_pool[TOS_PRIO_Q_MGR_ARRAY_SIZE(5)];
智能体编程go运行

  • 元素入队

__API__ k_err_t tos_prio_q_enqueue(k_prio_q_t *prio_q, void *item, size_t item_size, k_prio_t prio);
智能体编程go运行

其中优先级的值遵循：数值越小，优先级越高。

  • 元素出队

__API__ k_err_t tos_prio_q_dequeue(k_prio_q_t *prio_q, void *item, size_t *item_size, k_prio_t *prio);
智能体编程go运行

其中prio需要传入一个地址，用于记录出队元素的优先级。

3.3. 优先级队列使用Demo
  1. #include <tos_k.h>
  3. typedefstruct item_st {
  4. inta;
  5. intb;
  6. intc;
  7. } item_t;
  9. #define PRIO_QUEUE_ITEM_MAX5
  11. uint8_t prio_q_buffer[PRIO_QUEUE_ITEM_MAX * sizeof(item_t)];
  12. uint8_t mgr_pool[TOS_PRIO_Q_MGR_ARRAY_SIZE(PRIO_QUEUE_ITEM_MAX)];
  14. k_prio_q_t prio_q;
  16. void entry_task_demo(void *arg)
  17. {
  18. k_err_t err;
  19. inti;
  20. item_t item;
  21. size_t item_size;
  22. k_prio_t item_prio;
  24. //创建优先级队列
  25. tos_prio_q_create(&prio_q, mgr_pool, prio_q_buffer, PRIO_QUEUE_ITEM_MAX, sizeof(item_t));
  27. //数据入队
  28. for(i = PRIO_QUEUE_ITEM_MAX;i >0; i--)
  29. {
  30. item.a = i;
  31. item.b = i;
  32. item.c = i;
  34. err = tos_prio_q_enqueue(&prio_q, &item, sizeof(item), i);
  35. if(err == K_ERR_NONE)
  36. {
  37. printf("enqueue a item: %d %d %d\n", item.a, item.b, item.c);
  38. }
  39. else
  40. {
  41. printf("prio queue enqueue fail,err = %d\r\n", err);
  42. }
  43. }
  45. //队列满之后，继续入队
  46. err = tos_prio_q_enqueue(&prio_q, &item, sizeof(item_t), i);
  47. if(err == K_ERR_PRIO_Q_FULL)
  48. {
  49. printf("prio queue is full: %s\n", tos_prio_q_is_full(&prio_q) ?"TRUE":"FALSE");
  50. }
  51. else
  52. {
  53. printf("prio queue enqueue fail,err = %d\r\n", err);
  54. }
  56. //数据出队
  57. for(i =0; i < PRIO_QUEUE_ITEM_MAX; ++i)
  58. {
  59. err = tos_prio_q_dequeue(&prio_q, &item, &item_size, &item_prio);
  60. if(err == K_ERR_NONE)
  61. {
  62. printf("dequeue a item[piro %d]: %d %d %d\n", item_prio, item.a, item.b, item.c);
  63. }
  64. else
  65. {
  66. printf("prio queue dequeue fail,err = %d\r\n", err);
  67. }
  68. }
  70. //没有数据后继续出队
  71. err = tos_prio_q_dequeue(&prio_q, &item, &item_size, &item_prio);
  72. if(err == K_ERR_PRIO_Q_EMPTY)
  73. {
  74. printf("prio queue is empty: %s\n", tos_prio_q_is_empty(&prio_q) ?"TRUE":"FALSE");
  75. }
  76. else
  77. {
  78. printf("prio queue dequeue fail,err = %d\r\n", err);
  79. }
  80. }
智能体编程go运行

运行结果为：

4. 总结

① 普通队列是一种只能在一端入队，在一端出队的数据结构，规则：FIFO。

② 环形队列对内存空间的利用率最高，使用最多，规则：FIFO。

③ 优先级队列不遵循FIFO，每个元素都有自己的优先级，规则：优先级最高的元素先出队。

声明：本文素材来源网络，版权归原作者所有。如涉及作品版权问题，请与我联系删除。

------------END------------


●专栏《嵌入式工具》

●专栏《嵌入式开发》

●专栏《Keil教程》

●嵌入式专栏精选教程

关注公众号回复“加群”按规则加入技术交流群，回复“1024”查看更多内容。

点击“阅读原文”查看更多分享。

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/15 17:44:56

AI智能预警系统：矿山、工厂与油气站安全管理架构浅析

随着矿山、工厂和油气站等高风险行业对安全管理要求的提升&#xff0c;传统人工巡查已无法满足严格的监管需求。人工巡查存在隐患空档、疏漏和瞒报问题。基于AI智能预警系统&#xff0c;结合深度学习、计算机视觉和大数据分析等前沿技术&#xff0c;能够实现全天候、全方位的智…

作者头像 李华
网站建设 2026/4/16 14:23:18

Multisim14模拟电路仿真入门必看基础指南

Multisim14模拟电路仿真入门&#xff1a;从零搭建你的第一个虚拟实验室你有没有过这样的经历&#xff1f;想做个放大电路&#xff0c;结果面包板刚搭好&#xff0c;三极管就烫得不敢碰&#xff1b;调试滤波器时示波器上全是噪声&#xff0c;却分不清是电路问题还是接线错误&…

作者头像 李华
网站建设 2026/4/15 20:33:07

跨境电商应用案例：用anything-llm管理产品说明书

跨境电商应用案例&#xff1a;用Anything-LLM管理产品说明书 在一家主营小家电的跨境电商公司里&#xff0c;客服主管李婷正为一个老问题头疼——每天要处理上百条来自欧美客户的咨询&#xff1a;“这款吹风机支持220V吗&#xff1f;”“包装里有没有英标插头&#xff1f;”虽然…

作者头像 李华
网站建设 2026/4/16 19:09:42

高速信号完整性设计：电路板PCB布局全面讲解

高速信号完整性设计&#xff1a;从布局到阻抗匹配的实战全解析你有没有遇到过这样的情况&#xff1f;一块PCB板子焊接完成&#xff0c;通电正常&#xff0c;但高速接口就是“抽风”——DDR总线频繁报错、PCIe链路协商失败、千兆以太网丢包严重。示波器一测&#xff0c;眼图几乎…

作者头像 李华
网站建设 2026/4/16 12:16:40

基于数字孪生的产线优化：完整指南

从“看得到”到“管得准”&#xff1a;如何用数字孪生重塑产线优化能力&#xff1f;你有没有遇到过这样的场景&#xff1f;某条关键产线突然停机&#xff0c;维修团队花了几个小时排查&#xff0c;最后发现只是某个传感器信号漂移&#xff1b;或者新产品导入时&#xff0c;反复…

作者头像 李华
网站建设 2026/4/15 12:33:52

anything-llm插件生态展望：未来可能的扩展方向

Anything-LLM 插件生态展望&#xff1a;未来可能的扩展方向 在企业知识管理日益智能化的今天&#xff0c;一个普遍存在的矛盾逐渐凸显&#xff1a;员工面对海量文档却找不到关键信息&#xff0c;而管理者又疲于重复解答相同问题。传统搜索工具因语义理解能力有限&#xff0c;难…

作者头像 李华