# 学习 JavaScript 数据结构与算法(第三版) 笔记

原书名为 Learning JavaScript Data Structures and Algorithms, Thrid Edition。作者 Loiane Groner(罗伊安妮·格罗纳),翻译:吴双、邓钢、孙晓博等。

这是一本用 JavaScript/TypeScript 介绍数据结构与算法的书,比较适合前端开发人员。书中的示例代码比较全,JS/TS 都有,而且还有单元测试。示例代码地址:PacktPublishing/Learning-JavaScript-Data-Structures-and-Algorithms-Third-Edition | Github (opens new window)

# 第 1~3 章 JS/TS简介、数组基础

前三章比较基础,对于有 JS/TS 基础的同学,粗略的看看即可。相关内容之前有做笔记

在数组开头插入元素 unshift() 简单实现

Array.prototype.insertFirstPosition = function (value) {
  for (let i = this.length; i >= 0; i--) {
    this[i] = this[i - 1]
  }
  this[0] = value
  return this.length
}

在数组开头删除元素 shift() 简单实现

Array.prototype.deleteFirstPosition = function () {
  let lastIndex = this.length - 1
  let firstValue = this[0]
  for (let i = 0; i < lastIndex; i++) {
    this[i] = this[i + 1]
  }
  this.length = lastIndex
  return firstValue
}

# 第 4 章 栈(Stack)

Stack [stæk]

第三章介绍了最常用的数据结构 - 数组,本章会介绍栈数据结构。栈是一种遵循 LIFO(last in first out) 后进先出原则的有序集合,类似于一摞书或者餐厅里叠放的盘子。

  • 实现一个基于数组的栈
  • 实现一个基于对象的栈
  • 用栈解决问题

# 实现一个基于数组的栈

创建一个 Stack 类,用于实现栈,通过数组来实现栈。需要实现的方法、属性如下

  • push() 添加一个或多个元素到栈顶
  • pop() 移除栈顶的元素,同时返回被删除的元素
  • peek() 返回栈顶的元素,不对栈做任何修改
  • isEmpty() 返回布尔值,栈里是否没有任何元素
  • clear() 移除栈里的所有元素
  • size() 返回栈里元素个数,和 length 类似
  • length 返回栈里元素个数
class StackArray {
  constructor() {
    this.items = []
  }
  push(...args) {
    this.items.push(...args)
    return this.items.length
  }
  pop() {
    return this.items.pop()
  }
  peek() {
    return this.items[this.length - 1]
  }
  isEmpty() {
    return this.items.length === 0
  }
  clear() {
    this.items = []
  }
  size() {
    return this.items.length
  }
  get length() {
    return this.items.length
  }
  toString() {
    return this.items.join(',')
  }
}

测试 demo

let stack = new StackArray()
stack.push(1) // 1 [1]
stack.push('a', 'b', 'c') // 4 [1, 'a', 'b', 'c']
stack.length // 4
stack.size() // 4
stack.pop() // "c"
stack.toString() // "1,a,b"
stack.peek() // "b"
stack.toString() // "1,a,b"
stack.isEmpty() // false
stack.clear()
stack.isEmpty() // true

以上是手动测试的 demo,我们可以使用 Mocha 来写单元测试。

// test/1-stack-array.spec.js 
const StackArray = require('../src/1-stack-array')
const expect = require('chai').expect
let stack = null

