数组实现环形(循环)队列的关键部分总结

预备）队列的概念
只能在表的一端进行插入操作，只能在表的另一端进行删除操作，这种数据结构称为 队列。把允许插入的一端叫 队尾(rear)，允许删除的一端叫 对头(front)。

1）产生背景

将顺序队列首尾相连，形成一个“环”，充分利用空间。

2）如何连接成环？

其实结构上并没有真的成环，仍旧是以数组来存储数据，所谓首尾相连，实际上是对数组空余空间的复用，即当rear指针到达末尾时，他能够去把自己重置，重新从头开始。值得注意的是，要在数组头部没有元素时，才能去插入数据，而判断是否有数据，可通过front指针进行判断，后面会详细讲解。

3）循环队列中，头尾指针的位置与状态的对应关系

这里对rear和front指针做了如下人为规定：
1、rear指针总是指向队列最后一个元素的后一个位置
2、front指针总是指向队列的第一个元素。

这里要注意的是，一般的实现方案中，如果定义数组的长度为n，那么队列能存储的最大数据为n-1个。为什么少了一个呢？这是因为要区分数组为空和满这个状态。当为空的时候是rear=front，而队列满的时候，依旧是rear=front。所以为了区分这两个状态，人为做了一个约定，将数组空出一个位置，一开始默认的时候，rear=front=0，即为空。当满的时候，rear+1=front。但是满的条件判断，在顺序队列中是成立的，但在环形队列中需要作出调整。因为指针是可以“从头开始”，所以对上式作出调整后得到新的判断满的条件为：
（rear+1）%maxSize = front

判断为空的条件为：
front=rear

空出一个位置，还有另外一个好处，可以便于计算队列中的有效元素数量。那么为了实现上面这些目的，就必须空出一个位置，浪费这一个空间吗？答案当然是否定的。可以通过设置标志位，也可以通过计数器来统计，但是为什么主流的实现上，没有采用这些方式呢？因为当处理大规模数据时，维护一个计数器或者标志位，会付出远大于一个空间的代价。且空间在现代计算机中，并不是太稀缺的资源，牺牲空间换取效率是一个很自然的想法。

4）如何获取环形队列中有效元素数？

我们知道，在顺序队列中，判断有效元素数是一个非常容易的事情，rear和front之间的即是有效元素数。但是，在环形队列中，需要考虑的更多一点。我们分如下两种情形来考虑：
1、设数组最大长度为maxSize，当front<rear<maxSize时，
有效元素数 = rear-front

2、当rear<front<maxSize时
有效元素数=maxSize - （front-rear）

综上，我们得到如下关系
有效元素数=（rear-front+maxSize）% maxSize

关键部分已给出，相应代码实现并不难，请自行查找资料，图片来自《数据结构 C语言》一书
（感谢阅读，更多文章请看专栏）

最后

以上就是无聊小笼包为你收集整理的数组实现环形(循环)队列的关键部分总结 获取队列有效元素数，空满判断数组实现环形(循环)队列的关键部分总结的全部内容，希望文章能够帮你解决数组实现环形(循环)队列的关键部分总结 获取队列有效元素数，空满判断数组实现环形(循环)队列的关键部分总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。