Detaillierte Einführung in Warteschlangen in JavaScript (Codebeispiele)

Dieser Artikel bietet Ihnen eine detaillierte Einführung (Codebeispiel) über Warteschlangen in JavaScript. Ich hoffe, dass er für Freunde hilfreich ist.

Definition von Warteschlange

Eine Warteschlange ist eine geordnete Menge von Elementen, die dem First-In-First-Out-Prinzip folgt. Der Unterschied zu einem Stapel besteht darin, dass der Stapel Wird gepusht oder gepoppt Stapeloperationen werden alle am Anfang des Stapels ausgeführt, während Warteschlangen Elemente am Ende der Warteschlange hinzufügen und Elemente am Anfang der Warteschlange entfernen Zur Darstellung des Prozesses wird ein Diagramm verwendet:

Verwendung Ein anschaulicheres Beispiel ist: Warteschlangendienst. Die Person, die sich zuerst anstellt, erhält den Dienst immer zuerst. Die Situation des Warteschlangenspringens wird natürlich nicht berücksichtigt

Erstellung der Warteschlange

und des Stapels Die Erstellung ist ähnlich. Erstellen Sie zunächst eine Funktion, die die Warteschlange darstellt, und definieren Sie dann ein Array, um die Elemente in der Warteschlange zu speichern:

function Queue() {
  let items = []
}

Nachdem Sie die Warteschlange erstellt haben, müssen Sie einige Methoden dafür definieren. Im Allgemeinen enthält die Warteschlange die folgenden Methoden:

• enqueue(element): Fügen Sie am Ende ein neues Element hinzu queue

• dequeue(): Entfernt das erste Element der Warteschlange und gibt entfernte Elemente zurück

• front(): Gibt das erste Element in der Warteschlange zurück Warteschlange, und die Warteschlange nimmt keine Änderungen vor

• isEmpty(): Wenn die Warteschlange kein Element enthält, wird true zurückgegeben, andernfalls wird false zurückgegeben

• size(): Gibt die Anzahl der in der Warteschlange enthaltenen Elemente zurück

Spezifische Implementierung:

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())
  }
}

Nutzung der Warteschlange

Als nächstes schauen wir uns die Verwendung der Warteschlange an:

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

Fügen Sie zuerst drei Elemente zur Warteschlange hinzu: a, b, c, entfernen Sie dann ein Element aus der Warteschlange und drucken Sie schließlich die vorhandene Warteschlange aus Veranschaulichen Sie diesen Prozess gemeinsam:

es6 implementiert Queue

Ähnlich wie bei der Implementierung der Stack-Klasse können Sie auch die Syntax der es6-Klasse verwenden Um die Queue-Klasse zu implementieren, verwenden Sie WeakMap, um private Attributelemente zu speichern, und verwenden Sie Abschlüsse, um die Queue-Klasse zurückzugeben: Schauen wir uns die spezifische Implementierung an:

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()

Priority Queue

Prioritätswarteschlange, wie der Name schon sagt: Jedes Element in der Warteschlange hat seine eigene Priorität. Beim Einfügen wird der Einfügevorgang entsprechend der Prioritätsreihenfolge ausgeführt, was sich etwas von der vorherigen Warteschlangenimplementierung unterscheidet Schauen wir uns den spezifischen Code an:

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 <p> Wenn die Warteschlange leer ist, fügen Sie sie andernfalls direkt zur Warteschlange hinzu Je höher die Priorität, desto höher wird die Priorität an der Spitze der Warteschlange platziert. Verwenden wir ein Diagramm, um den Aufrufvorgang darzustellen: <br></p><p><img src="/static/imghw/default1.png" data-src="https://img.php.cn/upload/image/471/355/539/1550021327400018.png" class="lazy" title="1550021327400018.png" alt="Detaillierte Einführung in Warteschlangen in JavaScript (Codebeispiele)"></p> <p   style="max-width:90%"><strong>Zirkuläre Warteschlange</strong></p><p> Wie der Name schon sagt, ist die zirkuläre Warteschlange: Sie erhalten eine Zahl, durchlaufen dann die Warteschlange, entfernen ein Element vom Anfang der Warteschlange und fügen es dann hinzu Wenn die Schleife die angegebene Zahl erreicht, springen Sie aus der Schleife und bewegen Sie sich vom Anfang der Warteschlange, bis ein Element übrig bleibt: </p>rrree

Das obige ist der detaillierte Inhalt vonDetaillierte Einführung in Warteschlangen in JavaScript (Codebeispiele). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!