function Queue() { //属性 this.items = [] }
//1.将元素加入到队列中 Queue.prototype.enqueue = function (element) { this.items.push(element) } //2.从队列中删除前端元素 Queue.prototype.dequeue = function () { return this.items.shift() } //3.查看前端元素 Queue.prototype.front = function () { return this.items[0] } //4.查看队列是否为空 Queue.prototype.isEmpty = function () { return this.items.length === 0 } //5.查看队列中元素的个数 Queue.prototype.size = function () { return this.items.length } //6.toString方法 Queue.prototype.toString = function () { let resultString = '' for (let i = 0; i < this.items.length; i++) { resultString += this.items[i] + '' } return resultString }
击鼓传花是一个常见的面试算法题.使用队列可以非常方便的实现最终的结果.
原游戏规则:
修改游戏规则:
封装一个基于队列的函数
//击鼓传花 function paseGame(nameList, num) { //创建一个队列 let queue = new Queue() //将所有人依次加入队列 for (let i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]) } //开始数数字 while (queue.size() > 1) { //不是num的时候吗,重新加入到队列的末尾 //num数字之前的人重新放入到队列的末尾 for (let i = 0; i < num - 1; i++) { queue.enqueue(queue.dequeue()) } //num对应的这个人直接从队列中删除 queue.dequeue() } //获取剩下的结果 let endName = queue.front() console.log(endName); return nameList.indexOf(endName) } paseGame(['lisi', 'zhangsan', 'fgbfd', 'tom', 'jack', 'lisa', 'ez', 'laoshu', 'jikdf', 'dsada', 'poru', 'fjds'], 6)//fgbfd
优先级队列的特点:
优先级队列主要考虑的问题:
优先级队列的应用:
//封装优先级队列 function PriorityQueue() { //在PriorityQueue重新创建了一个类 function QueueElemnt(element, priority) { this.element = element this.priority = priority } //封装属性 this.items = [] //1.实现插入方法 PriorityQueue.prototype.enqueue = function (element, priority) { //创建QueueElement对象 let queueElemnt = new QueueElemnt(element, priority) //判断队列是否为空 if (this.items.length === 0) { this.items.push(queueElemnt) } else { let added = false for (let i = 0; i < this.items.length; i++) { if (queueElemnt.priority < this.items[i].priority) { this.items.splice(i, 0, queueElemnt) added = true break } } if (!added) { this.items.push(queueElemnt) } } } //2.从队列中删除前端元素 PriorityQueue.prototype.dequeue = function () { return this.items.shift() } //3.查看前端元素 PriorityQueue.prototype.front = function () { return this.items[0] } //4.查看队列是否为空 PriorityQueue.prototype.isEmpty = function () { return this.items.length === 0 } //5.查看队列中元素的个数 PriorityQueue.prototype.size = function () { return this.items.length } //6.toString方法 PriorityQueue.prototype.toString = function () { let resultString = '' for (let i = 0; i < this.items.length; i++) { resultString += this.items[i] + '' } return resultString } } // 测试代码 let pq = new PriorityQueue() pq.enqueue('abc', 111) pq.enqueue('cba', 151) pq.enqueue('nba', 66) pq.enqueue('wba', 856) console.log(pq);