TencentOS-tiny中队列、环形队列、优先级队列的实现及使用

野性酷女 2022-09-14 09:38 177阅读 0赞

# 1. 什么是队列 #

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

队列中有两个基本概念：

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

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

① 基于静态连续内存（数组）存储，如图：![c3b976c6998d9ebbcf0389ad67f4376d.png][]② 基于动态内存（链表节点）存储，如图：![db2bb57c254edc35579cbd93214784c4.png][]

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

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

*  **「入队（enqueue）」**

入队将一个元素添加到队尾，并将队尾指针+1后移，如图：![c65832d9e6bd1092685f36c13c932ebb.png][]

*  **「出队（dequeue）」**

出队将从队头中取出一个元素，并将队头指针+1后移，如图：![c4771dd58cde794d05ada1f1fad1ca58.png][]

# 2. 环形队列 #

### 2.1. 环形队列的特点 ###

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

### 2.2. 环形队列的实现 ###

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

typedef struct k_ring_queue_st {
        knl_obj_t   knl_obj;
    
        uint16_t    head; //队头指针
        uint16_t    tail; //队尾指针
        size_t      total; //记录队列中元素的个数
    
        uint8_t    *pool; //队列底层的存储结构（一个数组）
    
        size_t      item_size; //队列中每个元素的大小，单位：字节
        size_t      item_cnt; //队列中可以容纳的元素数量
    } k_ring_q_t;

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

__API__ k_err_t tos_ring_q_create(k_ring_q_t *ring_q, void *pool, size_t item_cnt, size_t item_size)
    {
     //省略了参数合法性检查代码
        ring_q->head        = 0u;
        ring_q->tail        = 0u;
        ring_q->total       = 0;
    
        ring_q->pool        = (uint8_t *)pool;
        ring_q->item_size   = item_size;
        ring_q->item_cnt    = item_cnt;
    
        return K_ERR_NONE;
    }

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

__API__ int tos_ring_q_is_empty(k_ring_q_t *ring_q)
    {
        TOS_CPU_CPSR_ALLOC();
        int is_empty = K_FALSE;
    
        //省略了参数合法性检查代码
        TOS_CPU_INT_DISABLE();
        is_empty = (ring_q->total == 0 ? K_TRUE : K_FALSE);
        TOS_CPU_INT_ENABLE();
    
        return is_empty;
    }
    
    __API__ int tos_ring_q_is_full(k_ring_q_t *ring_q)
    {
        TOS_CPU_CPSR_ALLOC();
        int is_full = K_FALSE;
    
      //省略了参数合法性检查代码
        TOS_CPU_INT_DISABLE();
        is_full = (ring_q->total == ring_q->item_cnt ? K_TRUE : K_FALSE);
        TOS_CPU_INT_ENABLE();
    
        return is_full;
    }

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

__API__ k_err_t tos_ring_q_enqueue(k_ring_q_t *ring_q, void *item, size_t item_size);

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

__STATIC_INLINE__ void ring_q_item_increase(k_ring_q_t *ring_q)
    {
        ring_q->tail = RING_NEXT(ring_q, ring_q->tail);
        ++ring_q->total;
    }

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

__API__ k_err_t tos_ring_q_dequeue(k_ring_q_t *ring_q, void *item, size_t *item_size);

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

__STATIC_INLINE__ void ring_q_item_decrease(k_ring_q_t *ring_q)
    {
        ring_q->head = RING_NEXT(ring_q, ring_q->head);
        --ring_q->total;
    }

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

#define RING_NEXT(ring_q, index)    ((index + 1) % ring_q->item_cnt)

### 2.3. 环形队列使用Demo ###

编写如下的测试代码：

