[TOC] >[success] # 實現一個隊列 ~~~ 1.要讓封裝的類遵循，'先入先出原則'，并且要具備最基本的兩個操作，'入隊 enqueue()'，放一個數據到隊列尾部； '出隊 dequeue()'，從隊列頭部取一個元素 ~~~ >[info] ## 基于js 對象實現隊列 * 先進先出原則,并且是從隊尾進入，隊頭出去  ~~~ 1.首先封裝隊列前，隊列需要具備的一下方法： enqueue(element(s))：向隊列的尾部添加一個（或多個）新項 dequeue()：移除隊列的第一項（即當前排在最前面的項）并且返回移除的元素 peek()：返回隊列中第一個元素 -- 最先被添加的元素，該方法不會改變隊列僅僅是返回它 isEmpty()：如果隊列里沒有任何元素就返回 true，否則返回 false。 size()：返回隊列里的元素個數。該方法和數組的 length 屬性很類似。 2.需要兩個標記指用來記錄'隊列頭'和'隊列的尾部' ~~~ ~~~ class Queue{ constructor(){ this.count = 0; // 記錄隊尾 this.lowestCount = 0; // 記錄隊頭 this.items = {}; } // 返回隊列長度 size(){ return this.count - this.lowestCount } // 是否為空 isEmpty(){ return this.size() === 0 } // 向隊列尾部添加一個或多個新項 enqueue(element){ this.items[this.count] = element; this.count++; } // 移除隊列第一項，并返回移除的元素 dequeue(){ if(this.isEmpty()){ return undefined; } const result = this.items[this.lowestCount] delete this.items[this.lowestCount]; this.lowestCount ++; return result; } // 返回隊列中第一個元素 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; } } ~~~ * 使用 ~~~ const queue = new Queue(); queue.enqueue('John'); queue.enqueue('Jack'); queue.enqueue('Camila'); queue.dequeue(); console.log(queue.items); // 打印結果： {1: "Jack", 2: "Camila"} ~~~ >[info] ## 使用隊列完成傳花 -- 循環隊列 ~~~ 1.一群人圍成圈傳遞花，規定當到達指定次數的時候淘汰手里那花的人 2.當花從一個人手里傳出的時候，到他臨邊的人此時，這個人相當于隊伍的最尾端，相當于從 隊首變成了隊尾，符合隊列的'先進先出'原則，并且形成閉環 3.因為勝利的人只有一個所以，在隊列元素不是僅有一個的時候，就不停的進行隊列進出操作 ~~~ >[danger] ##### 代碼 * 如圖  ~~~ function hotPotato(elementsList, num){ const queue = new Queue() const elimitatedList = []; for (let i = 0; i < elementsList.length; i++) { queue.enqueue(elementsList[i]); } // 因為最后只能剩一個因此用隊列size 來判斷 while(queue.size()>1){ for(let i=0;i<num;i++){ queue.enqueue(queue.dequeue()) } // 記錄每局被淘汰的人 elimitatedList.push(queue.dequeue()) } console.log(queue.count); // 打印33 return { eliminated: elimitatedList, winner: queue.dequeue() }; } const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl']; const result = hotPotato(names, 7); ~~~ * 使用api 實現 ~~~ function?win(arr,times){ ????????while(arr.length>1){ ????????????for(let?i=0;i<times;i++){ ????????????????arr.push(arr.shift()) ????????????} ????????????arr.shift() ????????} ????} ~~~ >[danger] ##### 總結 ~~~ 1.因為利用js的特殊性，所以上面的循環隊列簡單來說就是條件判斷，和下面章節的循環隊列不同， 想特殊語言為了保持空間，會使用數組并且規定好長度，這樣一來不會出現無限長度的問題 ~~~