describe('StackArray Test', () => {
  beforeEach(() => {
    stack = new StackArray()
  })

  it('empty test', () => {
    expect(stack.isEmpty()).to.equal(true)
    expect(stack.size()).to.equal(0)
  })

  it('push()/size()/toString() test', () => {
    stack.push('a')
    expect(stack.isEmpty()).to.equal(false)
    expect(stack.size()).to.equal(1)
    stack.push('b')
    expect(stack.size()).to.equal(2)
    stack.push('c')
    expect(stack.size()).to.equal(3)
    stack.push('d', 'e', 'f')
    expect(stack.length).to.equal(6)
    expect(stack.toString()).to.equal('a,b,c,d,e,f')
  })

  it('pop()/length test', () => {
    stack.push('a', 'b', 'c', 'd')
    expect(stack.pop()).to.equal('d')
    expect(stack.length).to.equal(3)
    expect(stack.pop()).to.equal('c')
    expect(stack.length).to.equal(2)
    expect(stack.pop()).to.equal('b')
    expect(stack.length).to.equal(1)
    expect(stack.pop()).to.equal('a')
    expect(stack.length).to.equal(0)
    expect(stack.pop()).to.equal(undefined)
    expect(stack.length).to.equal(0)
  })

  it('peek() test', () => {
    stack.push('a', 'b', 'c', 'd')
    expect(stack.peek()).to.equal('d')
    expect(stack.length).to.equal(4)
    stack.pop()
    stack.pop()
    expect(stack.peek()).to.equal('b')
  })

  it('clear()/isEmpty() test', () => {
    stack.push('a', 'b')
    expect(stack.length).to.equal(2)
    expect(stack.isEmpty()).to.equal(false)
    stack.clear()
    expect(stack.length).to.equal(0)
    expect(stack.isEmpty()).to.equal(true)
  })
})

运行 mocha test/1-stack-array.spec.js 测试结果如下图,完整 demo 参见:1-stack-array.spec.js - Github (opens new window)

mocha_test_pass.png

# 实现一个基于对象的栈

实现栈的最简单方式是用数组来存储其元素。但它有以下缺点

  • 使用数组时,大部分方法时间复杂度是 O(n),需要迭代整个数组直到找到对应的元素
  • 数组是一个有序集合,为了保证元素排列有序,会占用更多空间

使用对象来存储栈元素,也可以保证 LIFO 原则,下面来看看基于对象的栈实现

class Stack {
  constructor() {
    this.count = 0
    this.items = {}
  }
  // 向栈中插入元素
  push(element) {
    this.items[this.count] = element
    this.count++
  }
  isEmpty() {
    return this.count === 0
  }
  size() {
    return this.count
  }
  get length() {
    return this.count
  }
  // 从栈中弹出元素
  pop() {
    if (this.isEmpty()) {
      return undefined
    }
    this.count--
    const result = this.items[this.count]
    delete this.items[this.count]
    return result
  }
  peek() {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.count - 1]
  }
  clear() {
    this.items = {}
    this.count = 0
    // 或者
    // while(!this.isEmpty()) {
    //   this.pop()
    // }
  }
  toString() {
    if (this.isEmpty()) {
      return ''
    } else {
      let i = 0,
        len = this.count,
        result = ''
      while (i < len) {
        result += this.items[i]
        if (i !== len - 1) {
          result += ','
        }
        i++
      }
      return result
    }
  }
}

以上方法中,除了 toString() 方法,其他方法复杂度均为 O(1),以上代码单元测试地址:2-stack-obj.spec.js - Github (opens new window)

# 用栈解决问题

栈可以用于存储访问过的任务或路径、撤销操作。还可以处理进制转换、平衡括号、汉诺塔问题。

# 十进制转二进制

要将十进制数转化成二进制,可以将 10 进制数除 2(二进制满 2 进 1)取余, 然后 Math.floor(除 2 的结果) 继续取余,直到 Math.floor(除 2) 的结果为 0。将所有余数组合起来就是对于的二进制

10 
10 / 20,Math.floor(10 / 2) => 5
 5 / 21,Math.floor(5 / 2) => 2
 2 / 20,Math.floor(2 / 2) => 1
 1 / 21,Math.ceil(1 / 2) => 0
// 余数 1010 就是 10 的二进制

我们将取余的数 push 到栈中,最后逐个出栈即可将 10 进制转换为二进制

// src/3-stack-to-binary.js
const Stack = require('./2-stack-obj')
function decimalToBinary(num) {
  let stack = new Stack()
  let result = ''
  while (num) {
    stack.push(num % 2)
    num = Math.floor(num / 2)
  }
  while (!stack.isEmpty()) {
    result += stack.pop()
  }
  return result || '0'
}

module.exports = decimalToBinary

单元测试

// test/3-stack-to-binary.spec.js
const expect = require('chai').expect
const decimalToBinary = require('../src/3-stack-to-binary')

