JSデータ構造学習:キュー

キューの定義

キューは先進的な先出し原則に従う一連の秩序ある項目であり、スタックとは異なり、スタックは入スタックでも出スタックでもスタックのトップで操作され、キューはキューの尾に要素を追加し、キューのトップを削除し、図で大体このようなことを表している:よりイメージ的な例では、キューサービスは、いつも先に並んでいる人が先にサービスを受け、もちろん割り込みの状況を考慮しない

キューの作成

スタックの作成と同様に、まずキューを表す関数を作成し、キュー内の要素を保存する配列を定義します.

function Queue() {
  let items = []
}

キューを作成するには、いくつかのメソッドを定義する必要があります.一般的に、キューには次のメソッドが含まれます.

enqueue(element):新しいアイテム

をキューの末尾に追加します.

dequeue():キューの最初のアイテムを削除し、削除された要素

を返します.

front():キューの第1項を返し、キューは変更しない

isEmpty():キューにtrueを返す要素がない場合、false

を返します.

size():戻りキューに含まれる要素の数

具体的な実装:

function Queue() {
  let items = []
  //            
  this.enqueue = function (element) {
    items.push(element)
  }
  //         ，          
  this.dequeue = function () {
    return items.shift()
  }
  //          
  this.front = function () {
    return items[0]
  }
  //         
  this.isEmpty = function () {
    return items.length === 0
  }
  //        
  this.size = function () {
    return items.length
  }
  //     ，    
  this.print = function () {
    console.log(items.toString())
  }
}

キューの使用

次に、キューの使用方法を見てみましょう.

let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.dequeue()
queue.print()

まず、キューに3つの要素を追加します.a,b,c、次にキューの要素を削除し、最後に既存のキューを印刷します.この手順を説明します.

Es 6実装Queue

Stackクラスを実装するのと同様に、es 6のclass構文でQueueクラスを実装し、WeakMapでプライベート属性itemsを保存し、閉パケットでQueueクラスを返すこともできます.具体的な実装を見てみましょう.

let Queue = (function () {
  let items = new WeakMap
  class Queue {
    constructor () {
      items.set(this, [])
    }
    enqueue (element) {
      let q = items.get(this)
      q.push(element)
    }
    dequeue () {
      let q = items.get(this)
      return q.shift()
    }
    front () {
      let q = items.get(this)
      return q[0]
    }
    isEmpty () {
      let q = items.get(this)
      return q.length === 0
    }
    size () {
      let q = items.get(this)
      return q.length
    }
    print () {
      let q = items.get(this)
      console.log(q.toString())
    }
  }
  return Queue
})()
let queue = new Queue()
queue.enqueue('a')
queue.enqueue('b')
queue.enqueue('c')
queue.dequeue()
queue.print()

ゆうせんキュー

優先キューはその名の通り、キュー内の各要素にはそれぞれ優先度があり、挿入時に優先度の高低順に挿入操作が行われ、前のキューとは少し異なる場所で、キュー内の要素が多くなると先級の属性があり、具体的なコードを見てみましょう.

function PriorityQueue() {
  let items = []
  //     ，          
  function QueueElement(element, priority) {
    this.element = element
    this.priority = priority
  }
  this.enqueue = function (element, priority) {
    let queueElement = new QueueElement(element, priority)
    let added = false
    for (let i = 0; i < items.length; i++) {
      //         
      if (queueElement.priority < items[i].priority) {
        items.splice(i, 0, queueElement)
        added = true
        break
      }
    }
    if (!added) {
      items.push(queueElement)
    }
  }
  this.dequeue = function () {
    return items.shift()
  }
  this.front = function () {
    return items[0]
  }
  this.isEmpty = function () {
    return items.length === 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    for (let i = 0; i < items.length; i++) {
      console.log(`${items[i].priority}-${items[i].element}`)
    }
  }
}
let priorityQueue = new PriorityQueue()
priorityQueue.enqueue('a', 3)
priorityQueue.enqueue('b', 2)
priorityQueue.enqueue('c', 1)
priorityQueue.dequeue()
priorityQueue.print()

キューが空の場合、キューに直接追加されます.そうでない場合、priorityは小さい優先度が高く、優先度が高いほどキューの前に配置されます.次に、呼び出しプロセスを図で示します.

ループキュー

ループ・キューは、名前の通り、1つの数を指定し、キューを反復してキューの先頭から1つを削除し、キューの末尾に追加します.指定した数にループしたときにループを飛び出し、残りの要素までキューの先頭から1つを削除します.次に、具体的なコードを見てみましょう.

unction Queue() {
  let items = []
  this.enqueue = function (element) {
    items.push(element)
  }
  this.dequeue = function () {
    return items.shift()
  }
  this.front = function () {
    return items[0]
  }
  this.isEmpty = function () {
    return items.length === 0
  }
  this.size = function () {
    return items.length
  }
  this.print = function () {
    console.log(items.toString())
  }
}
function loopQueue(list, num) {
  let queue = new Queue()
  for (let i = 0; i 1) {
    for (let j = 0; j

まとめ

この文章は主にキューについて簡単に紹介し,キューおよび関連応用について簡単に実現した.間違いや厳密でないところがあれば、批判を歓迎し、好きなら、いいねを歓迎します.