JavaScript 数据结构与算法2(队列和双端队列) - 张_Ning

1、队列和双端队列

　　队列和栈非常类似，但是使用了与 后进先出 不同的原则。双端队列是一种将栈的原则和队列的原则混合在一起的数据结构。

1.1 队列数据结构

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

　　最常见的例子就是排队。排队打饭，排队买票等，计算机里面有排队打印等。

1.1.1 创建队列类

class Queue {
  constructor() {
    // 记录队列的长度，大小
    this.count = 0;
    // 记录队列的第一个元素
    this.lowestCount = 0;
    // 这里也可以使用数组，但是为了获取元素时更高效，使用对象存储元素，
    // 和 Stack 非常类似，只是添加和移除元素的原则不同
    this.items = {};
  }
}

1.1.2 向队列添加元素

  // 向队列尾部添加项
  // 这里的实现方法和 Stack 栈中的方式相同。将 count 作为items中的键对应元素作为它的值
  enqueue(element) {
    this.items[this.count] = element;
    this.count++;
  }

1.1.3 从队列移除元素

  // 移除第一项，并返回被移除的元素
  dequeue() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    // 删除最先进去的元素
    delete this.items[this.lowestCount];
    // 最先添加的元素位置，也要向后移动
    this.lowestCount++;
    return result;
  }

1.1.4 查看队列头元素

  // 返回队列中第一个元素，最先被添加，也将是最先被移除的元素，队列不做任何变动，只是取值
  peek() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

1.1.5 检查队列是否为空和获取队列长度

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

  // 队列元素个数
  size() {
    return this.count - this.lowestCount;
  }

1.1.6 清空队列和toString方法

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

  toString() {
    if (this.isEmpty()) {
      return '';
    }
    let queueString = this.items[this.lowestCount];
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      queueString += `,${this.items[i]}`;
    }
    return queueString;
  }

1.2 双端队列数据结构

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

　　双端队列生活中的例子，电影院、餐厅排队等。一个人刚买了票还想问一些问题，可以直接在队伍的最前面询问信息，另外，在队伍尾部的人不想排队了可以直接离开队伍。

　　双端队列的一个常见应用是存储一系列的撤销操作。每当用户在软件中进行一个操作，该操作会被存在一个双端队列中（就像一个栈里面）。双端队列同时遵守了先进先出和后进先出的原则，可以说它是把队列和栈相结合的一种数据结构。

1.2.1 创建 Deque 类

class Deque {
  constructor() {
    this.count = 0;
    this.lowestCount = 0;
    this.items = {};
  }
}

1.2.2 实现双端队列的方法

// 前端添加元素
  addFront(element) {
    if (this.isEmpty()) {// 空队列
      this.addBack(element);
    } else {
      this.lowestCount--;
      this.items[this.lowestCount] = element;
    }
  }

  // 后端添加元素
  addBack(element) {
    this.items[this.count] = element;
    this.count++;
  }

  // 从前端移除
  removeFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    const result = this.items[this.lowestCount];
    // 删除最先进去的元素
    delete this.items[this.lowestCount];
    // 最先添加的元素位置，也要向后移动
    this.lowestCount++;
    return result;
  }

  // 从后端移除
  removeBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    this.count--;
    const result = this.items[this.count];
    delete this.items[this.count];
    return result;
  }

  // 返回最前端的元素
  peekFront() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.lowestCount];
  }

  // 返回最后端的元素
  peekBack() {
    if (this.isEmpty()) {
      return undefined;
    }
    return this.items[this.count - 1];
  }

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

　　使用队列模拟击鼓传花游戏，使用双端队列检查一个短语是否为回文。

1.3.1 循环队列--击鼓传花游戏

　　队列可以修改为很多的不同队列，其中可以修改为一种循环队列。循环队列的一个例子就是击鼓传花游戏--多人围成一个圈，把花尽快地传递给旁边的人。某一刻传花停止，花在谁手里谁就退出，直到最后一个人为胜者。

// 击鼓传花
import {Queue} from './Queue.js';

// list: 人数 num: 传递次数
function hotPotato(list, num) {
  const queue = new Queue();
  // 淘汰的列表
  const elimitatedList = [];

  for (let i = 0; i < list.length; i++) {
    // 依次添加到队列中
    queue.enqueue(list[i]);
  }
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      // 队列开头移除一项添加到队尾，
      // 模拟击鼓传花（如果你把花传给旁边的人，你的淘汰威胁就立即解除了）
      queue.enqueue(queue.dequeue());
    }
    // 淘汰的放在数组中
    // 一旦达到传递次数，拿着花的那个人就被淘汰了
    elimitatedList.push(queue.dequeue());
  }
  return {
    eliminated: elimitatedList,
    winner: queue.dequeue()
  };
}

const names = ['zn1', 'zn2', 'zn3', 'zn4', 'zn5'];
const result = hotPotato(names, 7);
console.log(result);// zn1 为 winner

1.3.2 回文检查器

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

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

// 回文检查
function palindromeChecker(aString) {
  // 检查字符串是否合法
  if (aString === undefined || aString === null || (aString !== null && aString.length === 0)) {
    return false;
  }
  const deque = new Deque();
  // 大小写字母都转化为小写，同时移除所有空格。
  const lowerString = aString.toLocaleLowerCase().split(' ').join('');
  let isEqual = true;
  // 字符插入到双端队列中
  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString.charAt(i));
  }
  while (deque.size() > 1 && isEqual) {
    // 最前面一个是否等于最后面一个
    isEqual = deque.removeFront() === deque.removeBack();
  }
  return isEqual;
}

console.log(1111, palindromeChecker('123321'));

1.3.3 任务队列

　　当我们在浏览器中打开新标签时，就会创建一个任务队列。因为每个标签都是单线程处理所有的任务，称为事件循环。浏览器要负责多个任务，渲染HTML、执行 JavaScript 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。