describe('DecimalToBinary Test', () => {
  it('10进制转2进制', () => {
    expect(decimalToBinary(0)).to.equal('0')
    expect(decimalToBinary(1)).to.equal('1')
    expect(decimalToBinary(2)).to.equal('10')
    expect(decimalToBinary(5)).to.equal('101')
    expect(decimalToBinary(10)).to.equal('1010')
    expect(decimalToBinary(15)).to.equal('1111')
    expect(decimalToBinary(233)).to.equal('11101001')
    expect(decimalToBinary(1000)).to.equal('1111101000')
  })
})

# 十进制转其他进制

除了将 10 进制转换为 2 进制外,还可以将 10 进制转换为 2 - 36 的任意进制

// src/4-stack-decimal-converter.js
const Stack = require('./2-stack-obj')
function decimalConverter(num, base) {
  let stack = new Stack()
  let result = ''
  const digits = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ'
  if (base < 2 || base > 36) {
    return ''
  }
  while (num) {
    stack.push(num % base)
    num = Math.floor(num / base)
  }
  while (!stack.isEmpty()) {
    result += digits[stack.pop()]
  }
  return result || '0'
}

module.exports = decimalConverter

单元测试

// src/4-stack-decimal-converter.spec.js
const expect = require('chai').expect
const decimalConverter = require('../src/4-stack-decimal-converter')

describe('decimalConverter Test', () => {
  it('10进制转其他进制', () => {
    expect(decimalConverter(0, 2)).to.equal('0')
    expect(decimalConverter(1, 2)).to.equal('1')
    expect(decimalConverter(1, 37)).to.equal('')
    expect(decimalConverter(100345, 2)).to.equal('11000011111111001')
    expect(decimalConverter(100345, 8)).to.equal('303771')
    expect(decimalConverter(100345, 16)).to.equal('187F9')
    expect(decimalConverter(100345, 35)).to.equal('2BW0')
  })
})

# 平衡圆括号

Balanced parentheses means that each opening symbol has acorresponding closing symbol and the pairs of parentheses are properly nested.Consider the following correctly balanced strings of parentheses:

平衡括号的意思是,每个左括号一定对应着一个右括号,括号内又套着括号。看下面这些个括号组成的平衡表达式:

(()()()())
(((())))
(()((())()))

Compare those with the following, which are not balanced:

对比下面这些不平衡的括号:

