news 2026/4/23 14:15:47

【转载】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/23 8:31:05

数字频率计输入放大整形电路实战案例

从微弱信号到精准计数&#xff1a;一文讲透数字频率计的“眼睛”如何看清世界你有没有遇到过这种情况——手里的信号明明是10MHz正弦波&#xff0c;可频率计就是“看走眼”&#xff0c;测出来跳动不止、误差几十kHz&#xff1f;问题往往不在于后面的算法多牛&#xff0c;而在于…

作者头像 李华
网站建设 2026/4/23 8:32:46

K8S-EFK日志收

部署EFK1、创建nfs存储访问启动master节点的nfs服务创建/data/v1kubectl create -f serviceaccount.yaml ​ kubectl create -f rbac.yaml修改deployment.yaml文件NFS SERVER #存储地址 ​ kubectl create -f deployment.yaml ​ kubectl create -f class.yaml2、构建es集群kub…

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

字体大小调节与可访问性改进方案

字体大小调节与可访问性改进方案 在智能知识系统日益普及的今天&#xff0c;一个看似微小的设计细节——字体能否自由调整——往往决定了产品是真正“以人为本”&#xff0c;还是仅仅停留在功能堆砌的层面。尤其对于像 anything-LLM 这样集成了RAG引擎、支持多格式文档上传与自…

作者头像 李华
网站建设 2026/4/23 8:35:44

基于CMOS的一位全加器结构分析：专业级解读

一位全加器的CMOS电路设计深度解析&#xff1a;从逻辑到晶体管在数字系统的世界里&#xff0c;最基础的操作往往蕴藏着最深刻的工程智慧。加法——这个我们从小学就开始掌握的运算&#xff0c;在芯片内部却是一场由数十个微小晶体管协同完成的精密舞蹈。而这场舞蹈的核心角色之…

作者头像 李华
网站建设 2026/4/23 8:32:42

开源AI应用推荐：anything-llm让知识管理更简单

开源AI应用推荐&#xff1a;anything-llm让知识管理更简单 在企业文档堆积如山、员工总在重复查找同一份报销政策的今天&#xff0c;有没有一种方式能让知识“主动说话”&#xff1f;想象一下&#xff1a;你只需问一句“去年Q3项目审批要走哪些流程”&#xff0c;系统立刻给出…

作者头像 李华
网站建设 2026/4/23 11:19:00

避免重复上传：文件去重机制在anything-llm中的实现

避免重复上传&#xff1a;文件去重机制在 anything-llm 中的实现 在构建基于私有文档的智能问答系统时&#xff0c;一个看似微小却影响深远的问题逐渐浮出水面&#xff1a;用户反复上传“几乎一样”的文件。可能是同一份PDF被不同命名多次提交&#xff0c;也可能是Word转成PDF后…

作者头像 李华