type
status
date
slug
summary
tags
category
icon
password
数组实现环形队列 详细讲解
数组模拟环形队列
对前面的数组模拟队列的优化，将数组看做是一个环形的。(通过取模的方式来实现即可)
解题思路
1、既然是环形队列，那就一定有头有尾，有容量
2、既然是数组实现，那一定有个算法保证可以让数组循环起来
如图所示：
rear为7 ，front为0，实际的数据为7，是因为rear定义指向了最后一个元素的后一个位置，所以满数组的size变成了size-1，空出的位置来保证循环
- front 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素 front 的初始值 = 0
- rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.rear 的初始值 = 0
- 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
- 对队列为空的条件， rear == front 空
- 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
- 我们就可以在原来的队列上修改得到，一个环形队列
代码实现
- 作者:IT小舟
- 链接:https://codegym.top/article/%E6%95%B0%E7%BB%84%E5%AE%9E%E7%8E%B0%E7%8E%AF%E5%BD%A2%E9%98%9F%E5%88%97%20%E8%AF%A6%E7%BB%86%E8%AE%B2%E8%A7%A3
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
