队列

1、队列是遵循FIFO（First In First Out，先进先出，也称为先来先服务）原则的一组有序的项。（例如排队）

2、队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

一、创建队列的类

function Queue() {
　　var items = [];
　　this.enqueue = function(element){
　　　　items.push(element);                        //向队列尾部添加一个（或多个）新的项。
　　};

　　this.dequeue = function(){
　　　　return items.shift();                          //移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
　　};

　　this.front = function(){
　　　　return items[0];　　　　　　　　    //返回队列中第一个元素——最先被添加，也将是最先被移除的元素
　　};

　　this.isEmpty = function(){
　　　　return items.length == 0;              //如果队列中不包含任何元素，返回 true ，否则返回 false
　　};

　　this.clear = function(){
　　　　items = []; 　　　　　　　　　　 　// 清空队列
　　};

　　this.size = function(){
　　　　return items.length;          　　　　// 返回队列的长度
　　};

　　this.print = function(){
　　　　console.log(items.toString());        // 打印队列
　　};
}

二、队列的使用

 

　　var queue = new Queue();
　　console.log(queue.isEmpty());              // 输出true

　　queue.enqueue("John");
　　queue.enqueue("Jack");
　　queue.enqueue("Camila");
　　queue.print();
　　console.log(queue.size());                    // 输出3
　　console.log(queue.isEmpty());            // 输出false
　　queue.dequeue();
　　queue.dequeue();
　　queue.print();

三、优先队列

function PriorityQueue() {

　　var items = [];
　　function QueueElement (element, priority){            // 包含了要添加到队列的元素（它可以是任意类型）及其在队列中的优先级

　　　　this.element = element;
　　　　this.priority = priority;
　　}
　　this.enqueue = function(element, priority){
　　　　var queueElement = new QueueElement(element, priority);
　　　　if (this.isEmpty()){
　　　　　　items.push(queueElement);                       // 如果队列为空，可以直接将元素入列
　　　　}else {
　　　　　　var added = false;
　　　　　　for(var i=0; i<items.length; i++){
　　　　　　　　if (queueElement.priority <items[i].priority){
　　　　　　　　　　items.splice(i,0,queueElement);   //一旦找到 priority 值更大的元素，就插入新元素
　　　　　　　　　　added = true;
　　　　　　　　　　break;                                              // 终止队列循环
　　　　　　　　}
　　　　　　}
　　　　　　if (!added){                                 //  如果要添加元素的 priority 值大于任何已有的元素，把它添加到队列的末尾就行了
　　　　　　　　items.push(queueElement);
　　　　　　}
　　　　}
　　};
　　//其他方法和默认的Queue实现相同
}

四、循环队列

 

function hotPotato (nameList, num){
　　var queue = new Queue(); 
　　for (var i=0; i<nameList.length; i++){
　　　　queue.enqueue(nameList[i]); 
　　}
　　var eliminated = '';
　　while (queue.size() > 1){
　　　　for (var i=0; i<num; i++){
　　　　　　queue.enqueue(queue.dequeue());      // 从队列开头移除一项，再将其添加到队列末尾

　　　　}
　　　　eliminated = queue.dequeue();                   //一旦传递次数达到给定的数字，拿着花的那个人就被淘汰了（从队列中移除）

　　　　console.log(eliminated + '在击鼓传花游戏中被淘汰。');
　　}
　　return queue.dequeue();                        
}
var names = ['John','Jack','Camila','Ingrid','Carl'];
var winner = hotPotato(names, 7);
console.log('胜利者：' + winner);

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有