队列

2018-06-24 00:57:54来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

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
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:相册

下一篇:js闭包理解