#include <tos_k.h>
    
    typedef struct item_st {
        int a;
        int b;
        int c;
    } item_t;
    
    #define RING_QUEUE_ITEM_MAX 5
    
    uint8_t ring_q_buffer[RING_QUEUE_ITEM_MAX * sizeof(item_t)];
    
    k_ring_q_t ring_q;
    
    void entry_task_demo(void *arg)
    {
        k_err_t err;
        int i;
        item_t item;
        size_t item_size;
        
        //创建环形队列
        tos_ring_q_create(&ring_q, ring_q_buffer, RING_QUEUE_ITEM_MAX, sizeof(item_t));
        
        //数据入队
        for(i = 0;i < RING_QUEUE_ITEM_MAX; i++)
        {
            item.a = i;
            item.b = i;
            item.c = i;
            
            err = tos_ring_q_enqueue(&ring_q, &item, sizeof(item_t));
            if(err == K_ERR_NONE)
            {
                printf("enqueue a item: %d %d %d\n", item.a, item.b, item.c);
            }
            else
            {
                printf("ring queue enqueue fail,err = %d\r\n", err);
            }
        }
        
        //队列满之后，继续入队
        err = tos_ring_q_enqueue(&ring_q, &item, sizeof(item_t));
        if(err == K_ERR_RING_Q_FULL)
        {
            printf("ring queue is full: %s\n", tos_ring_q_is_full(&ring_q) ? "TRUE" : "FALSE");
        }
        else
        {
            printf("ring queue enqueue fail,err = %d\r\n", err);
        }
        
        //数据出队
        for(i = 0; i < RING_QUEUE_ITEM_MAX; ++i)
        {
            err = tos_ring_q_dequeue(&ring_q, &item, &item_size);
            if(err == K_ERR_NONE)
            {
                printf("dequeue a item(%d bytes): %d %d %d\n", item_size, item.a, item.b, item.c);
            }
            else
            {
                printf("ring queue dequeue fail,err = %d\r\n", err);
            }
        }
        
        //没有数据后继续出队
        err = tos_ring_q_dequeue(&ring_q, &item, &item_size);
        if(err == K_ERR_RING_Q_EMPTY)
        {
            printf("ring queue is empty: %s\n", tos_ring_q_is_empty(&ring_q) ? "TRUE" : "FALSE");
        }
        else
        {
            printf("ring queue dequeue fail,err = %d\r\n", err);
        }
        
    
    }

运行结果如下：![44a8d280a09083684103c272d705cc0d.png][]

# 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);

<table> 
 <thead> 
  <tr> 
   <th>参数</th> 
   <th>描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>prio_q</td> 
   <td>优先级队列控制块指针</td> 
  </tr> 
  <tr> 
   <td>mgr_array</td> 
   <td>提供一块缓冲区用于内部管理</td> 
  </tr> 
  <tr> 
   <td>pool</td> 
   <td>队列的缓冲区</td> 
  </tr> 
  <tr> 
   <td>item_cnt</td> 
   <td>队列可容纳的元素数量</td> 
  </tr> 
  <tr> 
   <td>item_size</td> 
   <td>每个元素的大小，单位字节</td> 
  </tr> 
 </tbody> 
</table>

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

uint8_t mgr_pool[TOS_PRIO_Q_MGR_ARRAY_SIZE(5)];

*  元素入队

__API__ k_err_t tos_prio_q_enqueue(k_prio_q_t *prio_q, void *item, size_t item_size, k_prio_t prio);

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

*  元素出队

__API__ k_err_t tos_prio_q_dequeue(k_prio_q_t *prio_q, void *item, size_t *item_size, k_prio_t *prio);

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

### 3.3. 优先级队列使用Demo ###

#include <tos_k.h>
    
    typedef struct item_st {
        int a;
        int b;
        int c;
    } item_t;
    
    #define PRIO_QUEUE_ITEM_MAX 5
    
    uint8_t prio_q_buffer[PRIO_QUEUE_ITEM_MAX * sizeof(item_t)];
    uint8_t mgr_pool[TOS_PRIO_Q_MGR_ARRAY_SIZE(PRIO_QUEUE_ITEM_MAX)];
    
    k_prio_q_t prio_q;
    
    void entry_task_demo(void *arg)
    {
        k_err_t err;
        int i;
        item_t item;
        size_t item_size;
        k_prio_t item_prio;
        
        //创建优先级队列
        tos_prio_q_create(&prio_q, mgr_pool, prio_q_buffer, PRIO_QUEUE_ITEM_MAX, sizeof(item_t));
        
        //数据入队
        for(i = PRIO_QUEUE_ITEM_MAX;i > 0; i--)
        {
            item.a = i;
            item.b = i;
            item.c = i;
            
            err = tos_prio_q_enqueue(&prio_q, &item, sizeof(item), i);
            if(err == K_ERR_NONE)
            {
                printf("enqueue a item: %d %d %d\n", item.a, item.b, item.c);
            }
            else
            {
                printf("prio queue enqueue fail,err = %d\r\n", err);
            }
        }
        
        //队列满之后，继续入队
        err = tos_prio_q_enqueue(&prio_q, &item, sizeof(item_t), i);
        if(err == K_ERR_PRIO_Q_FULL)
        {
            printf("prio queue is full: %s\n", tos_prio_q_is_full(&prio_q) ? "TRUE" : "FALSE");
        }
        else
        {
            printf("prio queue enqueue fail,err = %d\r\n", err);
        }
        
        //数据出队
        for(i = 0; i < PRIO_QUEUE_ITEM_MAX; ++i)
        {
            err = tos_prio_q_dequeue(&prio_q, &item, &item_size, &item_prio);
            if(err == K_ERR_NONE)
            {
                printf("dequeue a item[piro %d]: %d %d %d\n", item_prio, item.a, item.b, item.c);
            }
            else
            {
                printf("prio queue dequeue fail,err = %d\r\n", err);
            }
        }
        
        //没有数据后继续出队
        err = tos_prio_q_dequeue(&prio_q, &item, &item_size, &item_prio);
        if(err == K_ERR_PRIO_Q_EMPTY)
        {
            printf("prio queue is empty: %s\n", tos_prio_q_is_empty(&prio_q) ? "TRUE" : "FALSE");
        }
        else
        {
            printf("prio queue dequeue fail,err = %d\r\n", err);
        }
    }

