1. 队列数据结构

队列是遵循 FIFO（First In First Out，先进先出）的一组有序的项。在尾部添加元素，并从顶部移除元素。
image.png

1.1 创建队列

  • enqueue(element(s))：向队列尾部添加一个（或多个）新的项。
  • dequeue()：移除队列的第一（即排在队列最前面的）项，并返回被移除的元素。
  • front()：返回队列中第一个元素——最先被添加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与Stack类的peek方法非常类似）。
  • isEmpty()：如果队列中不包含任何元素，返回true，否则返回false。

  • size()：返回队列包含的元素个数，与数组的length属性类似。

    1.1.1 传统方式

    1. function Queue() {
    2. const items = [];
    4. this.enqueue = (element) => items.push(element);
    6. this.dequeue = () => items.shift();
    8. this.front = () => items[0];
    10. this.isEmpty = () => items.length === 0;
    12. this.size = () => items.length;
    14. this.print = () => console.log(items.toString());
    15. }

    1.1.2 ES6 Class

    1. const Queue = (function () {
    2. const items = new WeakMap();
    4. class Queue {
    5.   constructor() {
    6.     items.set(this, []);
    7.   }
    9.   enqueue(element) {
    10.     const q = items.get(this);
    11.     q.push(element);
    12.   }
    14.   dequeue() {
    15.     const q = items.get(this);
    16.     return q.shift();
    17.   }
    19.   front() {
    20.     const q = items.get(this);
    21.     return q[0];
    22.   }
    24.   isEmpty() {
    25.     const q = items.get(this);
    26.     return q.length === 0;
    27.   }
    29.   size() {
    30.     const q = items.get(this);
    31.     return q.length;
    32.   }
    34.   print() {
    35.     const q = items.get(this);
    36.     console.log(q.toString());
    37.   }
    38. }
    40. return Queue;
    41. })();

    1.2 优先队列

    和基本的队列相比，优先队列需要一个辅助类，用于包含元素的优先级信息，同时分为最小优先队列，和最大优先队列。其他方法没什么区别，只有入队列（enqueue）时要根据优先级来决定在队列中的位置。

    1. /**
    2. * 优先队列
    3. * @type {Queue}
    4. */
    5. const PriorityQueue = (function () {
    6. const items = new WeakMap();
    8. /**
    9.  * 队列元素能包含优先级信息
    10.  */
    11. class QueueElement {
    12.   constructor(element, priority) {
    13.     this.element = element;
    14.     this.priority = priority;
    15.   }
    16. }
    18. class Queue {
    19.   constructor() {
    20.     items.set(this, []);
    21.   }
    23.   // 最小优先队列（queueElement.priority < q[i].priority）
    24.   enqueue(element, priority = 0) {
    25.     if (element === undefined) {
    26.       throw new Error('参数非法');
    27.     }
    28.     const q = items.get(this);
    29.     const queueElement = new QueueElement(element, priority);
    30.     let added = false;
    31.     for (let i = 0; i < q.length; i++) {
    32.       if (queueElement.priority < q[i].priority) {
    33.         q.splice(i, 0, queueElement);
    34.         added = true;
    35.         break;
    36.       }
    37.     }
    38.     if (!added) {
    39.       q.push(queueElement);
    40.     }
    41.   }
    43.   // 最大优先队列（queueElement.priority > q[i].priority）
    44.   enqueue2(element, priority = 0) {
    45.     if (element === undefined) {
    46.       throw new Error('参数非法');
    47.     }
    48.     const q = items.get(this);
    49.     const queueElement = new QueueElement(element, priority);
    50.     let added = false;
    51.     for (let i = 0; i < q.length; i++) {
    52.       if (queueElement.priority > q[i].priority) {
    53.         q.splice(i, 0, queueElement);
    54.         added = true;
    55.         break;
    56.       }
    57.     }
    58.     if (!added) {
    59.       q.push(queueElement);
    60.     }
    61.   }
    63.   dequeue() {
    64.     const q = items.get(this);
    65.     return q.shift();
    66.   }
    68.   front() {
    69.     const q = items.get(this);
    70.     return q[0];
    71.   }
    73.   isEmpty() {
    74.     const q = items.get(this);
    75.     return q.length === 0;
    76.   }
    78.   size() {
    79.     const q = items.get(this);
    80.     return q.length;
    81.   }
    83.   print() {
    84.     const q = items.get(this);
    85.     q.forEach(item => {
    86.       console.log(`${item.element} - ${item.priority}`);
    87.     });
    88.   }
    89. }
    91. return Queue;
    92. })();

    1.3 循环队列

    ```javascript const Queue = require(‘./queue-weakMap’);

/**

  • 利用循环队列实现击鼓传花（烫手山芋）
  • 由于 JS 语言的灵活性，数组长度可以动态变化，这里的循环是指纯粹的元素滚动
  • 而像 Java 语言中的循环（环形）队列，指的是：
  • 通过数组和指针结合取余%运算，把存储队列元素的表从逻辑上看成一个环，称为循环队列，
  • 从而实现用固定长度的数组模拟队列时，可以循环利用数组的空间 *
  • @param nameList 名字列表
  • @param num 循环次数

  • @returns {} 获胜者 / function hotPotato(nameList = [], num) { const queue = new Queue();

    for (let i = 0; i < nameList.length; i++) { queue.enqueue(nameList[i]); }

    let eliminated = ‘’;

    // 最终只留一位获胜者 while (queue.size() > 1) { // 没循环滚动 num 次后，淘汰一名 for (let i = 0; i < num; i++) { queue.enqueue(queue.dequeue()); // 没停止滚动前，会重新进入队列，所以暂时不会被淘汰 } eliminated = queue.dequeue(); console.log(eliminated + ‘在游戏中被淘汰！’); }

    return queue.dequeue(); // 返回获胜者 }

const nameList = [‘a’, ‘b’, ‘c’, ‘d’, ‘e’]; const winner = hotPotato(nameList, 5); console.log(‘获胜者是：’, winner); ```

1.4 双端队列

双端队列 Deque。
双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。在计算机科学中双端队列常见应用是存储一系列的撤销操作。
当用户在软件中进行了操作时，该操作从尾部进入双端队列；
当用户点击撤销按钮时，从双端队列的尾部移除；
当队列中的操作达到预定义的一定数量后，最先存入的操作会被移除(头部移除)。
双端队列同时遵守了先进先出和后进先出的原则。
https://book.douban.com/subject/33441631
https://www.cnblogs.com/justbecoder/p/11383570.html