队列数据结构

队列是遵循先进先出（FIFO，先来先服务）原则的一组有序项。队列在尾部添加新元素，并从顶部移除元素。最新添加的元素必须排在队列的末尾。

生活中队列的例子：排队，打印队列（文档）。

创建 Queue 类

Queue 类和 Stack 类非常相似，只是添加元素和移除元素的原则不同。

  • 向队列添加元素
  • 从队列移除元素
  • 查看队列头元素
  • 检查队列是否为空
  • 获取队列的长度
  • 清空队列
  • 创建 toString 方法
  1. /**
  2.  * 创建队列
  3.  */
  4. class Queue {
  5.   constructor() {
  6.     this.count = 0;
  7.     this.lowestCount = 0;
  8.     this.items = {};
  9.   }
  11.   // 向队列尾部添加一个（或多个）元素
  12.   enqueue(element) {
  13.     this.items[this.count] = element;
  14.     this.count++;
  15.   }
  17.   // 移除队列的第一个元素，并返回被移除的元素
  18.   dequeue() {
  19.     if (this.isEmpty()) {
  20.       return undefined;
  21.     }
  22.     const result = this.items[this.lowestCount];
  23.     delete this.items[this.lowestCount];
  24.     this.lowestCount++;
  25.     return result;
  26.   }
  28.   // 返回队列中的第一个元素，不对队列做任何修改
  29.   peek() {
  30.     if (this.isEmpty()) {
  31.       return undefined;
  32.     }
  33.     return this.items[this.lowestCount];
  34.   }
  36.   // 如果队列中没有元素就返回 true，否则返回 false
  37.   isEmpty() {
  38.     return this.count - this.lowestCount === 0;
  39.     // return this.size();
  40.   }
  42.   // 返回队列的元素个数
  43.   size() {
  44.     return this.count - this.lowestCount;
  45.   }
  47.   // 清空队列
  48.   clear() {
  49.     this.items = {};
  50.     this.count = 0;
  51.     this.lowestCount = 0;
  52.   }
  54.   // toString 方法
  55.   toString() {
  56.     if (this.isEmpty()) {
  57.       return '';
  58.     }
  59.     let objString = `${this.items[this.lowestCount]}`;
  60.     for (let i = this.lowestCount + 1; i < this.count; i++) {
  61.       objString = `${objString}, ${this.items[i]}`;
  62.     }
  63.     return objString;
  64.   }
  66. }

使用 Queue 类

  1. /**
  2.  * 使用 Queue 类
  3.  */
  4. const queue = new Queue();
  5. console.log(queue.isEmpty());   // true
  6. queue.enqueue('John');
  7. queue.enqueue('Jack');
  8. console.log(queue.toString());  // John, Jack
  9. console.log(queue.size());      // 2
  10. console.log(queue.isEmpty());   // false
  11. queue.dequeue();
  12. console.log(queue.peek());      // Jack

双端队列数据结构

双端队列（Deque，double-ended queue）是一种允许我们同时从前端和后端添加和移除元素的特殊队列。

在计算机科学中，双端队列的一个常见应用是存储一些列的撤销操作。每当用户在软件中进行了一个操作，改操作会被存储在一个双端队列中。每当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预定义的一定数量的操作后，最先进行的操作会被双端队列的前端移除。

创建 Deque 类

  1. /**
  2.  * 创建双端队列（double-ended queue）
  3.  */
  4. class Deque {
  5.   constructor() {
  6.     this.count = 0;
  7.     this.lowestCount = 0;
  8.     this.items = {};
  9.   }
  11.   // 在双端队列最前端添加新的元素
  12.   addFront(element) {
  13.     if (this.isEmpty()) {
  14.       this.addBack(element);
  15.     } else if (this.lowestCount > 0) {
  16.       this.lowestCount--;
  17.       this.items[this.lowestCount] = element;
  18.     } else {
  19.       for (let i = this.count; i > 0; i--) {
  20.         this.items[i] = this.items[i - 1];
  21.       }
  22.       this.count++;
  23.       this.lowestCount = 0;
  24.       this.items[0] = element;
  25.     }
  26.   }
  28.   // 在双端队列后端添加新的元素
  29.   addBack(element) {
  30.     this.items[this.count] = element;
  31.     this.count++;
  32.   }
  34.   // 从双端队列前端移除第一个元素，并返回被移除的元素
  35.   removeFront() {
  36.     if (this.isEmpty()) {
  37.       return undefined;
  38.     }
  39.     const result = this.items[this.lowestCount];
  40.     delete this.items[this.lowestCount];
  41.     this.lowestCount++;
  42.     return result;
  43.   }
  45.   // 从双端队列后端移除第一个元素，并返回被移除的元素
  46.   removeBack() {
  47.     if (this.isEmpty()) {
  48.       return undefined;
  49.     }
  50.     this.count--;
  51.     const result = this.items[this.count];
  52.     delete this.items[this.count];
  53.     return result;
  54.   }
  56.   // 返回双端队列前端的第一个元素，不对队列做任何修改
  57.   peekFront() {
  58.     if (this.isEmpty()) {
  59.       return undefined;
  60.     }
  61.     return this.items[this.lowestCount];
  62.   }
  64.   // 返回双端队列后端的第一个元素，不对队列做任何修改
  65.   peekBack() {
  66.     if (this.isEmpty()) {
  67.       return undefined;
  68.     }
  69.     return this.items[this.count - 1];
  70.   }
  72.   // 如果队列中没有元素就返回 true，否则返回 false
  73.   isEmpty() {
  74.     return this.count - this.lowestCount === 0;
  75.     // return this.size();
  76.   }
  78.   // 返回队列的元素个数
  79.   size() {
  80.     return this.count - this.lowestCount;
  81.   }
  83.   // 清空队列
  84.   clear() {
  85.     this.items = {};
  86.     this.count = 0;
  87.     this.lowestCount = 0;
  88.   }
  90.   // toString 方法
  91.   toString() {
  92.     if (this.isEmpty()) {
  93.       return '';
  94.     }
  95.     let objString = `${this.items[this.lowestCount]}`;
  96.     for (let i = this.lowestCount + 1; i < this.count; i++) {
  97.       objString = `${objString}, ${this.items[i]}`;
  98.     }
  99.     return objString;
  100.   }
  102. }

