queue

数据结构和算法，和语言是无关的

队列的特点
1. 一种受限的线性表，先进先出(FIFO : first in first out)
2. 其限制是仅允许在表的前端进行删除
3. 而在表的后端(rear)进行插入操作
生活中类似的队列结构
- 电影院，商场甚至是厕所排队
- 优先排队的人优先处理(买票，结账等)
打印队列
- 有5份文档需要打印，这些文档会按次序放入到打印队列
- 打印机会依次从队列中取出文档，优先放入的文档，优先被取出打印
- 直到队列中不再有新的文档
线程队列
- 在开发中，为了让任务可以并行处理，通常会开启多个线程
- 但是，我们不能让大量的线程同时运行处理任务(占用过多资源)
- 这个时候，如果有需要开启线程处理任务的情况，我们就会使用线程队列
- 线程队列会依照次序来启动线程，并且处理对应的任务

队列的实现(基于数组)

队列的常见操作
- enqueue(element) : 向队列尾部添加一个(或多个)新的项
- dequeue() : 移除队列第一(即排在队列最前面的)项，并返回被移除的元素
- front() : 返回队列中的第一个元素，最先被添加，也将是最先被移除的元素。但是队列不做任何变动(不移除元素，只返回元素信息。类似栈中peek)
- isEmpty() : 如果队列里没有任何元素就返回true，否则返回false
- size() : 返回队列里元素个数

队列的实现

 // 声明队列
function Queue() {
    // 栈中属性
    this.items = [];
    // enqueue 添加元素到队列尾部
    this.enqueue = function(element) {
        this.items.push(element);
    }
    // dequeue 移除队列第一项
    this.dequeue = function() {
        return this.items.shift();
    }
    // front 返回队列中的第一个元素
    this.front = function() {
        if (this.isEmpty()) return null;
        return this.items[0];
    }
    // isEmpty 队列没有任何元素就返回true，否则返回false
    this.isEmpty = function() {
        return this.items.length === 0;
    }
    // size 返回队列里元素个数
    this.size = function() {
        return this.items.length;
    }
 }

面试题-击鼓传花

要求
1. 几个朋友一起玩个游戏，围在一圈，开始数数，数到某个数字的人自动淘汰
2. 最后剩下的这个人会获胜，请问最后剩下的是哪个人

实现

var nameList = ["Why", "Tom", "LiLei", "Lucy"];
transferGame(nameList, 3);
/**
 * 依次从队列头取出某个人，没数到某个数字的人，再放回到队列尾部
 * 例: Why Tom LiLei Lucy  数到3的人淘汰，最后剩谁
 * @param nameList 参加的所有人
 * @param number 数到几被淘汰
 */
function transferGame(nameList, number) {
  var queue1 = new Queue();
  // 初始化队列
  for (let name of nameList) {
    queue1.enqueue(name);
  }
  // 方法1
  var count = 1;
  while(queue1.size() > 1) {
    var name = queue1.dequeue();
    if (count === number) {
      // 淘汰的人的下一个人
      name = queue1.dequeue();
      count = 1;
    }
    count ++;
    queue1.enqueue(name);
  }
  console.log("方法1 : " + queue1.items);
  // 方法2
  var queue2 = new Queue();
  for (let name of nameList) {
    queue2.enqueue(name);
  }
  while(queue2.size() > 1) {
    for (let i = 1; i < 3; i++) {
      // 没数到3的时候，队列里出来的人依次再添加回去
      queue2.enqueue(queue2.dequeue());
    }
    queue2.dequeue();
  }
  console.log("方法2 : " + queue2.items);
}

优先级队列
- 普通队列插入一个元素，数据会被放到后端
- 优先级队列在插入一个元素的时候，会考虑该数据的优先级
- 和其他数据的优先级进行比较
- 比较完成后，得出这个元素在队列中的正确的位置
优先级队列主要考虑的问题
- 每个元素不再只是一个数据，而且包含数据的优先级
- 在添加方式中，根据优先级放入正确的位置
优先级队列的应用
- 机场的登机顺序
  - 头等舱和商务舱乘客优先级高于经济舱乘客
  - 老年人和孕妇也享有高于其他乘客的优先级
- 医院急诊科候诊室
  - 医生优先处理病情比较严重的患者
  - 一般情况下是按照排号的顺序
- 计算机中也可以通过优先级队列来重新排序队列中任务的顺序
  - 每个线程处理的任务重要性不同, 可以通过优先级的大小, 来决定该线程在队列中被处理的次序

优先级队列实现

function  PriorityQueue() {
   // 用父类的属性, 方法初始化子类
   // 相当于es6 extends
   Queue.call(this);
   // 重写方法
   this.enqueue = function (element, priority) {
     // 1.创建QueueElement对象
     var queueElement = new QueueElement(element, priority);
     // 2.考虑如何插入新的元素
     if (this.isEmpty()) {
       this.items.push(queueElement);
     } else {
       var added = false;
       for (var i = 0; i < this.items.length; i++) {
         if (this.items[i].priority > queueElement.priority) {
           // 0: 不删除index开始的元素
           this.items.splice(i, 0, queueElement);
           added = true;
           break;
         }
       }
       if (!added) {
         this.items.push(queueElement);
       }
     }
   }
 }
 var que = new PriorityQueue();
 que.enqueue("aa", 100);
 que.enqueue("bb", 150);
 que.enqueue("cc", 120);
 que.enqueue("dd", 90);
 console.log(que.items);
 // 如果原队列的原型上有某方法, 需要继承的话，通过以下方法
 function object(o) {
   function F() {};
   F.prototype = o;
   return new F();
 }
 function Inherit(subClass, parentClass) {
   // F实例 F实例的原型对象 = 父类的原型对象
   var temp = object(parentClass.prototype);
   // 为了让F实例作为子类的原型对象
   temp.constructor = subClass;
   subClass.prototype = temp;
 }
 Inherit(PriorityQueue, Queue);