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

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