5. 队列和双端队列

5.1 队列数据结构

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

创建队列

为了写出一个在获取元素时更高效的数据结构，我们将使用一个对象来存储我们的元素。你会发现 Queue 类和 Stack 类非常类似，只是添加和移除元素的原则不同。

class Queue {
  constructor() {
    this.count = 0; // 定义队列长度
    this.lowestCount = 0; // 定义队列中的第一个元素
    this.items = {}; // 定义一个对象来存储队列中的元素
  }
  // 向队列中添加元素，这里有一个非常重要的细节就是新的元素只能添加到队列末尾
  enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }
  // 从队列中移除元素，由于队列遵循先进先出原则，最先添加的向也是最先被移除的
  dequeue() {
    if (this.isEmpty()) {
      // 检验队列是否为空，如果为空，直接返回 undefined
      return undefined;
    }
    const result = this.items[this.lowestCount]; // 暂存队列头部的值
    delete this.items[this.lowestCount]; // 删除队列头部的元素
    this.lowestCount++; // 头部元素后移
    return result; // 返回被删除的元素
  }

  // 查询队列头部
  peek() {
    if (this.isEmpty()) {
      // 检验队列是否为空，如果为空，直接返回 undefined
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  // 检查队列是否为空
  isEmpty() {
    return this.count - this.lowestCount === 0;
  }

  // 获取队列的长度
  size() {
    return this.count - this.lowestCount;
  }

  // 清空队列
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  // 创建toString方法
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString}, ${this.items[i]}`;
    }
    return objString;
  }
}

接下来需要声明一些队列可用的方法。

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

使用 Queue 类

const queue = new Queue();
console.log(queue.isEmpty()); // 输出true

// 向队列中添加元素
queue.enqueue("John");
queue.enqueue("Jack");
console.log(queue.toString()); // John, Jack

queue.enqueue("Camila");

console.log(queue.toString()); // John, Jack, Camila
console.log(queue.size()); // 输出3
console.log(queue.isEmpty()); // 输出false
queue.dequeue(); // 移除John
queue.dequeue(); // 移除Jack
console.log(queue.toString()); // Camila

5.2 双端队列数据结构

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

双端队列在现实生活中的例子有电影院、餐厅中排队的队伍等。举个例子，一个刚买了票的人如果只是还需要再问一些简单的信息，就可以直接回到队伍的头部。另外，在队伍末尾的人如果赶时间，他可以直接离开队伍。

在计算机科学中，双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行了一个操作，该操作会被存在一个双端队列中（就像在一个栈里）。当用户点击撤销按钮时，该操作会被从双端队列中弹出，表示它被从后面移除了。在进行了预先定义的一定数量的操作后，最先进行的操作会被从双端队列的前端移除。由于双端队列同时遵守了先进先出和后进先出原则，可以说它是把队列和栈相结合的一种数据结构。

创建 Deque 类

既然双端队列是一种特殊的队列，我们可以看到其构造函数中的部分代码和队列相同，包括相同的内部属性和以下方法：isEmpty、clear、size 和 toString。

由于双端队列允许在两端添加和移除元素，还会有下面几个方法。

• addFront(element)：该方法在双端队列前端添加新的元素。
• addBack(element)：该方法在双端队列后端添加新的元素（实现方法和 Queue 类中的 enqueue 方法相同）。
• removeFront()：该方法会从双端队列前端移除第一个元素（实现方法和 Queue 类中的 dequeue 方法相同）。
• removeBack()：该方法会从双端队列后端移除第一个元素（实现方法和 Stack 类中的 pop 方法一样）。
• peekFront()：该方法返回双端队列前端的第一个元素（实现方法和 Queue 类中的 peek 方法一样）。
• peekBack()：该方法返回双端队列后端的第一个元素（实现方法和 Stack 类中的 peek 方法一样）。

class Deque {
  constructor() {
    this.count = 0; // 定义队列长度
    this.lowestCount = 0; // 定义队列中的第一个元素的序号
    this.items = {}; // 定义一个对象来存储队列中的元素
  }

  // 向双端队列的前端添加元素
  addFront(element) {
    if (this.isEmpty()) {
      // 如果双端队列是空的，在前端添加和在后端添加一样，可以直复用在后端添加元素的方法
      this.addBack(element);
    } else if (this.lowestCount > 0) {
      // 第一个元素从双端队列的前端移除（第一个元素的序号大于0），这种情况下，我们只需要将lowestCount属性减1并将新元素的值放在这个键的位置上即可。
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    } else {
      for (let i = this.count; i > 0; i--) {
        // 将现有队列中元素后移一位
        this.items[i] = this.items[i - 1];
      }
      this.count++;
      this.lowestCount = 0;
      this.items[0] = element; // 将新的元素放在队首
    }
  }
  // 向双端队列的后端添加元素
  addBack(element) {
    this.items[this.count] = element;
    this.count++;
  }
  // 从双端队列前端移除第一个元素
  removeFront() {
    if (this.isEmpty()) {
      // 检验队列是否为空，如果为空，直接返回 undefined
      return undefined;
    }
    const result = this.items[this.lowestCount]; // 暂存队列头部的值
    delete this.items[this.lowestCount]; // 删除队列头部的元素
    this.lowestCount++; // 头部元素后移
    return result; // 返回被删除的元素
  }
  // 从双端队列后端移除第一个元素
  removeBack() {
    if (this.isEmpty()) {
      return undefined; // 检验队列是否为空，如果为空，直接返回 undefined
    }
    this.count--; // count属性减1
    const result = this.items[this.count]; // 保存队尾元素的值
    delete this.items[this.count]; // 删除队尾元素
    return result; // 返回队尾元素的值
  }
  // 返回双端队列前端的第一个元素
  peekFront() {
    if (this.isEmpty()) {
      // 检验队列是否为空，如果为空，直接返回 undefined
      return undefined;
    }
    return this.items[this.lowestCount];
  }
  // 返回双端队列后端的第一个元素
  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

  // 检查队列是否为空
  isEmpty() {
    return this.count - this.lowestCount === 0;
  }

  // 获取队列的长度
  size() {
    return this.count - this.lowestCount;
  }

  // 清空队列
  clear() {
    this.items = {};
    this.count = 0;
    this.lowestCount = 0;
  }

  // 创建toString方法
  toString() {
    if (this.isEmpty()) {
      return "";
    }
    let objString = `${this.items[this.lowestCount]}`;
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      objString = `${objString}, ${this.items[i]}`;
    }
    return objString;
  }
}

使用 Deque 类

const deque = new Deque();
console.log(deque.isEmpty()); // 输出true
deque.addBack("John");
deque.addBack("Jack");
console.log(deque.toString()); // John, Jack
deque.addBack("Camila");
console.log(deque.toString()); // John, Jack, Camila
console.log(deque.size()); // 输出3
console.log(deque.isEmpty()); // 输出false
deque.removeFront(); // 移除John
console.log(deque.toString()); // Jack, Camila
deque.removeBack(); // Camila决定离开
console.log(deque.toString()); // Jack
deque.addFront("John"); // John回来询问一些信息
console.log(deque.toString()); // John, Jack

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

循环队列——击鼓传花游戏

由于队列经常被应用在计算机领域和我们的现实生活中，就出现了一些队列的修改版本，我们会在本章实现它们。这其中的一种叫作循环队列。循环队列的一个例子就是击鼓传花游戏（hot potato）。在这个游戏中，孩子们围成一个圆圈，把花尽快地传递给旁边的人。某一时刻传花停止，这个时候花在谁手里，谁就退出圆圈、结束游戏。重复这个过程，直到只剩一个孩子（胜者）。

在下面这个示例中，我们要实现一个模拟的击鼓传花游戏。

function hotPotato(elementsList, num) {
  const queue = new Queue(); // {1} 创建一个新的队列
  const elimitatedList = [];

  for (let i = 0; i < elementsList.length; i++) {
    queue.enqueue(elementsList[i]); // 将所有的名字，添加到队列中
  }

  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue()); // {3} 根据给定的数字，迭代队列，每次迭代从队列开头移除一项，将其添加到队列的末尾
    }
    elimitatedList.push(queue.dequeue()); // {4} 一旦循环结束，队首那花的那个人就被淘汰了，将其从队列中移除
  }

  return {
    eliminated: elimitatedList,
    winner: queue.dequeue(), // {5} 最后只剩下一个人的时候，这个人就是胜利者
  };
}

实现一个模拟的击鼓传花游戏，要用到本章开头实现的 Queue 类（行{1}）。我们会得到一份名单，把里面的名字全都加入队列（行{2}）。给定一个数字，然后迭代队列。从队列开头移除一项，再将其添加到队列末尾（行{3}），模拟击鼓传花（如果你把花传给了旁边的人，你被淘汰的威胁就立刻解除了）。一旦达到给定的传递次数，拿着花的那个人就被淘汰了（从队列中移除——行{4}）。最后只剩下一个人的时候，这个人就是胜者（行{5}）。

我们可以使用下面的代码来尝试 hotPotato 算法。

const names = ["John", "Jack", "Camila", "Ingrid", "Carl"];
const result = hotPotato(names, 7);
result.eliminated.forEach((name) => {
  console.log(`${name}在击鼓传花游戏中被淘汰。`);
});

console.log(`胜利者： ${result.winner}`);

以上算法的输出如下。

Camila在击鼓传花游戏中被淘汰。
Jack在击鼓传花游戏中被淘汰。
Carl在击鼓传花游戏中被淘汰。
Ingrid在击鼓传花游戏中被淘汰。
胜利者：John

下图模拟了这个输出过程。

回文检查器

下面是维基百科对回文的解释。

回文是正反都能读通的单词、词组、数或一系列字符的序列，例如 madam 或 racecar。

有不同的算法可以检查一个词组或字符串是否为回文。最简单的方式是将字符串反向排列并检查它和原字符串是否相同。如果两者相同，那么它就是一个回文。我们也可以用栈来完成，但是利用数据结构来解决这个问题的最简单方法是使用双端队列。

下面的算法使用了一个双端队列来解决问题。

    function palindromeChecker(aString) {
      if (aString === undefined || aString === null ||
        (aString ! == null && aString.length === 0)) { // {1} 检查传入的字符串是否合法，不合法直接返回 false
        return false;
      }
      const deque = new Deque(); // {2}  创建一个双端队列
      const lowerString = aString.toLocaleLowerCase().split(' ').join(''); // {3} 格式化字符串，全部转为小写字母并且移除所有的空格
      let isEqual = true;
      let firstChar, lastChar;

      for (let i = 0; i < lowerString.length; i++) { // {4} 对字符串中所有的字符执行入队操作
        deque.addBack(lowerString.charAt(i));
      }

      while (deque.size() > 1 && isEqual) { // {5} 循环结束条件：最后只剩下一个字符并且其他字符都是首位相等时，循环结束
        firstChar = deque.removeFront(); // {6} 从双端队列的前端移除一个元素
        lastChar = deque.removeBack(); // {7} 从双端队列的后端移除一个元素
        if (firstChar ! == lastChar) {
          isEqual = false; // {8} 移除的元素不相等，就不是回文字符串
        }
      }

      return isEqual;
    }

在我们开始解释算法逻辑之前，需要检查传入的字符串参数是否合法（行{1}）。如果不合法，我们返回 false。

对于这个算法，我们将使用在本章实现的 Deque 类（行{2}）。由于可能接收到同时包含大小写字母的字符串，我们会将所有字母转化为小写，同时移除所有的空格（行{3}）。如果你愿意，也可以移除所有的特殊字符，例如！、? 、-、(和)等。为了保证算法简洁，我们会跳过这部分。

然后，我们会对字符串中的所有字符执行 enqueue 操作（行{4}）。如果所有元素都在双端队列中（如果只有一个字符的话，那它肯定是回文）并且首尾字符相同的话（行{5}），我们将从前端移除一个元素（行{6}），再从后端移除一个元素（行{7}）。要使字符串为回文，移除的两个字符必须相同。如果字符不同的话，这个字符串就不是一个回文（行{8}）。

我们可以用下面的代码来测试 palindromeChecker 算法。

    console.log('a', palindromeChecker('a'));
    console.log('aa', palindromeChecker('aa'));
    console.log('kayak', palindromeChecker('kayak'));
    console.log('level', palindromeChecker('level'));
    console.log('Was it a car or a cat I saw', palindromeChecker('Was it a car
    or a cat I saw'));
    console.log('Step on no pets', palindromeChecker('Step on no pets'));

前面所有示例的输出结果都是 true。

JavaScript 任务队列

当我们在浏览器中打开新标签时，就会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务，称为事件循环。浏览器要负责多个任务，如渲染 HTML、执行 JavaScript 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。如果想更多地了解事件循环，可以访问https://jakearchibald.com/2015/tasks-microtasks-queues-and-schedules/。