循环队列

[wl05]

为什么要有循环队列

我们可以借助这个图来理解一下，我们用数组来实现队列，如图中所示，我们给队列分配了四个存储单位，现在已经存满了，我们出队0，1，现在我们剩出2个空间，现在如果我们进行入队操作，如图我想入队4，此时显然是不行的，因为3后没有多余的存储空间了，但其实我们看到此时的队列是还有空闲的空间的（这种现象我们称之假溢出）。
那我们怎么把空闲的空间利用起来呢，答案就是我们今天要讲的循环队列了。

循环队列

还是借助图我们一起来理解一下，简单理解就是把队列“掰弯”然后形成一个环，首跟尾相连。
我们用front、rear分别标识队首和队尾，设为正整数，入队一个元素rear 加1，出队一个元素front + 1.

如何判断队列满和空

很明显的，当rear === front 的时候，队列有可能是空也有可能是满。如何区分呢，通常的做法是我们空出一个存储空间，使得当队列不为空时，front跟rear 至少间隔一个存储空间。如上图所示，这样我们就可以设置循环队列的一些前置条件了：

• 给循环队列分配maxSize的存储空间
• front、rear 初始值为0
• front === rear 的时候我们就可以判定队列为空
• 入队操作时，rear = (rear+1)%maxSize,取余是为了使rear值进入一个[0，maxSize]的循环，以上面的图来理解，maxSize = 4，假如在进行入队出队操作后，rear的值为3，这样在下一次入队操作时rear的值为（3+1）% 4 = 0 ，这样就进入循环了。
• 出队操作时，front = (front+1)%maxSize
• (rear + 1) % maxSize === queue.front 参考上面的理解。

代码实现

有了上面的理解后，我们一起来用代码实现循环队列吧。

class LoopQueue {
    constructor() {
        this.front = 0
        this.rear = 0
        this.maxSize = 4
        this.queueList = []
    }

    //判断队列是否为空
    isEmpty() {
        return this.front === this.rear
    }

    //判断队列是否已满
    isFull() {
        return (this.rear + 1) % this.maxSize === this.front
    }

    //取循环队列的队头元素
    getFront() {
        return this.isEmpty() ? '' : this.queueList[this.front]
    }

    //入队
    enQueue(val) {
        if (this.isFull()) {
            console.log('Warn：队列已满！')
            return ''
        } else {
            this.queueList[this.rear] = val
            this.rear = (this.rear + 1) % this.maxSize
        }
    }

    // 出队
    deQueue() {
        if (this.isEmpty()) {
            console.log('Warn:队列已空!')
        } else {
            this.front = (this.front + 1) % this.maxSize
        }
    }

    //获取队列真实长度
    QueueLength() {
        if(this.isEmpty()){
            return 0
        }else{
            return (this.rear - this.front + this.maxSize) % this.maxSize;
        }
    }
    print(){
        console.log("队列数据",this.queueList)
    }
}

const q = new LoopQueue();
q.enQueue(5);
q.enQueue(4);
q.enQueue(3);
q.enQueue(2); // Warn：队列已满！
q.enQueue(1); // Warn：队列已满！
q.print() // 队列数据 [ 5, 4, 3 ] // 此时队列已经满了
console.log("队列长度:" + q.QueueLength(),"队头元素:" + q.getFront()); // 队列长度:3 队头元素:5
q.deQueue();
q.print() // 队列数据 [ 5, 4, 3 ] // 因为我们只是front + 1操作，所以数组中的元素并不会减少，这里理解一下
q.enQueue(1);
q.print() // 队列数据 [ 5, 4, 3, 1 ] // 上面的出队操作，5已经出队了，所以此时队头元素是4
console.log("队列长度:" + q.QueueLength(),"队头元素:" + q.getFront()); // 队列长度:3 队头元素:4
q.deQueue();
q.deQueue();
q.deQueue();
q.deQueue(); // Warn:队列已空!
q.print() // 队列数据 [ 5, 4, 3, 1 ]
console.log("队列是否为空：" + q.isEmpty()); // 队列是否为空：true
console.log("队头元素:" + q.getFront()); // 队头元素:
console.log("队列长度:" + q.QueueLength()); // 队列长度:0

参考

1. 队列的理解和实现(一) ----- 循环队列(java实现)
   
2. 数据结构：循环队列