摘要：定場(chǎng)詩(shī)馬瘦毛長(zhǎng)蹄子肥，兒子偷爹不算賊，瞎大爺娶個(gè)瞎大奶奶，老兩口過(guò)了多半輩，誰(shuí)也沒(méi)看見(jiàn)誰(shuí)前言本章為重讀學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)與算法第三版的系列文章，主要講述隊(duì)列數(shù)據(jù)結(jié)構(gòu)雙端隊(duì)列數(shù)據(jù)結(jié)構(gòu)以及隊(duì)列相關(guān)應(yīng)用。

馬瘦毛長(zhǎng)蹄子肥，兒子偷爹不算賊，瞎大爺娶個(gè)瞎大奶奶，老兩口過(guò)了多半輩，誰(shuí)也沒(méi)看見(jiàn)誰(shuí)！

本章為重讀《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-第三版》的系列文章，主要講述隊(duì)列數(shù)據(jù)結(jié)構(gòu)、雙端隊(duì)列數(shù)據(jù)結(jié)構(gòu)以及隊(duì)列相關(guān)應(yīng)用。

隊(duì)列是遵循先進(jìn)先出（FIFO）原則的一組有序的項(xiàng)。隊(duì)列在尾部添加元素，并從頂部移除元素。最新添加的元素必須排在隊(duì)列的末尾?，F(xiàn)實(shí)中常見(jiàn)的隊(duì)列就是排隊(duì)，計(jì)算機(jī)科學(xué)中，常見(jiàn)的例子是打印隊(duì)列，如文檔按順序打印，第一個(gè)發(fā)送到打印隊(duì)列的文檔優(yōu)先被打印。

/**
 * class Queue 隊(duì)列類
 * 特點(diǎn)：先進(jìn)先出
 */
class Queue {
  construcor () {
    // 存儲(chǔ)數(shù)據(jù)
    this.items = {}
    // 隊(duì)列頭部元素索引
    this.lowestCount = 0
    // 隊(duì)列尾部元素索引
    this.count = 0
  }

  /**
   * enqueue() 添加元素到隊(duì)列 - 先進(jìn)先出
   * @param {*} element 添加到隊(duì)列的元素
   */
  enqueue (elemenet) {
    this.items[this.count] = element
    this.count++
  }

  /**
   * dequeue() 移除隊(duì)列頭部元素 - 先進(jìn)先出
   * @returns {*} result 返回頭部元素
   */
  dequeue () {
    if (this.isEmpty()) {
      return undefined
    }
    let result = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return result
  }

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

  /**
   * isEmpty() 判斷隊(duì)列是否為空
   * @returns {Boolean}
   */
  isEmpty () {
    return this.count === this.lowestCount
  }

  /**
   * size() 隊(duì)列長(zhǎng)度
   * @returns {Number}
   */
  size () {
    return this.count - this.lowestCount
  }

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