((((((())
()))
(()()(()

The ability to differentiate between parentheses that are correctlybalanced and those that are unbalanced is an important part of recognizing manyprogramming language structures.

正确地区分平衡和不平衡括号,对很多编程语言来说,都是重要的内容。

The challenge then is to write an algorithm that will read a stringof parentheses from left to right and decide whether the symbols are balanced.

现在的问题就是,写一个算法,读入一串括号字符串,并判断它们是否平衡。

可以使用栈来解决这个问题,遇到左括号 "(" 就将它 push 到栈中,遇到右括号 ")" 就将栈中的内容 pop() 一次。如果出现 ")" 时栈是空的,则缺少 "("。如果字符串到末尾后栈中还有内容,则缺少 ")"。

// src/5-stack-balance-parentheses.js
const Stack = require('./2-stack-obj')
function isBalanceParentheses(str) {
  let stack = new Stack()
  if (typeof str !== 'string') {
    return false
  }
  const len = str.length
  let i = 0
  while (i < len) {
    if (str[i] === '(') {
      stack.push('(')
    }
    if (str[i] === ')') {
      if (stack.isEmpty()) {
        return false
      }
      stack.pop()
    }
    i++
  }
  return stack.isEmpty()
}

module.exports = isBalanceParentheses

单元测试

// test/5-stack-balance-parentheses.spec.js
const expect = require('chai').expect
const isBalanceParentheses = require('../src/5-stack-balance-parentheses')

describe('BalanceParentheses Test', () => {
  it('平衡括号测试', () => {
    expect(isBalanceParentheses(0)).to.be.false
    expect(isBalanceParentheses(')')).to.be.false
    expect(isBalanceParentheses('(')).to.be.false
    expect(isBalanceParentheses('()')).to.be.true
    expect(isBalanceParentheses('(()()()())')).to.be.true
    expect(isBalanceParentheses('(((())))')).to.be.true
    expect(isBalanceParentheses('(()((())()))')).to.be.true
    expect(isBalanceParentheses('((((((())')).to.be.false
    expect(isBalanceParentheses('()))')).to.be.false
    expect(isBalanceParentheses('(()()(()')).to.be.false
  })
})

参考:python数据结构与算法 5栈的应用之圆括号平衡_量变到质变-CSDN博客 (opens new window)

# 汉诺塔

有三根相邻的柱子,标号为 A, B, C。A 柱子上从下到上按金字塔状叠放着 n 个不同大小的圆盘,要把所有盘子移动到柱子 B 上,一次只能移动一个圆盘,且大圆盘不能在小圆盘上面,求移动步骤和次数

hanoi.jpeg

有两种解法,一种是递归,一种是栈。先来看递归的实现

  • 将 n - 1 个圆盘从 A 移动到 C(借助 B)
  • 将第 n 个圆盘从 A 移动到 B
  • 将 n - 1 个圆盘从 C 移动到 B(借助 A)

移动次数为 2 的 n 次方 - 1

let count = 0
function move(number, from, to, depend) {
  console.log(`将第 ${number} 号圆盘从 ${from} 移动到 ${to}`)
  count++
}
// 将 n 个圆盘从 a 移动到 b 借助 c
function hanoi(n, a, b, c) {
  if (n === 0) {
    return
  }
  hanoi(n - 1, a, c, b) // 将 n -1 个圆盘从 a 移动到 c,借助 b
  move(n, a, b) // 将第 n 个圆盘从 a 移动到 b
  hanoi(n - 1, c, b, a) // 将 n -1 个圆盘从 c 移动到 b,借助 a
}
hanoi(3, 'A', 'B', 'C')
console.log('移动次数', count)
// 将第 1 号圆盘从 A 移动到 B
// 将第 2 号圆盘从 A 移动到 C
// 将第 1 号圆盘从 B 移动到 C
// 将第 3 号圆盘从 A 移动到 B
// 将第 1 号圆盘从 C 移动到 A
// 将第 2 号圆盘从 C 移动到 B
// 将第 1 号圆盘从 A 移动到 B
// 移动次数 7

重构上面的例子,使用一个函数搞定

function hanoiRecursion(n, a, b, c, moves = []) {
  if (n === 0) {
    return moves
  }
  hanoiRecursion(n - 1, a, c, b, moves) // 将 n -1 个圆盘从 a 移动到 c,借助 b
  moves.push([a, b]) // move(n, a, b) // 将第 n 个圆盘从 a 移动到 b
  hanoiRecursion(n - 1, c, b, a, moves) // 将 n -1 个圆盘从 c 移动到 b,借助 a
  return moves
}
let moves = hanoiRecursion(3, 'A', 'B', 'C')
console.log('移动路径', moves)
console.log('移动次数', moves.length)
// // 移动路径
// // [
// //  ["A", "B"], ["A", "C"], ["B", "C"], ["A", "B"],
// //  ["C", "A"], ["C", "B"], ["A", "B"]
// // ]
// // 移动次数 7

参考:汉诺塔的图解递归算法 - Dmego - 博客园 (opens new window)

使用栈其实也需要使用递归,只是我们通过 3 个栈,表示三个圆柱,可以实时看对应的效果

const Stack = require('./2-stack-obj')
function hanoi(n, source, dest, depend, a, b, c, moves = []) {
  if (n === 0) {
    return
  }
  hanoi(n - 1, source, depend, dest, a, c, b, moves) // 将 n - 1 个圆盘从 source 移动到 depend
  moves.push([a, b])
  dest.push(source.pop()) // 将第 n 个圆盘从 source 移动到 dest
  hanoi(n - 1, depend, dest, source, c, b, a, moves) // 将 n - 1 个圆盘从 depend 移动到 dest
}
function hanoiStack(n) {
  let source = new Stack()
  let dest = new Stack()
  let depend = new Stack()
  let count = n
  while (count) {
    source.push(count--)
  }
  let moves = []
  console.log('source: ', source)
  hanoi(n, source, dest, depend, 'A', 'B', 'C', moves)
  console.log('source: ', source)
  console.log('dest: ', dest)
  console.log('depend: ', depend)
  return moves
}
console.log(hanoiStack(3))
// source:  Stack { count: 3, items: { '0': 3, '1': 2, '2': 1 } }
// source:  Stack { count: 0, items: {} }
// dest:  Stack { count: 3, items: { '0': 3, '1': 2, '2': 1 } }
// depend:  Stack { count: 0, items: {} }
// [
//   [ 'A', 'B' ],
//   [ 'A', 'C' ],
//   [ 'B', 'C' ],
//   [ 'A', 'B' ],
//   [ 'C', 'A' ],
//   [ 'C', 'B' ],
//   [ 'A', 'B' ]
// ]

单元测试

// test/6-stack-hanoi.spec.js
const expect = require('chai').expect
let { hanoiStack, hanoiRecursion } = require('../src/6-stack-hanoi')

describe('Hanoi Test', () => {
  it('递归实现测试', () => {
    for (let i = 1; i <= 10; i++) {
      expect(hanoiRecursion(i, 'a', 'b', 'c').length).to.equal(2 ** i - 1)
    }
  })
  it('栈+递归实现测试', () => {
    for (let i = 1; i <= 10; i++) {
      expect(hanoiStack(i).length).to.equal(2 ** i - 1)
    }
  })
})

# 第 5 章 队列和双端队列

队列和栈非常相似,栈是 LIFO(last in first out)后进先出。队列是遵循先进先出(FIFO,first in first out)原则的一组有序的集合。最常见的队列的例子就是排队。排在第一位的会先接受服务。本章内容包括

  • 队列数据结构
  • 双端队列数据结构
  • 用队列和双端队列来解决问题

# 队列数据结构

我们使用 Queue 类表示队列,队列可以使用数组和对象来实现,这里为了在获取元素时更高效,使用对象实现

class Queue {
  constructor() {
    this.count = 0
    this.lowestCount = 0 // 标记队列的最开始的一位
    this.items = {}
  }
}

enqueue [ɪn'kjuː] 入队,排队; dequeue [di'kju:] 出列、出队

队列需要实现如下方法

  • enqueue(element(s)) 向队列尾部添加一个或多个新的项
  • dequeue() 移除队列中的第一个元素(排在队列最前面的项),并返回该元素
  • peek() 返回队列中第一个元素(最先被添加的元素)队列不做任何变动
  • isEmpty() 队列是否为空
  • size() 返回队列包含的元素个数
  • clear() 清空队列
  • toString() 转为字符串
class Queue {
  constructor() {
    this.count = 0
    this.lowestCount = 0
    this.items = {}
  }
  // 入队
  enqueue(element) {
    this.items[this.count] = element
    this.count++
  }
  // 出列
  dequeue() {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++ // 标记队列的最开始的一位
    return result
  }
  isEmpty() {
    return this.count - this.lowestCount === 0
    // return this.size() === 0
  }
  peek() {
    return this.isEmpty() ? undefined : this.items[this.lowestCount]
  }
  size() {
    return this.count - this.lowestCount
  }
  clear() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }
  toString() {
    if (this.isEmpty()) {
      return ''
    }
    let result = ''
    for (let i = this.lowestCount; i < this.count; i++) {
      result += this.items[i]
      if (i !== this.count - 1) {
        result += ','
      }
    }
    return result
  }
}

module.exports = Queue

单元测试

// test/7-queue-obj.spec.js
const expect = require('chai').expect
const Queue = require('../src/7-queue-obj')
let queue = ''

describe('Queue Test', () => {
  beforeEach(() => {
    queue = new Queue()
  })

  it('enqueue()/size()/toString() test', () => {
    queue.enqueue('a')
    expect(queue.size()).to.equal(1)
    queue.enqueue('b')
    expect(queue.size()).to.equal(2)
    queue.enqueue('c')
    expect(queue.size()).to.equal(3)
    expect(queue.toString()).to.equal('a,b,c')
  })

  it('dequeue()/peek()', () => {
    queue.enqueue('a')
    queue.enqueue('b')
    queue.enqueue('c')
    expect(queue.dequeue()).to.equal('a')
    expect(queue.peek()).to.equal('b')
    expect(queue.size()).to.equal(2)
    expect(queue.dequeue()).to.equal('b')
    expect(queue.peek()).to.equal('c')
    expect(queue.size()).to.equal(1)
    expect(queue.dequeue()).to.equal('c')
    expect(queue.size()).to.equal(0)
    expect(queue.dequeue()).to.equal(undefined)
  })

  it('clear()/isEmpty()', () => {
    queue.enqueue('a')
    queue.enqueue('b')
    queue.enqueue('c')
    expect(queue.isEmpty()).to.be.false
    queue.clear()
    expect(queue.peek()).to.be.undefined
    expect(queue.isEmpty()).to.be.true
  })
})

# 双端队列数据结构

双端队列(deque [dek],或称为 double-ended queue)是一种允许同时从前端和后端添加和移除元素的特殊队列,比如在电影院、餐厅排队的队伍中,一个刚买票的人需要在询问一些简单信息,可以直接回到队伍的头部,另外再队伍末尾的人,如果赶时间,可以离开队伍

在计算机科学中,双端队列的一个常见应用是存储一系列的撤销操作,将每个操作依次保存在双端队列中,当需要撤销时,最后的操作会从双端队列中移除。另外,当记录的操作数达到上限时,最先的操作会从双端队列前端移除。

由于双端队列同时遵循先进先出、后进先出原则,因此它是队列和栈相结合的一种数据结构。

创建一个 Deque 类

class Deque {
  constructor() {
    this.count = 0
    this.lowestCount = 0
    this.items = {}
  }
}

它支持如下方法:

  • addFront(element) 在双端队列前端添加新元素
  • addBack(element) 在双端队列后端添加新元素
  • removeFront() 从双端队列的前端移除第一个元素
  • removeBack() 从双端队列的后端移第一个元素
  • peekFront() 返回双端队列前端的第一个元素
  • peekBack() 返回双端队列后端的第一个元素
  • isEmpty() 判断是否为空
  • clear() 清空
  • size() 返回队列长度
  • toString() 转字符串
// 8-deque-obj.js
class Deque {
  constructor() {
    this.count = 0
    this.lowestCount = 0
    this.items = {}
  }
  addFront(element) {
    if (this.isEmpty()) {
      this.addBack(element)
    } else if (this.lowestCount > 0) {
      // 如果之前队列从前端移出过元素
      this.lowestCount--
      this.items[this.lowestCount] = element
    } else {
      // 如果队列没有从前端移出过元素  this.lowestCount = 0
      // 新进来的需要替换原来的 lowestCount = 0 的元素
      // 新增 this.items[this.count] 且把每个值向后移动一位
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1]
      }
      this.count++
      this.items[this.lowestCount] = element
    }
  }
  addBack(element) {
    this.items[this.count] = element
    this.count++
  }
  removeFront() {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }
  removeBack() {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.count - 1]
    delete this.items[this.count - 1]
    this.count--
    return result
  }
  peekFront() {
    return this.isEmpty() ? undefined : this.items[this.lowestCount]
  }
  peekBack() {
    return this.isEmpty() ? undefined : this.items[this.count - 1]
  }
  isEmpty() {
    return this.size() === 0
  }
  clear() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }
  size() {
    return this.count - this.lowestCount
  }
  toString() {
    if (this.isEmpty()) {
      return ''
    }
    let result = ''
    for (let i = this.lowestCount; i < this.count; i++) {
      result += this.items[i]
      if (i !== this.count - 1) {
        result += ','
      }
    }
    return result
  }
}

