也是对数组类似的线性数据结构加以限制魔改的一种数据结构！
区别于栈，栈好比是个一个口的容器，比如水杯子，进去出去的口只有一个，还是同一个口：栈顶！只不过，出去的顺序是先进后出，这里加以限制了。而且无法插入操作。

队列，跟栈类似，无法中间插入操作（优先级队列的操作更符合预编排，预留插槽的观念，而不是插入操作，只是预留好了优先级高的空位权限的理念而已。），也讲究顺序，只不过讲究先进先出的顺序。
队列，其实就是生活中的排队取钱，排队打饭。

栈，容器的命。队列是个流通通道，管道，讲究流动，讲究流动控制。

JS的任务队列

js队列其实听了很多了，在异步执行时，经常听到的词。JS执行是单线程的，但是浏览器是多线程的，浏览器可以用其他线程对多个异步操作进行定时，用事件轮询机制，不断看这些异步操作的计时器到了没，到了就把对应异步回调函数放到任务队列中。
任务队列中，先放进去的先被JS引擎执行。后面的需要等前面的执行完了，才能被执行。
cpu在多任务并行时，多线程的优化，也是有队列的控制参与的。

队列的特性

  • 先进先出，也讲究顺序
  • 两个口，前端进行删除，后端进行添加。
  • 移除第一个元素，用数组很消耗性能，最好用链表。

截屏2020-03-28 下午12.21.10.png

  1. //数组实现：
  2. class Queue {
  3.     constructor(arr = []) {
  4.         this.lists = arr;
  5.     }
  7.     //尾部新增
  8.     enqueue(...lists) {
  9.         lists.map(list=>this.lists.push(list));
  10.     }
  12.     //首部移除
  13.       //这里是数组，其实这里的移除操作，会很消耗性能的。最佳方式是用链表。
  14.     dequeue() {
  15.         return this.lists.shift();
  16.     }
  18.     //返回队列中的第一个元素
  19.     front() {
  20.         return this.lists[0];
  21.     }
  23.     //空：
  24.     isEmpty() {
  25.         return this.lists.length === 0;
  26.     }
  28.     //个数：
  29.     size() {
  30.         return this.lists.length;
  31.     }
  32.     //转成字符串：
  33.     toString(){
  34.         return this.lists.reduce(
  35.             (a,b)=>a+ (a? ' <- ':'')+(''+b),''
  36.         )
  37.     }
  38. }
  41. const queue = new Queue([1,2,3])
  42. console.log(queue.toString(),queue.front(),);
  43. queue.enqueue(6)
  44. queue.enqueue(7,8,9)
  46. console.log(queue.dequeue(),queue);

优先级队列

看似跟队列的不可中间插入很矛盾的，，，
其实是预留好了权限空位的。
这种预编排，预留空位的设计，其实是为了包容队列的更广泛的应用场景。
生活中的队列，比如排队，说是没有插队，那是因为排队的规则是相对的。

优先级高的，就优先在前面。比如各种vip特权，老人孩子特权。高危病人特权！
计算机里的很多任务，如果傻瓜式地不允许插队，按着默认顺序在队列中执行，就是错的！因为不尊重人，无人性！人才是根本！

  1. 权限高：a,b,c,
  2.   权限中：d,e,f
  3. a -> [权限高区...,d,e,f...权限中区,...权限低区]
  4. [a,d,e,f,...]

优先级更倾向于，人性，规则！
上面说过，队列是个流通管道，控制任务的进出，一种可控的流水线理念！但是，这是机器的理念，人的理念是，人为可以控制任务的出去的结果！
为了不像数组一样不受限，需要一种规则。
当然，相对同等优先级的，不允许插队！
所以优先级出来了！
根据优先级，预留好插槽，插槽是逻辑上的插槽，而不是代码上的，代码里体现在逻辑上。
根据数据的优先级确定进入队列时的位置。
最根本的是：不一定先进先出，但是一定是按队列的位置从前端依次执行！
**

实现：2分法牛皮！

  1. //优先级队列的实现：
  2. //默认的传入数据为{data:xxx,priority:1}
  3. //priority的值不可重复，递增式的数字类型！
  4. //初始默认的arr参数，顺序遵循priority的order。
  5. class PriorityQueue extends Queue {
  6.     enqueue(...lists) {
  7.         lists.map(
  8.             list => {
  9.                 if (
  10.                     this.lists.length === 0 ||
  11.                     this.lists[this.lists.length - 1].priority > list.priority
  12.                 ) return this.lists.push(list);
  13.                     //傻瓜式线性遍历：
  14.                 if (this.lists.length < 6) {
  15.                     let res;
  16.                     for (let i = 0; i < this.lists.length; i++) {
  17.                         if (this.lists[i].priority < list.priority) {
  18.                             this.lists.splice(i, 0, list);
  19.                             res = true;
  20.                             break;
  21.                         }
  22.                     }
  23.                 } else {
  24.                   //放纵一下，尝试用2分发搞的：
  25.                     let getIndex = (length) =>
  26.                         // length % 2 === 0 ? [length / 2 - 1, length / 2] :
  27.                         Math.round(length / 2) - 1
  28.                     ;
  29.                     let length = this.lists.length;
  30.                     let index = getIndex(length);
  31.                     let max, min;
  32.                     while (index) {
  33.                         if (min && max && min + 1 === max) {
  34.                             this.lists.splice(max - 1, 0, list);
  35.                             return index = null;
  36.                         }
  38.                         const {priority} = this.lists[index];
  39.                        // console.log("indss:", priority, index, "dd", min, max);
  40.                         if (priority > list.priority) {
  41.                             min = min && min > index + 1 ? min : index + 1;
  42.                             length = min +(max|| this.lists.length);
  43.                             index = getIndex(length);
  44.                             // console.log('in', index,'pri:', priority);
  45.                         } else {
  46.                             const {priority} = this.lists[index - 1];
  47.                             // console.log('in2222', index,'pri:', priority);
  49.                             if (priority > list.priority) {
  50.                                 this.lists.splice(index, 0, list);
  51.                                 index = null;
  52.                             } else {
  53.                                 max = max && max < index ? max : index;
  54.                                 index = getIndex(max);
  55.                             }
  56.                             // console.log('in2', index,'pri:', priority);
  57.                         }
  58.                     }
  59.                 }
  60.             }
  61.         );
  62.     }
  63. }
  66. const pq = new PriorityQueue(
  67.     [
  68.         {data: 1, priority: 300},
  69.         {data: 1, priority: 200},
  70.         {data: 1, priority: 100},
  71.         {data: 1, priority: 50},
  72.         {data: 1, priority: 25},
  73.         {data: 1, priority: 12},
  74.         {data: 1, priority: 6}
  75.     ]
  76. );
  78. pq.enqueue({data: 2, priority: 40});
  80. pq.enqueue(
  81.     {data: 2, priority: 30},
  82.     {data: 2, priority: 400},
  83.     {data: 2, priority: 7},
  84.     {data: 2, priority: 150}
  85. );
  87. console.log(pq, 0);