环形队列是循环队列吗（环形队列的实现）



队列的特性: 先进先出,环形队列也不例外,只不过这里的队尾指向队头,所以环形队列也叫"环形缓冲器",同时环形队列的大小是固定的,它可以重复利用某一位置。

环形队列分两种: 链表和数组,这里我们写的是数组的实现方法

我们定义两个变量front和rear,一个指向队头一个指向队尾,每次插入元素的时候rear就++指向下一个位置,这里跟我们顺序表的插入其实是一样的,只不过当rear == n(数组长度-这里我们循环队列的长度是固定的), rear == n的时候我们应该让rear返回到下标为0的位置,或者可以直接对数组长度取模。

1. 入元素(队尾)
2. 出元素(队头)
3. 判空
4. 判满
5. 返回队头元素
6. 返回队尾元素

不过这样写的话会有个问题,就是判空和判满如何判断?,判空简单,判断front是否等于rear就可以了,但如果按照我们上面那个思路的话,当rear+1此时等于n再取模的时候变为0,但是此时数组元素是满的
如下图:

这里有两种解决方案:

这里我们写第二种,第一种我放在文章末尾了

这里我们多开辟一个空间的目的就是防止判空与判满冲突,只要我们的rear+1再对数组长度+1取模等于我们的front就相当于满了,由于之前我们没有多开辟一个空间的时候是直接对数组长度取模,这里多开辟的一个就是对数组长度+1取模

由于队列的特性是:队头入,队尾出。

队头出:
只要我们的front还小于数组长度+1(由于我们多开了一个空间,所以我们此时的长度为原数组长度+1),那我们就可以放心的直接front++,否则我们就要让front++的值对数组长度+1取模

队尾入:

队尾入也是一样的,只需要当rear等于数组+1的时候要对数组加一取模

动图演示:

取队头元素简单,直接取front位置的元素即可

重点是取队尾元素:

1.rear > 0

2. rear == 0

如果此时rear == 0,rear-1就为-1,这样就会导致数组越界,所以我们取(rear-1+SIZE+1）%(SIZE+1)位置的元素,此时即便rear = 0,那我们取得也是最后一个元素,同时rear > 0的时候也是满足条件的。

综上: 我们取队尾元素的时候可以都直接让rear-1再加上数组长度+1再对他取模(数组长度+1)就可以得到准确的位置了。

头文件

源文件

头文件

源文件

版权声明：

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

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