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

 

———–磨刀不误砍柴工、加油!!!

标签:

商匡云商
Logo
注册新帐户
对比商品
  • 合计 (0)
对比
0
购物车