文档章节

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

胡哥有话说
 胡哥有话说
发布于 08/20 16:14
字数 1887
阅读 19
收藏 0

定场诗

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

前言

本章为重读《学习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

以上操作示意图 操作示意图

双端队列

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

  1. 当用户在软件中进行了操作时,该操作从尾部进入双端队列;
  2. 当用户点击撤销按钮时,从双端队列的尾部移除;
  3. 当队列中的操作达到预定义的一定数量后,最先存入的操作会被移除(头部移除)

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

实现双端队列

/**
 * 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

实战应用

循环队列 - 模拟击鼓传花游戏

规则:

  1. 使用队列模拟击鼓传花
  2. 当执行一定的约定次数(每次都随机一个数)时,花在谁手里,谁被淘汰
  3. 重复执行游戏,直到剩下最后一人,为胜利者
/**
 * 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章 栈

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

后记

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

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

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

胡哥有话说

© 著作权归作者所有

胡哥有话说
粉丝 0
博文 9
码字总数 15247
作品 0
东城
私信 提问
重读《学习JavaScript数据结构与算法-第三版》- 第5章 队列

定场诗 前言 本章为重读《学习JavaScript数据结构与算法-第三版》的系列文章,主要讲述队列数据结构、双端队列数据结构以及队列相关应用。 队列 队列是遵循先进先出(FIFO)原则的一组有序的...

胡哥有话说
08/20
0
0
分享51本关于JavaScript方面的学习书籍(免费下载)

分享51本关于JavaScript方面的学习书籍(免费下载) 1、JavaScript面向对象15分钟教程 2、原型、作用域、闭包的完整解释 3、Javascript面向对象特性实现(封装、继承、接口) 4、JavaScript面向...

邓剑彬
2012/12/02
1K
12
重读《学习JavaScript数据结构与算法-第三版》-第2章 ECMAScript与TypeScript概述

定场诗 八月中秋白露,路上行人凄凉; 小桥流水桂花香,日夜千思万想。 心中不得宁静,清早览罢文章, 十年寒苦在书房,方显才高志广。 前言 洛伊安妮·格罗纳女士所著的《学习JavaScript数据...

胡哥有话说
08/12
0
0
开源书籍-JavaScript 编程精解

《JavaScript 编程精解》(Eloquent JavaScript)第三版,是由马尔奇·哈弗贝克(Marlin Haverbeke)JavaScript程序员编写的JS入门书籍,Marlin Haverbeke通晓多种编程语言,在Web开发方面积累...

marsdream
2018/06/04
0
0
用js来实现那些数据结构及算法—目录

  首先,有一点要声明,下面所有文章的所有内容的代码,都不是我一个人独立完成的,它们来自于一本叫做《学习JavaScript数据结构和算法》(第二版),人民邮电出版社出版的这本书。github代...

zaking
2018/05/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Docker常用命令小记

除了基本的<font color="blue">docker pull</font>、<font color="blue">docker image</font>、<font color="blue">docker ps</font>,还有一些命令及参数也很重要,在此记录下来避免遗忘。 ......

程序员欣宸
昨天
4
0
MAT使用-jvm内存溢出问题分析定位

1.MAT简介: MAT 全称 Eclipse Memory Analysis Tools 是一个分析 Java堆数据的专业工具,可以计算出内存中对象的实例数量、占用空间大小、引用关系等,看看是谁阻止了垃圾收集器的回收工作,...

xiaomin0322
昨天
4
0
内网和外网之间的通信(端口映射原理)

首先解释一下“内网”与“外网”的概念: 内网:即所说的局域网,比如学校的局域网,局域网内每台计算机的IP地址在本局域网内具有互异性,是不可重复的。但两个局域网内的内网IP可以有相同的...

Jack088
昨天
5
0
3.深入jvm内核-原理、诊断与优化-4. GC算法和种类

一、GC算法和种类 GC的概念 GC算法 引用计数法 标记清除 标记压缩 复制算法 可触及性 Stop-The-World GC的对象是堆空间和永久区 引用计数法 老牌垃圾回收算法 通过引用计算来回收垃圾 使用者...

hexiaoming123
昨天
4
0
MySQL中的哈希索引

Memory中的哈希索引 哈希索引是基于哈希表实现的,只有精确匹配索引所有列的查询才有效。对于每一行数据,存储引擎都会对所有的索引列计算一个哈希码,哈希码是一个较小的值,并且不同键值的...

我的眼里只有眼屎
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部