队列

视频：https://www.bilibili.com/video/BV18z4y1D7W9

队列就是先进先出的一种线性数据结构。

队列的数据结构

队列一般用

{
    length: 100, // 队列的长度
  front：0, // 队头下标
  rear：0, // 队尾下标
}

入队操作

在rear对应下标处存储，并且rear += 1。

出队操作

取出并删除在rear对应下标处存储，并且rear += 1。

假溢出

由于front和rear都只会++ 导致rear可能会溢出，但整个队列里的元素并没有满，这种现象就叫假溢出。

循环队列

循环队列当 （front 或 rear） + 1 溢出时就需要将 front 或 rear 指向 0 , 总结如下：

const newFront = (front + 1) % arrayLength;
const newRear = (rear + 1) % arrayLength;

问题：

• 这样的循环队列无法判断满还是空，因为当满或者空时front和rear都指向同一个位置。如何解决？
  • 队列中舍弃一个元素，当入队时探测rear的下标是不是队尾，如果是直接循环到0。这样的话(rear+1)%length === front 时就是满；front===rear 时就是空;

队列的长度

const queueLength = （rear - front + maxQueueLength）% maxQueueLength;