JSにおけるキューとダブルエンドキューの実現と応用の詳細

キュー

列

二二端キューデータ構造

アプリケーション

用のシューティングゲームのシミュレーションサイクル行列

.二重端列で一語が回文

を構成するかどうかを確認する。

は、1からnまでのバイナリ数

を生成する。
キューとツーエンドの列
列は先进的な后出（FIFO、先来先サービスともいう）の原则に従っています。
列の特性によって、銀行の行列を例にとって、列は次のような基本的な操作を含むべきです。

列に参加する（番号を取る）enqueue

列からdequeue

を除去する。

現在の待ち行列番号（次の人を呼ぶ）peek

現在の列の長さ(現在の列の人数)size

は、キューが空ISEmpty

であるかどうかを判断する。

class Queue {
  constructor() {
    //     ,     length
    this.count = 0
    //       
    this.items = {}
    //      ,     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() {
    /**
    *        :
    * 1. count    
    * 2. lowestCount    
    *        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
  }

}

ダブルエンド行列(dequeまたはdoub-ended queue)
二重の列は何ですか？
フロントエンドとバックエンドから要素を追加することができます。原則に従って先に出します。
二重端列は、スタック（後進先出）とキュー（先入先出）の結合体として理解されます。それに関連して、対応する操作もキューをサポートします。スタックの操作です。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
  }

}

キューの適用
太鼓を打って花を伝える遊び
鼓を打って花のゲームを伝えます：簡単な説明は1群の人が囲んで1つの輪を伝えて花を伝えて、止まったことを叫ぶ時使って誰の手の上で淘汰されます（すべての人はすべて先端になるかもしれなくて、すべての参加者は列の位置で絶えず変化します）、最後にただ1つだけ残します。
以下はコードによって実現されます。

function hotPotato(elementsList, num) {
  //       
  const queue = new Queue()
  const elimitatedList = []
  //    (   )     
  for (let i = 0, len = elementsList.length; i < len; i++) {
    queue.enqueue(elementsList[i])
  }

  /**
  *     
  *       :     
  *         ,            ,                    .
  *      (num    ),         (    )     *（    ）
  */

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

コードの実行は以下の通りです

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]}

判断回文
前のスタックの中にも回文の実現に関するものがあります。次に私達は二重端行列を通して同じ機能を実現します。

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

  //     

  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

}

コードによるデモを行います。

console.log(palindromeChecker('abcba')) // true      

1からnまでのバイナリ数を生成します。

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

ここでは、JSの中列と双端列の実現と応用についての詳細な文章を紹介します。JSの双端行列については、以前の文章を検索したり、下記の関連記事を見たりしてください。これからもよろしくお願いします。