exportclassPriorityQueueextendsQueue{ enqueue(element, priority) { const queueElement = new QueueElement(element, priority) if (this.items.length === 0) { this.items.push(queueElement) } else { let added = false for (let i = 0; i < this.items.length; i++) { const element = this.items[i] if (element.priority > queueElement.priority) { this.items.splice(i, 0, queueElement) added = false break } } if (!added) { this.items.push(queueElement) } } } }
代码解析
封装了一个 QueueElement, 将 element 和 priority 封装在一起.
在插入新的元素时, 有如下情况下考虑:
根据新的元素先创建一个新的 QueueElement 对象.
如果元素是第一个被加进来的, 那么不需要考虑太多, 直接加入数组中即可.
如果是后面加进来的元素, 需要和前面加进来的元素依次对比优先级.
一旦优先级, 大于某个元素, 就将该元素插入到元素这个元素的位置. 其他元素会依次向后移动.
如果遍历了所有的元素, 没有找到某个元素被这个新元素的优先级低, 直接放在最后即可.
队列的应用(击鼓传花)
使用队列实现小游戏:击鼓传花,传入一组数据和设定的数字 num,循环遍历数组内元素,遍历到的元素为指定数字 num 时将该元素删除,直至数组剩下一个元素。
击鼓传花的规则
原游戏规则:
班级中玩一个游戏, 所有学生围成一圈, 从某位同学手里开始向旁边的同学传一束花.
这个时候某个人(比如班长), 在击鼓, 鼓声停下的一颗, 花落在谁手里, 谁就出来表演节目.
修改游戏规则:
我们来修改一下这个游戏规则.
几个朋友一起玩一个游戏, 围成一圈, 开始数数, 数到某个数字的人自动淘汰.
最后剩下的这个人会获得胜利, 请问最后剩下的是原来在哪一个位置上的人?
代码实现
1 2 3 4 5 6 7 8 9 10 11 12 13 14
functionpassGame(nameList, num) { const queue = new Queue() for (let i = 0; i < nameList.length; i++) { const element = nameList[i] queue.enqueue(element) } while (queue.size() > 1) { for (let i = 1; i < num - 1; i++) { queue.enqueue(queue.dequeue()) } queue.dequeue() } return queue.front() }
// 队列应用:面试题:击鼓传花 let passGame = (nameList, num) => { //1.创建队列结构 let queue = new Queue() //2.将所有人依次加入队列 // 这是ES6的for循环写法,i相当于nameList[i] for (let i of nameList) { queue.enqueue(i) }
// 3.开始数数 while (queue.size() > 1) { //队列中只剩1个人就停止数数 // 不是num的时候,重新加入队列末尾 // 是num的时候,将其从队列中删除 // 3.1.num数字之前的人重新放入队列的末尾(把队列前面删除的加到队列最后) for (let i = 0; i < num - 1; i++) { queue.enqueue(queue.dequeue()) } // 3.2.num对应这个人,直接从队列中删除 /* 思路是这样的,由于队列没有像数组一样的下标值不能直接取到某一元素,所以采用,把num前面的num-1个元素先删除后添加到队列末尾,这样第num个元素就排到了队列的最前面,可以直接使用dequeue方法进行删除 */ queue.dequeue() }
//4.获取剩下的那个人 console.log(queue.size()) let endName = queue.front() console.log('最终剩下的人:' + endName)