环形队列是循环队列吗（环形队列是循环队列吗为什么）



  当写代码，不再是简单的完成需求，对代码进行堆砌，而是开始思考如何写出优美代码的时候，我们的代码水平必然会不断提升，今天，咱们来学习环形队列结构。

  相信对数据结构有过接触的小伙伴，对队列肯定不会陌生，队列相对来说是比较简单的数据结构，典型特点是FIFO，即First in First out，先进先出，就像我们日常排队买票一样，先到的人先买票，先从购票口出去，从下面的图中，可以比较形象的了解队列的特性。

  用数组创建一个普通队列，当有数据存储时，队列尾指针不断增加，直到空间用完，当数据出队列时，队列头指针不断增加，直至和队列尾相同时，所有数据完成出队列，那么这时候会引入一个问题，全部出队后，将无法继续入队，这样的情况也叫做“假溢出”，即使数组中，明明还有空间可以利用，但是却无法使用(平时我们做串口接收的时候，往往是通过清零计数器，清空数组，重新接收来解决这一问题)。

  只要思想不滑坡，方法总比困难多。为了解决上面“假溢出”的现象，环形队列应运而生，即通常将一维数组Queue[0]到Queue[MAXSIZE - 1]看成是一个首尾相连接的圆环，即Queue[0]与Queue[MAXSIZE - 1]相连接在一起，将这样形式的队列成为循环队列。

  在计算机的内存中，是不存在所谓的环形内存区域的，所以，需要程序员认为的“画个圈圈”，从图示环形队列来看，存储空间有限，当数据存到末端时，如何处理呢，只需要重新转回0的地址区域，有点像“驴拉磨”的意思......

  环列队列的是逻辑上将数组元素q[0]与q[MAXN-1]连接，形成一个存放队列的环形空间。

  环形队列设计的重要部分是，确定队列的状态，即队列时空还是满状态。根据上面介绍的存储顺序，数据存储时，队列尾指针移动，头指针不动，数据读取时，头指针移动，尾指针不动，但是如果从单纯的“tail==head”还无法得出是处于空还是满状态，需要加些判断手段：

1、tail追上head时，tag=1，队列为满状态

2、head追上tail时，tag=0，队列为空状态

在存储数据时，最后一个位置与队列头预留至少一个单位的空间

1、head==tail 队列为空

2、(tail+1)% MAXN ==head 队列满

  环形队列的原理也算比较简单，弄清楚了原理之后，进行代码的编写。

先来定义个结构体：

初始化队列：

判断是否为空队列：

插入元素：

读取元素：

先来对这种方法进行测试：

测试结果：

代码与第一种方法区别不大，主要在空、满状态的判断上，代码如下：

main函数与上面相同：

测试结果：

  相比较上面的测试结果，小伙伴们有没有发现什么不同之处呢，我们main函数想把5个元素写入队列，实际上只写进去了4个，原因在与，我们预留了一个单元空间，用于判断队列空或者满的状态。

  本次的介绍就到这里啦，下章介绍：环形队列在单片机中的应用，欢迎大家持续关注嵌入式实验基地，来这里还可以学习HAL库+cubemx的更多精彩内容哦！

  如果你觉得对自己有帮助的话，给个赞，点个关注，点个在看，感谢前进的道路上有你的陪伴！

  所有公众号文章资料源码已上传，关注公众号回复资料即可获取哦，欢迎加群一起炸起来！

- END -

版权声明：

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

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