资讯专栏INFORMATION COLUMN

重读《学习JavaScript数据结构与算法-第三版》- 第5章 队列

charles_paul / 3290人阅读

摘要:定场诗马瘦毛长蹄子肥,儿子偷爹不算贼,瞎大爷娶个瞎大奶奶,老两口过了多半辈,谁也没看见谁前言本章为重读学习数据结构与算法第三版的系列文章,主要讲述队列数据结构双端队列数据结构以及队列相关应用。

定场诗
马瘦毛长蹄子肥,儿子偷爹不算贼,瞎大爷娶个瞎大奶奶,老两口过了多半辈,谁也没看见谁!
前言

本章为重读《学习JavaScript数据结构与算法-第三版》的系列文章,主要讲述队列数据结构、双端队列数据结构以及队列相关应用。

队列

队列是遵循先进先出(FIFO)原则的一组有序的项。队列在尾部添加元素,并从顶部移除元素。最新添加的元素必须排在队列的末尾。现实中常见的队列就是排队,计算机科学中,常见的例子是打印队列,如文档按顺序打印,第一个发送到打印队列的文档优先被打印。

实现队列
/**
 * class Queue 队列类
 * 特点:先进先出
 */
class Queue {
  construcor () {
    // 存储数据
    this.items = {}
    // 队列头部元素索引
    this.lowestCount = 0
    // 队列尾部元素索引
    this.count = 0
  }

  /**
   * enqueue() 添加元素到队列 - 先进先出
   * @param {*} element 添加到队列的元素
   */
  enqueue (elemenet) {
    this.items[this.count] = element
    this.count++
  }

  /**
   * dequeue() 移除队列头部元素 - 先进先出
   * @returns {*} result 返回头部元素
   */
  dequeue () {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }

  /**
   * peek() 返回队列头部元素
   * @returns {*}
   */
  peek () {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.lowestCount]
  }

  /**
   * isEmpty() 判断队列是否为空
   * @returns {Boolean}
   */
  isEmpty () {
    return this.count === this.lowestCount
  }

  /**
   * size() 队列长度
   * @returns {Number}
   */
  size () {
    return this.count - this.lowestCount
  }

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

  /**
   * toString() 返回队列的字符串结构
   * @returns {String}
   */
  toString () {
    if (this.isEmpty()) {
      return ""
    }
    let queueStr = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      queueStr = `${queueStr},${this.items[i]}`
    }
    return queueStr
  }
}
使用队列
// 实例化队列
const queue = new Queue()

// 判断队列是否为空
console.log(queue.isEmpty()) // true

// 向队列中添加元素
queue.enqueue("John")
queue.enqueue("Jack")

console.log(queue.toString()) // John,Jack

queue.enqueue("Camila")

console.log(queue.toString()) // John,Jack

console.log(queue.size()) // 3

console.log(queue.isEmpty()) // false

以上操作示意图:

console.log(queue.dequeue()) // John
console.log(queue.dequeue()) // Jack
console.log(queue.toString()) // Camila

以上操作示意图

双端队列

双端队列是一种允许我们同时从前端和后端添加和移除元素的特殊队列。在计算机科学中双端队列常见应用是存储一系列的撤销操作。

当用户在软件中进行了操作时,该操作从尾部进入双端队列;

当用户点击撤销按钮时,从双端队列的尾部移除;

当队列中的操作达到预定义的一定数量后,最先存入的操作会被移除(头部移除)

双端队列同时遵守了先进先出和后进先出的原则

实现双端队列
/**
 * class Deque 双端队列
 * 特点:支持先进先出、后进先出
 */
class Deque {
  constructor () {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  /**
   * addFront() 从头部插入
   * @param {*} element 待插入队首的元素
   */
  addFront (element) {
    this.lowestCount--
    this.items[this.lowestCount] = element
  }

  /**
   * addBack() 从尾部插入
   * @param {*} element 待插入队尾的元素
   */
  addBack (element) {
    this.items[this.count] = element
    this.count++
  }

  /**
   * removeFront() 队首移除元素
   * @returns {*}
   */
  removeFront () {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }

  /**
   * removeBack() 队尾移除元素
   * @returns {*}
   */
  removeBack () {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.count -1]
    delete this.items[this.count - 1]
    this.count--
    return result
  }

  /**
   * isEmpty() 判断是否为空
   * @returns {Boolean} 是否为空
   */
  isEmpty () {
    return this.count === this.lowestCount
  }

  /**
   * size() 返回队列的长度
   * @returns {Number} 队列的长度
   */
  size () {
    return this.count - this.lowestCount
  }

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

