2. 数据结构-队列

其实队列跟栈有很多相似的地方,包括其中的一些方法和使用方式,只是队列使用了与栈完全不同的原则,栈是后进先出原则,而队列是先进先出(First In First Out)原则.

1.队列

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。

队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

一个完整的队列需要的方法：

enqueue(element(s))，入队，向队列尾部添加一个或者多个元素。
dequeue()，出队，移除队列中的第一个元素，也就是队列最前面的元素，并返回该元素。
front()，获取队列最前面的元素，返回队列中第一个元素（最先被添加，也是最先被移除的元素）。队列并不移除该元素。
isEmpty()，判断队列是否不包含任何元素。
size()，返回队列的元素总数。

构造函数实现队列

//声明Queue类
function Queue() {
  //声明并初始化一个用来存放队列元素的数组。
  let 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;
  };

  //获取队列元素个数
  this.size = function () {
    return items.length;
  };
  //打印该队列
  this.print = function () {
    console.log(items.toString());
  };
}
const queue = new Queue();
console.log(queue.isEmpty()); // outputs true
queue.enqueue("John");
queue.enqueue("Jack");
queue.print(); // John,Jack
queue.enqueue("Camila");
queue.print(); // John,Jack,Camila
console.log(queue.size()); // outputs 3
console.log(queue.isEmpty()); // outputs false
queue.dequeue(); // remove John
queue.dequeue(); // remove Jack
queue.print(); // Camila

Class 配合 WeakMap 实现队列

let Queue = (function () {
  const items = new WeakMap();
  class Queue {
    constructor() {
      //强调一下，这里items是WeakMap类型的数据，而WeakMap是键值对，有专属的set和get方法来获取和设置值，　　　　　　　　//所以这里给this设置了[]，即以this为键名，[]为值，所以该方法形成的队列仍旧是对数组的操作
      items.set(this, []);
    }
    enqueue(element) {
      let q = items.get(this); //这里的q就相当于是[]
      q.push(element);
    }
    dequeue() {
      let q = items.get(this);
      let r = q.shift();
      return r;
    }
    front() {
      return items.get(this)[0];
    }
    isEmpty() {
      return items.get(this).length == 0;
    }
    size() {
      return items.get(this).length;
    }
    print() {
      console.log(items.get(this));
    }
  }
  return Queue;
})();

2.优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出（first in, largest out）的行为特征。就像是我们在窗口买票，机场排队，正常来说我们都是依照排队的顺序从队列的最前面开始依次进入，但是有规定老人孩子军人等优先，那么就赋予了该老人（孩子军人）插队的权利。而优先队列，同样就是给特定元素赋予插队（优先级）的权利。我想要入队，并不一定是直接到尾部。而是根据我设定的优先级来插入队列。

其实优先队列在实现上不同的地方是队列元素的设定和入队方法的不同（这里其实有两种实现方式，一个是按照优先级入列，一个是按照优先级出列，这里我们只用第一种方式实现）。

//声明Queue类
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;
    //遍历队列元素，1的优先级最高，一次类推，如果当前元素优先级大于items[i]，那么就把该元素放在items[i]前面。
    //splice方法的第二的参数如果为0，那么则把第三个参数添加到i前面。
    for (let i = 0; i < items.length; i++) {
      if (queueElement.priority < items[i].priority) {
        items.splice(i, 0, queueElement);
        added = true;
        break;
      }
    }
    // 通过added判断是否可以直接把元素入列。
    if (!added) {
      items.push(queueElement);
    }
  };
  //移除并返回该队列元素
  this.dequeue = function () {
    return items.shift();
  };
  //获取队列头部元素
  this.front = function () {
    return items[0];
  };
  //判断队列元素是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };

  //获取队列元素个数
  this.size = function () {
    return items.length;
  };
  //循环打印元素及其优先级“``”是ES6的模板字符串
  this.print = function () {
    for (let i = 0; i < items.length; i++) {
      console.log(`${items[i].element} - ${items[i].priority}`);
    }
  };
}
const queue = new PriorityQueue();
console.log(queue.isEmpty()); // outputs true

queue.enqueue("zaking", 2);
queue.enqueue("linbo", 6);
queue.enqueue("queue", 5);
queue.enqueue("ada", 3);
queue.enqueue("John", 1);
queue.enqueue("Jack", 2);
queue.enqueue("Camila", 3);
queue.enqueue("zak", 3);
queue.print();

主要的更改在于队列元素的设置和 enqueue 方法，由于需要为每一个循环队列的元素设置优先级，所以这里稍微更改了一下队列的元素，使其带有两个参数（元素自身和优先级），那么既然要根据不同的优先级来插入队列，所以循环队列的 enqueue 方法也就需要循环整个队列去判断要插入到哪里。

其实这个优先队列的实现并不是很好，还有很多优化空间,比如我不传第二优先级参数,那么队列打印的时候该参数就是 undefined，而且在不传参数的时候应该默认为最末优先级。

2.数据结构-队列

2. 数据结构-队列

1.队列

构造函数实现队列

Class 配合 WeakMap 实现队列

2.优先队列

3.数据结构-链表

1.数据结构-栈

ShmilyXI