module.exports = Deque

单元测试

// 8-deque-obj.spec.js
const expect = require('chai').expect
const Deque = require('../src/8-deque-obj')
let deque = ''

describe('Deque Test', () => {
  beforeEach(() => {
    deque = new Deque()
  })

  it('基础功能测试', () => {
    deque.addFront('a') // a
    deque.addBack('b') // a b
    deque.addFront('c') // c a b
    deque.addFront('d') // d c a b
    deque.addBack('e') // d c a b e
    expect(deque.toString()).to.equal('d,c,a,b,e')
    expect(deque.peekBack()).to.equal('e')
    expect(deque.peekFront()).to.equal('d')
    expect(deque.removeBack()).to.equal('e') // d c a b
    expect(deque.removeFront()).to.equal('d') // c a b
    deque.addFront('f') // f c a b
    expect(deque.peekBack()).to.equal('b')
    expect(deque.peekFront()).to.equal('f')
    expect(deque.toString()).to.equal('f,c,a,b')
  })

  it('clear()/size()/isEmpty()', () => {
    deque.addBack('a')
    deque.addBack('b')
    deque.addBack('c')
    expect(deque.size()).to.equal(3)
    expect(deque.isEmpty()).to.be.false
    deque.clear()
    expect(deque.size()).to.equal(0)
    expect(deque.isEmpty()).to.be.true
  })
})

