[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的特殊性，所以上面的循环队列简单来说就是条件判断，和下面章节的循环队列不同， 想特殊语言为了保持空间，会使用数组并且规定好长度，这样一来不会出现无限长度的问题 ~~~