Datenstrukturgratis

Queue

Eine Sammlung nach dem Prinzip „first in, first out“: hinten anstellen, vorne entnehmen.

Zeit: O(1)
Speicher: O(n)

// Schritt für Schritt

Schritt 1 / 7

1class Queue {2  items = [];3  head = 0;4  enqueue(x) {5    this.items.push(x);6  }7  dequeue() {8    return this.items[this.head++];9  }10}

head: = 0

leer

Wir starten mit einer leeren Queue. head markiert den Anfang.

Tipp: Mit den Pfeiltasten durch die Schritte gehen.

So funktioniert es

Diese Queue speichert ihre Elemente in einem Array und merkt sich mit einem Index head den Anfang. Enqueue hängt hinten an; dequeue liest das Element bei head und schiebt head weiter, sodass keine Operation das Array verschieben muss. Queues stecken hinter Breitensuche, Aufgabenplanung und Puffern.