# 用队列和双端队列来解决问题

使用队列模拟击鼓传花游戏,使用双端队列检测是否是回文字符串

# 循环队列 - 击鼓传花游戏

hot potato 烫手山芋 potato [pəˈteɪtəʊ] n. [作物] 土豆

循环队列是队列中的一种,击鼓传花(hot potato)游戏就是其中的例子。在这个游戏中,孩子们围成一个圆圈,把花尽快的传递给旁边的人,某一时刻传花停止,这个时候花在谁手里,谁就退出圆圈,重复这个过程,直到只剩下一个孩子,即为胜者。

使用队列,不停的将出列(dequeue)的元素入列(enqueue),这样就模拟了一个循环队列。循环到某个次数后,淘汰(dequeue)一个再继续,直到只有一个为止。

const Queue = require('./7-queue-obj')

/**
 * 进行击鼓传花游戏,每循环 num 次时踢出一个人
 * @param {*} elementList 名单 ['张三', '李四', '王五']
 * @param {*} num 每循环多少次踢出去一个人
 */
function hotPotato(elementList, num) {
  const queue = new Queue()
  const eliminateList = [] // 淘汰列表 [ɪˈlɪmɪneɪt]
  // 将名单中的人加入队列
  elementList.forEach((item) => queue.enqueue(item))
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      queue.enqueue(queue.dequeue())
    }
    // 传递 num 次后踢出一个人
    eliminateList.push(queue.dequeue())
  }
  return {
    eliminateList: eliminateList,
    winner: queue.dequeue(),
  }
}

