重讀《學習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
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類