运行结果为：![b7c13ed90d22d5e09d0d44ca3e5abfd9.png][]

# 4. 总结 #

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

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

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

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

\------------ **END** ------------

![0ee9dba834b27c56402aa2d1db59c77b.gif][]

[**●嵌入式专栏精选教程**][Link 1]

[**●精选汇总 | ST工具、下载编程工具**][_ ST]

[**●精选汇总 | 嵌入式软件设计与开发**][Link 2]

[**●精选汇总 | STM32、MCU、单片机**][_ STM32_MCU]

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

**欢迎关注我的视频号：**

![e3e213be073d0753edf60d82b5530423.png][]

点击“**阅读原文**”查看更多分享，欢迎**点分享、收藏、点赞、在看。**

[c3b976c6998d9ebbcf0389ad67f4376d.png]: https://img-blog.csdnimg.cn/img_convert/c3b976c6998d9ebbcf0389ad67f4376d.png
[db2bb57c254edc35579cbd93214784c4.png]: /images/20220828/eb5322b157694f76a6fd7c4613a3018d.png
[c65832d9e6bd1092685f36c13c932ebb.png]: /images/20220828/1c7c84bf13fd4d348e2c9a72c77bad17.png
[c4771dd58cde794d05ada1f1fad1ca58.png]: /images/20220828/b0d91dd34ad347cba5e08de036478abb.png
[d8e28e0f10cb0415fadfcc432eeeb82b.png]: https://img-blog.csdnimg.cn/img_convert/d8e28e0f10cb0415fadfcc432eeeb82b.png
[fbaffaad76d434290fe6d5ee2c29b442.png]: https://img-blog.csdnimg.cn/img_convert/fbaffaad76d434290fe6d5ee2c29b442.png
[7be573c198d48283383c509345953f84.png]: /images/20220828/db82667ef5624a3fa0bd9dd48cce3682.png
[44a8d280a09083684103c272d705cc0d.png]: /images/20220828/39a8282ce5dd41e2982d7021621f749f.png
[b7c13ed90d22d5e09d0d44ca3e5abfd9.png]: /images/20220828/5dab6fe5f9dc44628ac04e5c2d34042b.png
[0ee9dba834b27c56402aa2d1db59c77b.gif]: /images/20220828/4449fe92d99d409581f92b9542f330eb.png
[Link 1]: http://mp.weixin.qq.com/s?__biz=MzUxNjgxMDE4OQ==&mid=2247490732&idx=3&sn=fe17751c678c2d0451956f6ce16bfa45&chksm=f9a0e80eced761189daea6e7b2d245fae32d117caa0b4af8f770c1f15a9c8b27c5a7e701d02e&scene=21#wechat_redirect
[_ ST]: https://mp.weixin.qq.com/s?__biz=MzI4MDI4MDE5Ng==&mid=2247500196&idx=3&sn=e91f59c8aa8efe6c6d697fb97ba5ba56&scene=21#wechat_redirect
[Link 2]: https://mp.weixin.qq.com/s?__biz=MzI4MDI4MDE5Ng==&mid=2247502904&idx=2&sn=c1f461b14949c53d3916ea1c2be4b629&scene=21#wechat_redirect
[_ STM32_MCU]: https://mp.weixin.qq.com/s?__biz=MzI4MDI4MDE5Ng==&mid=2247502904&idx=3&sn=c42a2f88226fda826e097c90c9dbb655&scene=21#wechat_redirect
[e3e213be073d0753edf60d82b5530423.png]: /images/20220828/806b15a74e8d40d79c3f208bb2a29d45.png