JavaScript数据结构与算法——队列
栏目: JavaScript · 发布时间: 5年前
内容简介:队列和栈非常类似,但是使用了不同的原则,而非后进先出,是先进先出。队列遵循FIFO(先进先出,也称先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的的末尾。队列示意图如下:
队列和栈非常类似,但是使用了不同的原则,而非后进先出,是先进先出。
1.队列数据结构
队列遵循FIFO(先进先出,也称先来先服务)原则的一组有序的项。队列在尾部添加新元素,并从顶部移除元素。最新添加的元素必须排在队列的的末尾。队列示意图如下:
2.创建队列
// 创建一个类表示队列 function Queue() { // 使用数组作为存储队列的数据结构 let items = []; // 下面声明队列一些可用的方法 // 1.enqueue(elements) 向队尾添加一个或多个项 this.enqueue = function(element) { items.push(element); } // 2.dequeue() 从队列移除元素 FIFO this.dequeue = function() { return item.shift(); } // 3.front() 查看队列头元素 this.front = function() { return items[0]; } // 4.isEmpty() size() 检查队列是否为空 this.isEmpty = function() { return items.length === 0; } this.size = function() { return items.length; } // 5.打印队列元素 this.print = function() { console.log(items.toString()) } }
使用Queue类
let queue = new Queue(); console.log(queue.isEmpty()); // true // 添加元素 queue.enqueue('june'); queue.enqueue('jack'); queue.print(); // 'june,jack' console.log(queue.size()); // 2 // 删除元素 queue.dequeue(); queue.dequeue(); queue.print(); // ''
3.优先队列
实现一个有限队列,有两种选择:设置优先级,然后在正确的位置添加元素;或者用入列操作添加元素,然后按照他们的优先级移除他们。
function PriorityQueue() { let items = []; // 设置添加元素的类 function QueueElement(element, priority) { this.element = element; this.priority = priority; } // 优先级添加 this.enqueue = function(element, priority) { let queueElement = new QueueElement(element, priority); let added = false; // 遍原队列中的元素,如果新添加元素的优先级的值(优先级大,priority值小)小于当前遍历原始的优先级的值(即新添加元素优先级大于当前遍历元素的优先级),则在其前面添加新的元素 for(let i=0; i<items.length; i++) { if(queueElement.priority < items[i].priority) { items.splice(i, 0, queueElement); added = true; break; } } if(!added) { items.push(queueElement); } } // 打印 this.print = function() { for(let i=0; i<items.length; i++) { console.log(`${items[i].element}-${items[i].priority}`) } } // 其他方法和默认的Queue实现方式相同 }
4.队列的应用——击鼓传花:rose:(循环队列)
// nameList-参与的人 num-每轮传:rose:次数 function hotPotato(nameList, num) { let queue = new Queue(); // 初始化队列 for(let i=0; i<nameList.length; i++) { queue.enqueue(nameList); } // let eliminated = ''; // 进行循环队列的入队和出队 while(queue.size() > 1) { for(let i=0; i<num; i++) { queue.enqueue(queue.dequeue); } // 传花停止-淘汰队列第一个 eliminated = queue.dequeue(); console.log(eliminated + '在击鼓传花:rose:中被淘汰。') } // 最后一个出队列的为胜者:rose: return queue.dequeue(); }
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。