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

来源:https://www.cnblogs.com/justbecoder/archive/2019/08/20/11383570.html
-Advertisement-
Play Games

定場詩 前言 本章為重讀《學習JavaScript數據結構與演算法 第三版》的系列文章，主要講述隊列數據結構、雙端隊列數據結構以及隊列相關應用。 隊列 隊列是遵循 先進先出（FIFO） 原則的一組有序的項。隊列在尾部添加元素，並從頂部移除元素。最新添加的元素必須排在隊列的末尾。現實中常見的隊列就是排隊 ...


定場詩

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

前言

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

後記

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

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

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

胡哥有話說


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • element-ui表單驗證無效解決
    最近在項目中遇到了一個需求，需要動態增減表單元素，同時給新增的表單元素增加校驗規則。 element-ui官網給出瞭解決方案：點擊新增按鈕時，向迴圈渲染的數組中push新的對象，數據驅動視圖，通過增加數據的方式來增加新的dom元素；同樣的，通過刪除迴圈遍歷的數據來達到刪除dom的效果。 但是，校驗規 ...
  • 關於盒子的水平垂直居中幾種方案
    HTML CSS 第一種 第二種 第三種 ...
  • JS實現簡單的圖片透明度迴圈變化（漸變）
    找了好多，都是由100到0就結束了，到頭來自己魔改，以下就是源碼。 div中加入img，js添加函數，完事（調用），取名後面加個1是為了避免衝突 ...
  • js去重
    var arr=[2,8,5,0,5,2,6,7,2]; //es6 function uniqueEs6(arr){ var newArr = new Set(arr) ; return [...newArr] } //indexOf function unique(arr){ var newAr ...
  • display屬性
    display屬性規定元素應該生成的框的類型,用的最多的就是display:block;顯示 display:none;隱藏。 ...
  • whistle手機調試工具使用簡單教程
    npm全局安裝 全局啟動 啟動之後，輸入127.0.0.1:8899 就可以訪問到whistle調試界面了： 我們主要常用幾個功能： 1、mock本地數據映射，即手機請求線上某個介面的時候做本地映射，直接請求本地json數據 2、查看console列印信息，對於windows系統的電腦來說還是很有用 ...
  • js創建對象的三種方式
    如何遍歷這個對象的屬性和值呢？用for in 迴圈 註意，key只是屬性，obj[key] 才是值 ...
  • DOM之節點操作
    DOM提供了很多實用的API，這些API讓我們可以輕鬆的訪問HTML文檔。所謂API（應用程式介面），簡單來說，就是讓我們可以直接使用它訪問程式的一些屬性或方法，而不用瞭解程式內部的運作過程和原理。 前面我們已經瞭解了DOM把HTML文檔解析為節點樹，實際上HTML節點樹只是整個DOM樹的一個分支， ...
一周排行
    -Advertisement-
    Play Games
  • GoF之工廠模式
    GoF之工廠模式 @目錄GoF之工廠模式每博一文案1. 簡單說明“23種設計模式”1.2 介紹工廠模式的三種形態1.3 簡單工廠模式（靜態工廠模式）1.3.1 簡單工廠模式的優缺點:1.4 工廠方法模式1.4.1 工廠方法模式的優缺點:1.5 抽象工廠模式1.6 抽象工廠模式的優缺點：2. 總結:3 ...
  • dotnet C# 簡單的追加文件夾到 ZipArchive 壓縮文件的方法
    新改進提供的Taurus Rpc 功能，可以簡化微服務間的調用，同時可以不用再手動輸出模塊名稱，或調用路徑，包括負載均衡，這一切，由框架實現並提供了。新的Taurus Rpc 功能，將使得服務間的調用，更加輕鬆、簡約、高效。 ...
  • Elasticsearch 系列（六）- ES數據同步和ES集群
    本章將和大家分享ES的數據同步方案和ES集群相關知識。廢話不多說，下麵我們直接進入主題。 一、ES數據同步 1、數據同步問題 Elasticsearch中的酒店數據來自於mysql資料庫，因此mysql數據發生改變時，Elasticsearch也必須跟著改變，這個就是Elasticsearch與my ...
  • 自動化測試數據生成：Asp.Net Core單元測試利器AutoFixture詳解
    引言 在我們之前的文章中介紹過使用Bogus生成模擬測試數據，今天來講解一下功能更加強大自動生成測試數據的工具的庫"AutoFixture"。 什麼是AutoFixture? AutoFixture 是一個針對 .NET 的開源庫，旨在最大程度地減少單元測試中的“安排（Arrange）”階段，以提高 ...
  • .NET Emit 入門教程：第七部分：實戰項目1：將 DbDataReader 轉實體
    經過前面幾個部分學習，相信學過的同學已經能夠掌握 .NET Emit 這種中間語言，並能使得它來編寫一些應用，以提高程式的性能。隨著 IL 指令篇的結束，本系列也已經接近尾聲，在這接近結束的最後，會提供幾個可供直接使用的示例，以供大伙分析或使用在項目中。 ...
  • Windows下綁定線程到指定的CPU核心
    當從不同來源導入Excel數據時，可能存在重覆的記錄。為了確保數據的準確性，通常需要刪除這些重覆的行。手動查找並刪除可能會非常耗費時間，而通過編程腳本則可以實現在短時間內處理大量數據。本文將提供一個使用C# 快速查找並刪除Excel重覆項的免費解決方案。 以下是實現步驟： 1. 首先安裝免費.NET ...
  • mORMot 1.18 第07章 簡單的讀寫操作
    C++ 異常處理 C++ 異常處理機制允許程式在運行時處理錯誤或意外情況。它提供了捕獲和處理錯誤的一種結構化方式，使程式更加健壯和可靠。 異常處理的基本概念： 異常: 程式在運行時發生的錯誤或意外情況。 拋出異常: 使用 throw 關鍵字將異常傳遞給調用堆棧。 捕獲異常: 使用 try-catch ...
  • mORMot 1.18 第06章 概念
    優秀且經驗豐富的Java開發人員的特征之一是對API的廣泛瞭解，包括JDK和第三方庫。 我花了很多時間來學習API，尤其是在閱讀了Effective Java 3rd Edition之後 ，Joshua Bloch建議在Java 3rd Edition中使用現有的API進行開發，而不是為常見的東西編 ...
  • php 開發規範
    框架 · 使用laravel框架，原因：tp的框架路由和orm沒有laravel好用 · 使用強制路由，方便介面多時，分多版本，分文件夾等操作 介面 · 介面開發註意欄位類型，欄位是int，查詢成功失敗都要返回int（對接java等強類型語言方便） · 查詢介面用GET、其他用POST 代碼 · 所 ...
  • 2024 年 4 月 28 日 周日 晴 熱（1253 字）
    正文 下午找企業的人去鎮上做貸後。 車上聽同事跟那個司機對罵，火星子都快出來了。司機跟那同事更熟一些，連我在內一共就三個人，同事那一手指桑罵槐給我都聽愣了。司機也是老社會人了，馬上聽出來了，為那個無辜的企業經辦人辯護，實際上是為自己辯護。 “這個事情你不能怪企業。”“但他們總不能讓銀行的人全權負責， ...
所有分類