使用 Deque 类

  1. /**
  2.  * 使用 Deque 类
  3.  */
  4. const deque = new Deque();
  5. console.log(deque.isEmpty());   // true
  6. deque.addBack('John');
  7. deque.addBack('Jack');
  8. deque.addFront('Camila');
  9. console.log(deque.toString());  // Camila, John, Jack
  10. console.log(deque.size());      // 3
  11. console.log(deque.isEmpty());   // false
  12. deque.removeFront();
  13. console.log(deque.toString());  // John, Jack
  14. console.log(deque.peekFront()); // John
  15. deque.removeBack();
  16. console.log(deque.peekBack());  // John
  17. deque.clear();

使用队列和双端队列来解决问题

击鼓传花游戏

击鼓传花游戏：

  • 孩子们围城一个圆圈，把花尽快地传递给傍边的人。
  • 某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈、结束游戏。
  • 重复这个过程，直到只剩一个孩子（胜者）。

使用队列

  1. function hotPotato(elementList, num) {
  2.   const queue = new Queue();
  3.   const elimitatedList = [];
  5.   for (let i = 0; i < elementList.length; i++) {
  6.     queue.enqueue(elementList[i]);
  7.   }
  9.   while (queue.size() > 1) {
  10.     for (let i = 0; i < num; i++) {
  11.       queue.enqueue(queue.dequeue());
  12.     }
  13.     elimitatedList.push(queue.dequeue());
  14.   }
  16.    return {
  17.      eliminated: elimitatedList,
  18.      winner: queue.dequeue()
  19.    };
  20. }
  22. const names = ['John', 'Jack', 'Camila', 'Ingrid', 'Carl'];
  23. const result = hotPotato(names, 7);
  24. result.eliminated.forEach(name => {
  25.   console.log(`${name}在击鼓传花游戏中被淘汰`);
  26. })
  28. console.log(`胜利者：${result.winner}`);
  29. /*
  30. Camila在击鼓传花游戏中被淘汰
  31. Jack在击鼓传花游戏中被淘汰
  32. Carl在击鼓传花游戏中被淘汰
  33. Ingrid在击鼓传花游戏中被淘汰
  34. 胜利者：John
  35. */

回文检查器

回文检查器：

  • 回文是正反都能读通的单词、词组、数或一系列字符的序列，例如：madam 或 racecar。
  • 最简单的检查方式：将字符串反向排列并检查它和原字符串是否相同。

使用双端队列

  1. function palindromeChecker(aString) {
  2.   if (aString === undefined || aString === null || (aString !== null && aString.length === 0)) {
  3.     return false;
  4.   }
  6.   const deque = new Deque();
  7.   const lowerString = aString.toLocaleLowerCase().split(' ').join('');
  8.   let isEqual = true;
  9.   let firstChar;
  10.   let lastChar;
  12.   for (let i = 0; i < lowerString.length; i++) {
  13.     deque.addBack(lowerString.charAt(i));
  14.   }
  16.   while (deque.size() > 1 && isEqual) {
  17.     firstChar = deque.removeFront();
  18.     lastChar  = deque.removeBack();
  19.     if (firstChar !== lastChar) {
  20.       isEqual = false;
  21.     }
  22.   }
  24.   return isEqual;
  25. }
  27. console.log('a', palindromeChecker('a'));                   // a true
  28. console.log('level', palindromeChecker('level'));           // level true
  29. console.log('JavaScript', palindromeChecker('JavaScript')); // JavaScript false

JavaScript 任务队列

当我们在浏览器中打开新的标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，称为事件循环。

浏览器要负责多个任务，如渲染 HTML、执行 JavaScript 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。

更多地了解事件循环