>[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.最難理解就是循環隊列的空間是有限的，因此他的頭部尾部指針是不停變換的，整體這里是最難繞的 ~~~