>[success] # 实现一个循环队列 [循环队列](https://blog.csdn.net/jessica0510/article/details/52472924) ~~~ 1.为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向 量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻 辑上看成一个环，成为循环队列。 ~~~ * 如图来自极客时间  >[danger] ##### 代码实现 ~~~ 1.循环队列的思路，初始化一个队列的长度，每次数据是在这个设置的范围内去执行，头部和尾部指针也是动态 变化，这里要注意的循环队列是会空出一位，这是为了区分'队列为空' 和'队列是否已满'，举个例子说明 1.1当前循环队列长度为 4，没有数据的时候，头部指针和尾部指针都应在 0 0位置，即数组的0下角标处， 也就是判断队列是否为空的条件则为 '头部指针 == 尾部指针' 2.1如果按照现在的思路则整个循环队列形成闭环则队列已满条件也为 '头部指针 == 尾部指针',现在出现的问题 对区分循环队列形成闭环的条件和队列为空的条件冲突，这时候采用的解决方案为，'减少一个空间使用'， 也就是一个'长度为5的循环队列，实际使用为4',此时判断公式'(队尾+1) % 队列长度 === 队列首位' 3.长度计算公式分两种： 3.1.当'尾部指针'大于'头部指针'时，循环队列的长度：'尾部指针-头部指针' 3.2.当'尾部指针'小于'头部指针'时，循环队列的长度:分为两类计算 0+'尾部指针'和 '队列长度'-'头部指针'即'尾部-头部+队列长度' 3.3.总的来说，总长度是'(尾部-头部+队列长度)%队列长度' ~~~ * 头部指针和尾部指针有一个空出位置（head头 ，tail尾部）  * 在具体解释这个过于抽象 ~~~ 1.当前有个数据为[1,2,3,4,5] 想给这个数据放进一个循环队列长度为'5',此时如果按照我们正常思路来说，整个 循环队列应该是可以塞进去这个数组的，但是刚才说了头部和尾部会每次留出一个空的空间因此实际存的循环 队列的效果是'[1, 2, 3, 4, empty]' 2.接着分析此时头部指针为'0',尾部的指针为'4'，这时候我们缩小队列长度为'3'，这时候整个数组是大于我们的 循环队列因此，我们会做出列和进列的一系列操作，此时收尾指针依次是'2','1'.循环队列显示效果为'[5, null, 4]', 这里的null就是保留的空间 ~~~ ~~~ // 循环队列 class CircularQueue{ constructor(){ this.items = [] // 循环队列的头 this.count = 0 // 循环队列的尾部 this.lowestCount =0 // 循环队列的头部 this.n = 0 // 队列的长度 } // 申请一个大小为capacity 长度的数组 circularQueue(capacity){ this.items = new Array(capacity) this.n = capacity } // 判断队列长度 size(){ return (this.count- this.lowestCount + this.n) %this.n } // 判断队列是否为空 isEmpty(){ return this.count === this.lowestCount } // 队尾添加元素 // 循环队列长度是固定的 因此需要判断当前是否已经满了 enqueue(ele){ console.log(ele) if((this.count+1) % this.n === this.lowestCount){ return false } this.items[this.count] = ele this.count = (this.count+1) % this.n return true } // 移除队列中第一个元素 dequeue(){ if(this.isEmpty()){ return undefined } const ret = this.items[this.lowestCount] this.items[this.lowestCount] = null this.lowestCount = (this.lowestCount+1) % this.n return ret } // 返回队列中第一个元素 peek(){ if (this.isEmpty()) { return undefined; } return this.items[this.lowestCount] } toString() { if (this.isEmpty()) { return ''; } let objString = `${this.items[this.lowestCount]}`; for (let i = this.lowestCount + 1; i < this.count; i++) { objString = `${objString},${this.items[i]}`; } return objString; } clear() { this.items = {}; this.count = 0; this.lowestCount = 0; this.n = 0 } } ~~~ >[danger] ##### 代码使用 ~~~ function useCircularQueue(list,n){ const circularQueue = new CircularQueue() circularQueue.circularQueue(n) for(let i=0;i<list.length;i++){ // const flag = circularQueue.enqueue(list[i]) if( i>=n){ circularQueue.dequeue() } circularQueue.enqueue(list[i]) } console.log(circularQueue.items) } const list = [1,2,3,4,5] useCircularQueue(list,3) // 打印结果： [5, null, 4] ~~~ >[danger] ##### 总结 ~~~ 1.最难理解就是循环队列的空间是有限的，因此他的头部尾部指针是不停变换的，整体这里是最难绕的 ~~~