欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

JS中隊(duì)列和雙端隊(duì)列實(shí)現(xiàn)及應(yīng)用詳解

 更新時(shí)間：2020年09月29日 08:33:48   作者：任重道遠(yuǎn)  
這篇文章主要介紹了JS中隊(duì)列和雙端隊(duì)列實(shí)現(xiàn)及應(yīng)用,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

隊(duì)列

  • 隊(duì)列
  • 雙端隊(duì)列數(shù)據(jù)結(jié)構(gòu)
  • 應(yīng)用
    • 用擊鼓傳花游戲模擬循環(huán)隊(duì)列
    • 用雙端對(duì)列檢查一個(gè)詞是否構(gòu)成回文
    • 生成 1 到 n 的二進(jìn)制數(shù)

隊(duì)列和雙端隊(duì)列

隊(duì)列遵循先進(jìn)后出(FIFO, 也稱(chēng)為先來(lái)先服務(wù)) 原則的. 日常有很多這樣場(chǎng)景: 排隊(duì)購(gòu)票、銀行排隊(duì)等.
由對(duì)列的特性,銀行排隊(duì)為例, 隊(duì)列應(yīng)該包含如下基本操作:

  • 加入隊(duì)列(取號(hào)) enqueue
  • 從隊(duì)列中移除(辦理業(yè)務(wù)離開(kāi)) dequeue
  • 當(dāng)前排隊(duì)號(hào)碼(呼叫下一個(gè)人) peek
  • 當(dāng)前隊(duì)列長(zhǎng)度(當(dāng)前排隊(duì)人數(shù)) size
  • 判斷隊(duì)列是不是空 isEmpty
class Queue {
  constructor() {
    // 隊(duì)列長(zhǎng)度, 類(lèi)數(shù)組 length
    this.count = 0
    // 隊(duì)列中所有項(xiàng)
    this.items = {}
    // 記錄對(duì)列頭, 類(lèi)數(shù)組 index
    this.lowestCount = 0
  }

  enqueue(ele) {
    this.items[this.count++] = ele
  }

  dequeue() {
    if (this.isEnpty()) {
      return undefined
    }
    const ele = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return ele
  }

  peek() {
    if (this.isEnpty()) {
      return
    }
    return this.items[this.lowestCount]
  }

  size() {
    /**
    * 當(dāng)隊(duì)列為非空時(shí):
    * 1. count 是長(zhǎng)度
    * 2. lowestCount 是下標(biāo)
    * 兩者關(guān)系應(yīng)該 lowestCount = count - 1
    */
    return this.count - this.lowestCount
  }

  isEnpty() {
    return this.size() == 0
  }

  clear() {
    this.items = {}
    this.lowestCount = 0
    this.count = 0
  }

  toString() {
    if (this.isEnpty()) {
      return ''
    }
    let objString = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount + 1; i < this.count; i++) {
    objString = `${objString}, ${this.items[i]}`
    }
    return objString
  }

}

雙端隊(duì)列(deque 或 double-ended queue)

什么是雙端隊(duì)列?

允許從前端(front)和后端(rear)添加元素, 遵循的原則先進(jìn)先出或后進(jìn)先出.
雙端隊(duì)列可以理解為就是棧(后進(jìn)先出)和隊(duì)列(先進(jìn)先出)的一種結(jié)合體. 既然是結(jié)合那么相應(yīng)的操作也支持隊(duì)列，棧的操作. 下面我們定義一個(gè)Deque

  • addFront
  • removeFront
  • addBack
  • removeBack
  • clear
  • isEmpty
  • peekFront
  • prekBack
  • size
  • toString
  • class Deque {
  constructor() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  addFront(ele) {
    if (this.isEmpty()) {
      this.items[this.count] = ele
    } else if (this.lowestCount > 0) {
      this.lowestCount -= 1
      this.items[this.lowestCount] = ele
    } else {
      for (let i = this.count; i > 0; i--) {
        this.items[i] = this.items[i - 1]
      }
      this.items[0] = ele
    }
      this.count++
      return ele
    }

  removeFront() {
    if (this.isEmpty()) {
      return
    }
    const delEle = this.items[this.lowestCount]
    delete this.items[this.lowestCount]
    this.lowestCount++
    return delEle
  }

  addBack(ele) {
    this.items[this.count] = ele
    this.count++
  }

  removeBack() {
    if (this.isEmpty()) {
      return
    }

    const delEle = this.items[this.count - 1]
    delete this.items[this.count - 1]
    this.count--
    return delEle
  }

  peekFront() {
    if (this.isEmpty()) {
      return
    }
    return this.items[this.lowestCount]
  }

  peekBack() {
    if (this.isEmpty()) {
      return
    }
    return this.items[this.count - 1]
  }

  size() {
    return this.count - this.lowestCount
  }

  isEmpty() {
    return this.size() === 0
  }

  clear() {
    this.items = {}
    this.count = 0
    this.lowestCount = 0
  }

  toString() {
    if (this.isEmpty()) {
      return ''
    }
    let objString = `${this.items[this.lowestCount]}`
    for (let i = this.lowestCount + 1; i < this.count; i++){
      objString = `${objString}, ${this.items[i]}`
    }
    return objString
  }

}