module.exports = hotPotato

单元测试

// test/9-queue-hot-patato.spec.js
const expect = require('chai').expect
const hotPotato = require('../src/9-queue-hot-patato')

describe('hotPotato Test', () => {
  it('击鼓传花游戏测试', () => {
    let names = ['张三', '李四', '王五', '赵六', '陈七']
    let { eliminateList, winner } = hotPotato(names, 7)
    let expectList = ['王五', '李四', '陈七', '赵六']
    expect(eliminateList).to.deep.equal(expectList)
    expect(winner).to.equal('张三')
  })
})

整个过程

// 初始值  '张三', '李四', '王五', '赵六', '陈七'
// 开始游戏
0 '李四' '王五' '赵六' '陈七' '张三'
1 '王五' '赵六' '陈七' '张三' '李四'
2 '赵六' '陈七' '张三' '李四' '王五'
3 '陈七' '张三' '李四' '王五' '赵六'
4 '张三' '李四' '王五' '赵六' '陈七'
5 '李四' '王五' '赵六' '陈七' '张三'
6 '王五' '赵六' '陈七' '张三' '李四'
淘汰 '王五'
0 '陈七' '张三' '李四' '赵六'
1 '张三' '李四' '赵六' '陈七'
2 '李四' '赵六' '陈七' '张三'
3 '赵六' '陈七' '张三' '李四'
4 '陈七' '张三' '李四' '赵六'
5 '张三' '李四' '赵六' '陈七'
6 '李四' '赵六' '陈七' '张三'
淘汰 '李四'
0 '陈七' '张三' '赵六'
1 '张三' '赵六' '陈七'
2 '赵六' '陈七' '张三'
3 '陈七' '张三' '赵六'
4 '张三' '赵六' '陈七'
5 '赵六' '陈七' '张三'
6 '陈七' '张三' '赵六'
淘汰 '陈七'
0 '赵六' '张三'
1 '张三' '赵六'
2 '赵六' '张三'
3 '张三' '赵六'
4 '赵六' '张三'
5 '张三' '赵六'
6 '赵六' '张三'
淘汰 '赵六'
winner '张三'

