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

学习数据结构的 git 代码地址: https://gitee.com/zhangning187/js-data-structure-study

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;  }

只有 enqueue 方法和 dequeue 方法可以添加和移除元素，这样就确保了 Queue 类遵循先进先出原则。

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 = {};  }}

　　双端队列是一个特殊的队列，构造函数和部分方法和队列相同，isEmpty、clear、size、toString

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 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。

 

-----------磨刀不误砍柴工、加油！！！