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

  • 2019 年 10 月 3 日
  • 筆記

定場詩

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

前言

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

後記

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

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

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

胡哥有話說

VirMach 便宜 VPS

QNews

QNews