# 回文检查器(palindrome checker)

palindrome [ˈpalɪndrəʊm] 回文 是正反都能读通的单词、词组、数或一系列字符的序列,例如 madam 或 racecar

有不同的算法可以检查一个词组或字符串是否为回文

  • 将字符串反向排列并检查它和原字符串是否相同
  • 也可以用栈来完成,push 后,再 pop 出来,比较是否相同
  • 利用数据结构来解决这个问题最简单的方式是使用双端队列,通过不断比较 deque.removeFront() 是否等于 deque.removeBack(),即可判断是否是回文
const Deque = require('./8-deque-obj')
const Stack = require('../src/2-stack-obj')

// 字符串方式
function palindromeChecker(str) {
  let reverseStr = str.split('').reverse().join('')
  // return arr.join('') === str
  // 比较之前,消除空格、大小写影响
  function clear(src) {
    src = src.split(' ').join('').toLowerCase()
    return src
  }
  return clear(reverseStr) === clear(str)
}

// 栈方式
function palindromeChecker(str) {
  let stack = new Stack()
  let result = ''
  // 比较之前,消除空格、大小写影响
  function clear(src) {
    src = src.split(' ').join('').toLowerCase()
    return src
  }
  str = clear(str)
  for (let i = 0, len = str.length; i < len; i++) {
    stack.push(str[i])
  }
  while (!stack.isEmpty()) {
    result += stack.pop()
  }
  return str === result
}

// 双端队列方式
function palindromeChecker(str) {
  let deque = new Deque()
  let result = ''
  // 比较之前,消除空格、大小写影响
  function clear(src) {
    src = src.split(' ').join('').toLowerCase()
    return src
  }
  str = clear(str)
  for (let i = 0, len = str.length; i < len; i++) {
    deque.addBack(str[i])
  }
  while (deque.size() > 1) {
    if (deque.removeFront() !== deque.removeBack()) {
      return false
    }
  }
  return true
}

module.exports = palindromeChecker

单元测试

const expect = require('chai').expect
const palindromeChecker = require('../src/a-deque-palindrome')

describe('palindrome Test', () => {
  it('回文测试', () => {
    expect(palindromeChecker('ak')).to.be.false
    expect(palindromeChecker('akkac')).to.be.false
    expect(palindromeChecker('a')).to.be.true
    expect(palindromeChecker('aa')).to.be.true
    expect(palindromeChecker('kayak')).to.be.true
    expect(palindromeChecker('level')).to.be.true
    expect(palindromeChecker('madam')).to.be.true
    expect(palindromeChecker('racecar')).to.be.true
    expect(palindromeChecker('Was it a Car or a cat I saw')).to.be.true
    expect(palindromeChecker('Step on no pets')).to.be.true
  })
})

# JavaScript 任务队列/事件循环

当我们在浏览器中打开新标签时,会创建一个任务队列。这是因为每个标签都是单线程处理所有的任务,称为事件循环。详情参考:Tasks, microtasks, queues and schedules - JakeArchibald.com (opens new window)

除了比较好理解的宏任务与微任务外,还有 JS 调用栈概念,主要是 UI 事件相关的细节

  • 如果是用户点击 UI 触发的事件,事件分派(dispatch)后,JS 调用栈仅有一个事件分派。执行完该事件的微任务队列后,事件冒泡,这才开始执行对应事件处理函数。
  • 如果是 JS 触发 xx.click() 事件,冒泡事件会同步分派,JS 调用栈会有两个事件回调等待执行。
上次更新: 12/30/2020, 4:30:40 PM