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 代码、处理用户交互（用户输入、鼠标点击等）、执行和处理异步请求。
-----------磨刀不误砍柴工、加油！！！