队列是一个有序列表可以用数組或是链表来实现
队列的输出、输入是分别从前后端来处理,因此需要两个变量 front 以及 rear 记录队列前后端的下标front 会随着数据输出而改变,而 rear 則是随着数据输入而改变
maxSize记录该队列的最大容量
-
当 front == rear 时,即队列为空将尾指针往后移
-
若尾指针 rear 小于队列的最大下标 maxSize-1,则将数据存入 rear 所指嘚数组元素中否则无法存入数据。
问题:目前数组使用一次就不能复用没有充分的利用数组空间
改进:使用算法将数组改为环形队列 – 取模
- front 变量含义调整:front 就指向队列的第一个元素,也就是说 arr[front] 就是队列的第一个元素, front 初始值 = 0;
- rear 变量含义调整:rear 指向队列的最后一个元素的后┅个位置希望空出一个空间作为约定,rear 初始值 = 0;