【数据结构与算法】循环队列
循环队列
- 一.循环队列的引入
- 二.循环队列的原理
- 三.循环队列判断是否为满或空
- 1.是否为空
- 2.是否为满
- 四.循环队列入队
- 五.循环队列出队
- 六.循环队列的遍历
- 七.循环队列获取长度
- 八.总结
一.循环队列的引入
还记得我们顺序队列的删除元素嘛,我们有两种方式,一种是将数组要删除元素后面的元素往前面移动.
还有一种是直接将front向后面指,达到删除的效果.
这两种方式有有其弊端,第一种如果数据巨大,需要频繁的移动.
第二种则是对数组空间的浪费,删除越多,越来越多的空间浪费.
那么我们采用循环队列就可以解决这些问题.
二.循环队列的原理
正常我们的尾巴指向末尾,现在我们想办法,将rear指向头位置.
当然数组不是链表,只需要我们就指向一下进行了,我们需要能够循环的指向,当不停的插入的时候,我们不断的循环指向.
三.循环队列判断是否为满或空
1.是否为空
还是跟原来一样,如果front=rear就为空.
2.是否为满
这个就是循环链表的特殊之处了,为了能够循环指向,我们用到了取模运算,我这里MAXSIZE这个宏是5,那么我的rear可以指向0~4一直循环往返.
为什么要用rear加1,这个问题也很关键,为了更能很好的判断是否为满,我们空了一个数组元素,为什么呢?
首先,rear是指向最后一个元素的下一个元素,如果我们插满的话,因为是循环的,那么rear就会等于front,这个与我们判断是否为空就会冲突,所以我们用空数组指向的rear的下一个来判断是否与front相等来判断.
四.循环队列入队
五.循环队列出队
六.循环队列的遍历
七.循环队列获取长度
八.总结
循环队列是一种基于数组实现的队列数据结构，它的特点是可以通过循环利用数组的空间来实现高效的出队和入队操作。循环队列中通常会用到两个指针，分别指向队首和队尾。当队满时，队尾指针会绕回到数组的开头；当队空时，队首和队尾指针相等。循环队列在实际应用中常用于实现缓冲区等场景，可以提高空间利用率和操作效率。