队列也是一种受限的线性结构，只允许在表的前端删除，在表的后端插入。

创建队列

虽然可以基于数组来创建队列，但是基于对象的队列效率更高，因为我们选择基于对象来创建队列。
队列需要一个lowetCount来跟踪现在最小的队列序号，且count不应该随着元素删除而减小，不然在插入元素时无法得知最后一个序号的大小。

  1. class Queue {
  2.   constructor() {
  3.     this.item = {};
  4.     this.count = 0;
  5.     this.lowestCount = 1;
  6.   }
  8.   enqueue(ele) {
  9.     this.count += 1;
  10.     this.item[this.count] = ele;
  11.   }
  13.   dequeue() {
  14.     if(this.isEmpty()) {
  15.       return undefined;
  16.     }
  17.     const res = this.item[this.lowestCount];
  18.     delete this.item[this.lowestCount];
  19.     this.lowestCount += 1;
  20.     return res;
  21.   }
  23.   peek() {
  24.     if(this.isEmpty()) {
  25.       return undefined;
  26.     }
  27.     return this.item[this.lowestCount];
  28.   }
  30.   isEmpty() {
  31.     return this.size() === 0;
  32.   }
  34.   size() {
  35.     return this.count + 1 - this.lowestCount;
  36.   }
  38.   toString() {
  39.     if(this.isEmpty()) {
  40.       return '';
  41.     }
  42.     let str = '';
  43.     for(const k in this.item) {
  44.       str = str?`${str},${this.item[k]}`:this.item[k];
  45.     }
  46.     return str;
  47.   }
  48. }
  49. const queue = new Queue();
  50. console.log(queue.isEmpty()); // 输出true
  51. queue.enqueue('John'); 
  52. queue.enqueue('Jack'); 
  53. console.log(queue.toString()); // John,Jack
  54. queue.enqueue('Camila');
  56. console.log(queue.toString()); // John, Jack, Camila 
  57. console.log(queue.size()); // 输出3 
  58. console.log(queue.isEmpty()); // 输出false 
  59. queue.dequeue(); // 移除John
  60. queue.dequeue(); // 移除Jack 
  61. console.log(queue.toString()); // Camila

双端队列

前后均可添加或者删除。
操作方法，addFront(element)、addBack(element)、removeFront``()、removeBack()、peekFront()、peekBack()。

击鼓传花问题

核心是将队列的第一个人丢到队列末尾去。

  1. function hotPotato(names, number) {
  2.   const queue = new Queue();
  3.   let outNames = [];
  4.   names.forEach((item) => {
  5.     queue.enqueue(item);
  6.   });
  7.   while (queue.size() > 1) {
  8.     for (let i = 0; i < number; i++) {
  9.       queue.enqueue(queue.dequeue());
  10.     }
  11.     outNames.push(queue.dequeue());
  12.   }
  13.   return {
  14.     winner: queue.dequeue(),
  15.     outNames: outNames,
  16.   };
  17. }
  18. const names = ["John", "Jack", "Camila", "Ingrid", "Carl"];
  19. const result = hotPotato(names, 7);
  20. console.log(result);
  21. // { winner: 'John', outNames: [ 'Camila', 'Jack', 'Carl', 'Ingrid' ] }
  22. // 在我们的写法中，每次淘汰的是第八个人。

回文检查器

核心是使用双端队列，取出队列队首和队尾的值进行比较。