环形队列特点（环形队列特点有哪些）



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

队列中有两个基本概念：

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

① 基于静态连续内存（数组）存储，如图：

② 基于动态内存（链表节点）存储，如图：

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

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

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

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

2.1. 环形队列的特点

普通队列的入队操作将队尾指针后移+1，出队操作将队头指针后移+1，操作几次之后会发现队头指针和队尾指针都跑到缓冲区的尾部去了：

这就导致了前面的内存空间全被浪费，如果要重新恢复使用，则需要进行元素和指针的移动：

显然这种队列使用方式太不方便了，所以就诞生了环形队列：「不用搬移元素和指针，一直可以重复利用这段内存空间」。

2.2. 环形队列的实现

TencentOS-tiny中环形队列的实现在和中。

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

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

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

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

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

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

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

2.3. 环形队列使用Demo

编写如下的测试代码：

运行结果如下：

3.1. 优先级队列的特点

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

3.2. 优先级队列的实现

TencentOS-tiny中环形队列的实现在和中。

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

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

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

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

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

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

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

3.3. 优先级队列使用Demo

运行结果为：

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

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

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

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/15406.html