隊(duì)列的應(yīng)用

擊鼓傳花游戲

擊鼓傳花游戲: 簡(jiǎn)單描述就是一群人圍成一個(gè)圈傳遞花,喊停的時(shí)花在誰(shuí)手上就將被淘汰(每個(gè)人都可能在前端,每個(gè)參與者在隊(duì)列位置會(huì)不斷變化)，最后只剩下一個(gè)時(shí)就是贏者. 更加詳細(xì)可以自行查閱.

下面通過(guò)代碼實(shí)現(xiàn):

function hotPotato(elementsList, num) {
  // 創(chuàng)建一個(gè)容器
  const queue = new Queue()
  const elimitatedList = []
  // 把元素(參賽者)加入隊(duì)列中
  for (let i = 0, len = elementsList.length; i < len; i++) {
    queue.enqueue(elementsList[i])
  }

  /**
  * 擊鼓傳花
  * 首先隊(duì)列規(guī)則: 先進(jìn)先出
  * 那么在傳花過(guò)程中,任何一個(gè)元素都可能是前端, 在傳花的過(guò)程中應(yīng)該就是前端位置不斷變化.
  * 當(dāng)喊停的時(shí)(num 循環(huán)完), 也就是花落在誰(shuí)手(誰(shuí)在前端)則會(huì)被淘汰*（移除隊(duì)列）
  */

  while (queue.size() > 1) {
    for (let j = 0; j < num; j++) {
      queue.enqueue(queue.dequeue())
    }
    elimitatedList.push(queue.dequeue())
  }
  return {
    winer: queue.dequeue(),
    elimitatedList
  }
}

代碼運(yùn)行如下:

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]}
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 5, elimitatedList: [4, 8, 2, 7, 3,10, 9, 1, 6]}
console.log(hotPotato(arr, Math.ceil(Math.random() * 10))) // { winer: 8, elimitatedList: [10, 1, 3, 6, 2,9, 5, 7, 4]}

判斷回文

上一篇棧中也有涉及回文的實(shí)現(xiàn), 下面我們通過(guò)雙端隊(duì)列來(lái)實(shí)現(xiàn)同樣的功能.

function palindromeChecker(aString) {
  if (!aString || typeof aString !== 'string' || !aString.trim().length) {
    return false
  }
  const deque = new Deque()
  const lowerString = aString.toLowerCase().split(' ').join('')

  // 加入隊(duì)列

  for (let i = 0; i < lowerString.length; i++) {
    deque.addBack(lowerString[i])
  }

  let isEqual = true
  let firstChar = ''
  let lastChar = ''

  while (deque.size() > 1 && isEqual) {
    firstChar = deque.removeFront()
    lastChar = deque.removeBack()
    if (firstChar != lastChar) {
      isEqual = false
    }
  }

  return isEqual

}

下面通過(guò)代碼演示下:

console.log(palindromeChecker('abcba')) // true 當(dāng)前為回文

生成 1 到 n 的二進(jìn)制數(shù)

function generatePrintBinary(n) {
  var q = new Queue()
  q.enqueue('1')
  while (n-- > 0) {
    var s1 = q.peek()
    q.dequeue()
    console.log(s1)
    var s2 = s1
    q.enqueue(s1 + '0')
    q.enqueue(s2 + '1')
  }
}

generatePrintBinary(5) // => 1 10 11 100 101

到此這篇關(guān)于JS中隊(duì)列和雙端隊(duì)列實(shí)現(xiàn)及應(yīng)用詳解的文章就介紹到這了,更多相關(guān)JS 雙端隊(duì)列 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

相關(guān)文章

最新評(píng)論