  /**
   * toString() 返回隊(duì)列的字符串結(jié)構(gòu)
   * @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
  }
}

// 實(shí)例化隊(duì)列
const queue = new Queue()

// 判斷隊(duì)列是否為空
console.log(queue.isEmpty()) // true

// 向隊(duì)列中添加元素
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

以上操作示意圖

雙端隊(duì)列是一種允許我們同時(shí)從前端和后端添加和移除元素的特殊隊(duì)列。在計(jì)算機(jī)科學(xué)中雙端隊(duì)列常見(jiàn)應(yīng)用是存儲(chǔ)一系列的撤銷操作。

當(dāng)用戶在軟件中進(jìn)行了操作時(shí)，該操作從尾部進(jìn)入雙端隊(duì)列；

當(dāng)用戶點(diǎn)擊撤銷按鈕時(shí)，從雙端隊(duì)列的尾部移除；

當(dāng)隊(duì)列中的操作達(dá)到預(yù)定義的一定數(shù)量后，最先存入的操作會(huì)被移除(頭部移除)

雙端隊(duì)列同時(shí)遵守了先進(jìn)先出和后進(jìn)先出的原則

/**
 * class Deque 雙端隊(duì)列
 * 特點(diǎn)：支持先進(jìn)先出、后進(jìn)先出
 */
class Deque {
  constructor () {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  /**
   * addFront() 從頭部插入
   * @param {*} element 待插入隊(duì)首的元素
   */
  addFront (element) {
    this.lowestCount--
    this.items[this.lowestCount] = element
  }

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

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

  /**
   * removeBack() 隊(duì)尾移除元素
   * @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() 返回隊(duì)列的長(zhǎng)度
   * @returns {Number} 隊(duì)列的長(zhǎng)度
   */
  size () {
    return this.count - this.lowestCount
  }

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

  /**
   * peekFront() 獲取隊(duì)首元素
   * @returns {*}
   */
  peekFront () {
    if (this.isEmpty()) {
      return undefined
    }
    return this.items[this.lowestCount]
  }

  /**
   * peekBack() 獲取隊(duì)尾元素
   * @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

規(guī)則：

使用隊(duì)列模擬擊鼓傳花

當(dāng)執(zhí)行一定的約定次數(shù)(每次都隨機(jī)一個(gè)數(shù))時(shí)，花在誰(shuí)手里，誰(shuí)被淘汰

重復(fù)執(zhí)行游戲，直到剩下最后一人，為勝利者

/**
 * hotPotato() 模擬擊鼓傳花游戲
 * @param {Array} elementList 需傳入的參與游戲的人員列表
 * @returns {Object} 返回信息：淘汰者和勝利者
 */
function hotPotato (elementList) {
  // 實(shí)例化隊(duì)列，將元素放入隊(duì)列
  let queue = new Queue()
  elementList.forEach((value) => {
    queue.enqueue(value)
  })

  // 淘汰的人
  let elimitatedList = []

  // 開(kāi)始游戲，直到隊(duì)列中剩余1人
  while (queue.size() > 1) {
    // 為了讓游戲更加有意思，每次停止的位置進(jìn)行隨機(jī)處理
    for (let i = 0; i < Math.floor(Math.random() * 10); i++) {
      // 取出頭部第一個(gè)元素，然后執(zhí)行插入
      queue.enqueue(queue.dequeue())
    }
    // 此時(shí)擁有花的人，淘汰
    elimitatedList.push(queue.dequeue())
  }

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

let elementList = [
  "孫悟空",
  "唐僧",
  "如來(lái)佛祖",
  "玉帝",
  "王母"
]

// 調(diào)用函數(shù)，傳入elementList，同時(shí)約定第6次時(shí)，擁有花的小伙伴被淘汰...
let result = hotPotato(elementList, 6)
console.log(result)

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

console.log(`${result.winner}勝利了...`)

以上代碼運(yùn)行效果 -- 展示其中一次的執(zhí)行結(jié)果
{ elimitatedList: [ "唐僧", "王母", "孫悟空", "如來(lái)佛祖" ], winner: "玉帝" }
唐僧被淘汰了...
王母被淘汰了...
孫悟空被淘汰了...
如來(lái)佛祖被淘汰了...
玉帝勝利了...

什么是回文？

回文是正反都能讀通的單詞、詞組、數(shù)或一系列字符的序列，例如：aba、madam

那如何實(shí)現(xiàn)回文檢查器呢？

/**
 * palindromeChecker() 回文檢查器
 * @param {String} str 待檢查的字符串
 * @returns {Boolean}
 */
function palindromeChecker (str) {
  // 檢測(cè)是否是合法字符串
  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

/**
 * palindromeChecker() 回文檢查器
 * @param {String} str 待檢查的字符串
 * @returns {Boolean}
 */
function palindromeChecker (str) {
  // 檢測(cè)是否是合法字符串
  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的實(shí)現(xiàn)，請(qǐng)參考上一篇文章：[重讀《學(xué)習(xí)JavaScript數(shù)據(jù)結(jié)構(gòu)與算法-第三版》- 第4章 棧
](http://mp.weixin.qq.com/s?__b...

/**
 * palindromeChecker() 回文檢查器
 * @param {String} str 待檢查的字符串
 * @returns {Boolean}
 */
function palindromeChecker (str) {
  // 檢測(cè)是否是合法字符串
  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])
  }

  // 設(shè)置是否是回文的標(biāo)記
  let isEqual = true
  while (deque.size() > 1 && isEqual) {
    // 取出收尾進(jìn)行比較
    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

以上就是胡哥今天給大家分享的內(nèi)容，喜歡的小伙伴記得收藏、轉(zhuǎn)發(fā)、點(diǎn)擊右下角按鈕在看，推薦給更多小伙伴呦，歡迎多多留言交流...

胡哥有話說(shuō)，一個(gè)有技術(shù)，有情懷的胡哥！京東開(kāi)放平臺(tái)首席前端攻城獅。與你一起聊聊大前端，分享前端系統(tǒng)架構(gòu)，框架實(shí)現(xiàn)原理，最新最高效的技術(shù)實(shí)踐！

長(zhǎng)按掃碼關(guān)注，更帥更漂亮呦！關(guān)注胡哥有話說(shuō)公眾號(hào)，可與胡哥繼續(xù)深入交流呦！