  /**
   * peekFront() 获取队首元素
   * @returns {*}
   */
  peekFront () {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.lowestCount]
  }

  /**
   * peekBack() 获取队尾元素
   * @returns {*}
   */
  peekBack () {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.count - 1]
  }

  /**
   * toString() 展示字符串形式
   * @returns {*}
   */
  toString () {
    if (this.isEmpty()) {
      return ""
    }
    let str = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount + 1; i < this.count; i++) {
      str = `${str},${this.items[i]}`
    }
    return str
  }
}
使用双端队列
const deque = new Deque()

console.log(deque.isEmpty()) // true

deque.addFront("宋江")
deque.addFront("晁盖")
deque.addBack("吴用")

console.log(deque.size()) // 3
console.log(deque.toString()) // 晁盖,宋江,吴用

console.log(deque.removeFront()) // 晁盖
console.log(deque.removeBack()) // 吴用

console.log(deque.toString()) // 宋江
console.log(deque.size()) // 1
实战应用 循环队列 - 模拟击鼓传花游戏

规则:

使用队列模拟击鼓传花

当执行一定的约定次数(每次都随机一个数)时,花在谁手里,谁被淘汰

重复执行游戏,直到剩下最后一人,为胜利者

/**
 * hotPotato() 模拟击鼓传花游戏
 * @param {Array} elementList 需传入的参与游戏的人员列表
 * @returns {Object} 返回信息:淘汰者和胜利者
 */
function hotPotato (elementList) {
  // 实例化队列,将元素放入队列
  let queue = new Queue()
  elementList.forEach((value) => {
    queue.enqueue(value)
  })

  // 淘汰的人
  let elimitatedList = []

  // 开始游戏,直到队列中剩余1人
  while (queue.size() > 1) {
    // 为了让游戏更加有意思,每次停止的位置进行随机处理
    for (let i = 0; i < Math.floor(Math.random() * 10); i++) {
      // 取出头部第一个元素,然后执行插入
      queue.enqueue(queue.dequeue())
    }
    // 此时拥有花的人,淘汰
    elimitatedList.push(queue.dequeue())
  }

  // 返回
  return {
    elimitatedList,
    winner: queue.dequeue()
  }
}

let elementList = [
  "孙悟空",
  "唐僧",
  "如来佛祖",
  "玉帝",
  "王母"
]

// 调用函数,传入elementList,同时约定第6次时,拥有花的小伙伴被淘汰...
let result = hotPotato(elementList, 6)
console.log(result)

result.elimitatedList.forEach((name) => {
  console.log(`${name}被淘汰了...`)
})

console.log(`${result.winner}胜利了...`)
以上代码运行效果 -- 展示其中一次的执行结果

{ elimitatedList: [ "唐僧", "王母", "孙悟空", "如来佛祖" ], winner: "玉帝" }

唐僧被淘汰了...

王母被淘汰了...

孙悟空被淘汰了...

如来佛祖被淘汰了...

玉帝胜利了...

回文检查器

什么是回文?

回文是正反都能读通的单词、词组、数或一系列字符的序列,例如:aba、madam

那如何实现回文检查器呢?

1. 使用反转排列字符串与原字符串进行比较
/**
 * palindromeChecker() 回文检查器
 * @param {String} str 待检查的字符串
 * @returns {Boolean}
 */
function palindromeChecker (str) {
  // 检测是否是合法字符串
  if (str === undefined || str === null || (str !== null && str.length === 0)) {
    return false
  }
  return str.split("").reverse().join("") === str
}

let str = "aba"
console.log(palindromeChecker(str)) // true
2. 使用数据结构-栈实现回文检查器
/**
 * palindromeChecker() 回文检查器
 * @param {String} str 待检查的字符串
 * @returns {Boolean}
 */
function palindromeChecker (str) {
  // 检测是否是合法字符串
  if (str === undefined || str === null || (str !== null && str.length === 0)) {
    return false
  }
  let stack = new Stack()
  // 分割字符串
  for (let i = 0; i < str.length; i++) {
    stack.push(str[i])
  }

  let reverseStr = ""
  while (!stack.isEmpty()) {
    reverseStr += stack.pop()
  }
  return str === reverseStr
}

