重讀《學習JavaScript數據結構與算法-第三版》- 第5章隊列

charles_paul 發布于2019-08-26 14:05 / 3317人閱讀

摘要：定場詩馬瘦毛長蹄子肥，兒子偷爹不算賊，瞎大爺娶個瞎大奶奶，老兩口過了多半輩，誰也沒看見誰前言本章為重讀學習數據結構與算法第三版的系列文章，主要講述隊列數據結構雙端隊列數據結構以及隊列相關應用。

定場詩

馬瘦毛長蹄子肥，兒子偷爹不算賊，瞎大爺娶個瞎大奶奶，老兩口過了多半輩，誰也沒看見誰！

前言

本章為重讀《學習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

后記

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

胡哥有話說，一個有技術，有情懷的胡哥！京東開放平臺首席前端攻城獅。與你一起聊聊大前端，分享前端系統架構，框架實現原理，最新最高效的技術實踐！

長按掃碼關注，更帥更漂亮呦！關注胡哥有話說公眾號，可與胡哥繼續深入交流呦！

GPU云服務器云服務器 javascript高級程序設計第三版匯編語言第三版人工智能第三版 python基礎教程第三版

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/110026.html

重讀《學習JavaScript數據結構與算法-第三版》- 第3章數組（二）

摘要：定場詩守法朝朝憂悶，強梁夜夜歡歌損人利己騎馬騾，正值公平挨餓修橋補路瞎眼，殺人放火兒多我到西天問我佛，佛說我也沒轍前言讀學習數據結構與算法第章數組，本小節將繼續為各位小伙伴分享數組的相關知識數組的新功能。定場詩守法朝朝憂悶，強梁夜夜歡歌；損人利己騎馬騾，正值公平挨餓；修橋補路瞎眼，殺人放火兒多；我到西天問我佛，佛說：我也沒轍！前言讀《學習JavaScript數據結構與算法...

William_Sang 2019-08-26 14:01 評論0 收藏0
重讀《學習JavaScript數據結構與算法-第三版》-第2章 ECMAScript與TypeScr

摘要：第二種接口的概念和面向對象編程相關接口視為一份合約，在合約里可以定義這份合約的類或接口的行為接口告訴類，它需要實現一個叫做的方法，并且該方法接收一個參數。定場詩八月中秋白露，路上行人凄涼；小橋流水桂花香，日夜千思萬想。心中不得寧靜，清早覽罷文章，十年寒苦在書房，方顯才高志廣。前言洛伊安妮·格羅納女士所著的《學習JavaScript數據結構與算法》第三版于2019年的5月份...

TZLLOG 2019-08-26 10:44 評論0 收藏0
重讀《學習JavaScript數據結構與算法-第三版》- 第3章數組（一）

摘要：此處應該有掌聲前言讀學習數據結構與算法第章數組，本節將為各位小伙伴分享數組的相關知識概念創建方式常見方法以及數組的新功能。數組數組是最簡單的內存數據結構，用于存儲一系列同一種數據類型的值。定場詩大將生來膽氣豪，腰橫秋水雁翎刀。風吹鼉鼓山河動，電閃旌旗日月高。天上麒麟原有種，穴中螻蟻豈能逃。太平待詔歸來日，朕與先生解戰袍。此處應該有掌聲... 前言讀《學習JavaScrip...

iKcamp 2019-08-26 10:46 評論0 收藏0
重讀《學習JavaScript數據結構與算法-第三版》- 第6章鏈表（一）

摘要：前言本章為重讀學習數據結構與算法的系列文章，該章節主要講述數據結構鏈表，以及實現鏈表的過程和原理。鏈表，是存儲有序的元素集合。鏈表中的元素在內存中并不是連續放置的，每個元素由一個存儲自身的元素節點和一個指向下一個元素的引用指針或鏈接組成。定場詩傷情最是晚涼天，憔悴廝人不堪言；邀酒摧腸三杯醉.尋香驚夢五更寒。釵頭鳳斜卿有淚，荼蘼花了我無緣；小樓寂寞新雨月.也難如鉤也難圓。前言...

lmxdawn 2019-08-26 11:00 評論0 收藏0
JavaScript書籍測評

摘要：前言今天和大家一起聊聊的推薦書籍，每一本都是精選，做前端開發的朋友們如果沒讀過，可以嘗試一下。如果怕麻煩，也可以關注曉舟報告，發送獲取書籍，四個字，就可以得到電子書的提取碼。前言今天和大家一起聊聊JavaScript的推薦書籍，每一本都是精選，做前端開發的朋友們如果沒讀過，可以嘗試一下。下面給大家簡單介紹了書的內容，還有讀書的方法，希望可以幫大家提升讀書效率。一、《JavaScr...

X1nFLY 2019-08-21 17:44 評論0 收藏0