队列学习笔记

案例

银行排队

image-20210117190136814

队列介绍

  • 队列是一个有序列表，可以用数组或是链表来实现。
  • 遵循先入先出的原则。即：先存入队列的数据，要先取出。后存入的要后取出

image-20210117190854596

数组模拟队列

  • 队列本身是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图, 其中 maxSize 是该队列的最大容量
  • 因为队列的输出、输入是分别从前后端来处理，因此需要两个变量 front及rear分别记录队列前后端的下标，front 会随着数据输出而改变，而 rear则是随着数据输入而改变，如图所示:

image-20210117191146621

数组模拟环形队列

思路分析

  1. ront 变量的含义做一个调整： front 就指向队列的第一个元素, 也就是说 arr[front] 就是队列的第一个元素
    front 的初始值 = 0
  2. rear 变量的含义做一个调整：rear 指向队列的最后一个元素的后一个位置. 因为希望空出一个空间做为约定.
    rear 的初始值 = 0
  3. 当队列满时，条件是 (rear + 1) % maxSize == front 【满】
  4. 对队列为空的条件， rear == front 空
  5. 当我们这样分析， 队列中有效的数据的个数 (rear + maxSize - front) % maxSize // rear = 1 front = 0
  6. 我们就可以在原来的队列上修改得到，一个环形队列