let str = "aba"
console.log(palindromeChecker(str)) // true
此处栈 class Stack的实现,请参考上一篇文章:[重读《学习JavaScript数据结构与算法-第三版》- 第4章 栈
](http://mp.weixin.qq.com/s?__b...
3. 使用双端队列实现回文检查器
/**
 * palindromeChecker() 回文检查器
 * @param {String} str 待检查的字符串
 * @returns {Boolean}
 */
function palindromeChecker (str) {
  // 检测是否是合法字符串
  if (str === undefined || str === null || (str !== null && str.length === 0)) {
    return false
  }

  let deque = new Deque()

  for (let i = 0; i < str.length; i++) {
    deque.addBack(str[i])
  }

  // 设置是否是回文的标记
  let isEqual = true
  while (deque.size() > 1 && isEqual) {
    // 取出收尾进行比较
    let front = deque.peekFront()
    let back = deque.peekBack()
    
    if (front !== back) {
      isEqual = false
    }
  }

  return isEqual
}

let str = "abc"
console.log(palindromeChecker(str)) // false
str = "aba"
console.log(palindromeChecker(str)) // true
后记

以上就是胡哥今天给大家分享的内容,喜欢的小伙伴记得收藏转发、点击右下角按钮在看,推荐给更多小伙伴呦,欢迎多多留言交流...

胡哥有话说,一个有技术,有情怀的胡哥!京东开放平台首席前端攻城狮。与你一起聊聊大前端,分享前端系统架构,框架实现原理,最新最高效的技术实践!

长按扫码关注,更帅更漂亮呦!关注胡哥有话说公众号,可与胡哥继续深入交流呦!

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/110026.html

相关文章

  • 重读学习JavaScript数据结构算法-三版》- 3 数组(二)

    摘要:定场诗守法朝朝忧闷,强梁夜夜欢歌损人利己骑马骡,正值公平挨饿修桥补路瞎眼,杀人放火儿多我到西天问我佛,佛说我也没辙前言读学习数据结构与算法第章数组,本小节将继续为各位小伙伴分享数组的相关知识数组的新功能。 定场诗 守法朝朝忧闷,强梁夜夜欢歌; 损人利己骑马骡,正值公平挨饿; 修桥补路瞎眼,杀人放火儿多; 我到西天问我佛,佛说:我也没辙! 前言 读《学习JavaScript数据结构与算法...

    William_Sang 评论0 收藏0
  • 重读学习JavaScript数据结构算法-三版》-2 ECMAScriptTypeScr

    摘要:第二种接口的概念和面向对象编程相关接口视为一份合约,在合约里可以定义这份合约的类或接口的行为接口告诉类,它需要实现一个叫做的方法,并且该方法接收一个参数。 定场诗 八月中秋白露,路上行人凄凉; 小桥流水桂花香,日夜千思万想。 心中不得宁静,清早览罢文章, 十年寒苦在书房,方显才高志广。 前言 洛伊安妮·格罗纳女士所著的《学习JavaScript数据结构与算法》第三版于2019年的5月份...

    TZLLOG 评论0 收藏0
  • 重读学习JavaScript数据结构算法-三版》- 3 数组(一)

    摘要:此处应该有掌声前言读学习数据结构与算法第章数组,本节将为各位小伙伴分享数组的相关知识概念创建方式常见方法以及数组的新功能。数组数组是最简单的内存数据结构,用于存储一系列同一种数据类型的值。 定场诗 大将生来胆气豪,腰横秋水雁翎刀。 风吹鼍鼓山河动,电闪旌旗日月高。 天上麒麟原有种,穴中蝼蚁岂能逃。 太平待诏归来日,朕与先生解战袍。 此处应该有掌声... 前言 读《学习JavaScrip...

    iKcamp 评论0 收藏0
  • 重读学习JavaScript数据结构算法-三版》- 6 链表(一)

    摘要:前言本章为重读学习数据结构与算法的系列文章,该章节主要讲述数据结构链表,以及实现链表的过程和原理。链表,是存储有序的元素集合。链表中的元素在内存中并不是连续放置的,每个元素由一个存储自身的元素节点和一个指向下一个元素的引用指针或链接组成。 定场诗 伤情最是晚凉天,憔悴厮人不堪言; 邀酒摧肠三杯醉.寻香惊梦五更寒。 钗头凤斜卿有泪,荼蘼花了我无缘; 小楼寂寞新雨月.也难如钩也难圆。 前言...

    lmxdawn 评论0 收藏0
  • JavaScript书籍测评

    摘要:前言今天和大家一起聊聊的推荐书籍,每一本都是精选,做前端开发的朋友们如果没读过,可以尝试一下。如果怕麻烦,也可以关注晓舟报告,发送获取书籍,四个字,就可以得到电子书的提取码。 前言 今天和大家一起聊聊JavaScript的推荐书籍,每一本都是精选,做前端开发的朋友们如果没读过,可以尝试一下。下面给大家简单介绍了书的内容,还有读书的方法,希望可以帮大家提升读书效率。 一、《JavaScr...

    X1nFLY 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<