Queue

Die Queue ist eine weitere Dynamische Listenstruktur.
Sie ist nach einer Menschenschlange modelliert und befolgt deshalb das Prinzip First in, First Out (FIFO): Möchte man ein neues Element anfügen, wird dieses hinten angehängt.
Entfernt man ein Element weg, so entfernt man immer das vorderste.
So kommt der Mensch, der sich zuerst anstellt, auch zuerst dran.

Modellierung

Die Queue wird, wie der Stack, mit zwei Klassen modelliert:

Die Klasse Node kennen wir schon aus dem Stack: Sie speichert einen Wert des generischen Typs ContentType sowie einen Pointer auf die nächste Node, beides kann man über Getter-Methoden abfragen.

Die Queue speichert einen Pointer auf das erste Element der Schlange head sowie einen Pointer auf das letzte Element tail.

Darüber hinaus bietet sie vier Methoden, mit der man mit ihr interagieren kann. Diese sind im folgenden Beschrieben.

Algorithmen

Standard-Qeue

Es gibt vier Standard-Methoden, die eine Queue charakterisieren.

isEmpty()

Gibt zurück, ob der Stack leer ist.

boolean isEmpty() {
  return head == null;
}

front()

Gibt den Inhalt des ersten Elements zurück.

ContentType front() {
  if (isEmpty()) return null;
  return head.getContent();
}

Falls die Schlange leer ist, gibt es kein erstes Element. Dann gibt die Methode null zurück (siehe Z. 2).

enqueue()

Diese Methode hängt der Queue ein neues Element mit dem Wert value an;

void enqueue(ContentType value) {
  Node node = new Node(value);

  if (isEmpty()) {
    this.head = node;
    this.tail = node;
  } else {
    tail.setNext(node);
    this.tail = node;
  }
}

In Zeile 2 wird ein neues Element mit dem Wert value erzeugt. Dann wird dieses Element angehängt, wobei zwei Fälle unterschieden werden müssen:

Ist die Schlange leer (Z. 4), so wird das Element der neue head (Z. 5) und der neue tail (Z. 6).

Ist die Schlange nicht leer, also schon befüllt (Z. 7), so muss das Element angehangen werden. Dafür wird zuerst der Zeiger des aktuell letzten Elements, der akutell auf null zeigt, auf das neue Element umgebogen werden (Z. 8). Dann wird der eigene Zeiger tail auf das neue Element - den neuen tail - umgebogen (Z. 9).

Je nach Modellierung ist es notwendig, den eingefügten Wert auf Zulässigkeit zu überprüfen.

dequeue()

Diese Methode entfernt das erste Element.

void dequeue() {
  if (isEmpty()) return;

  head = head.getNext();
}

Falls die Schlange keine Elemente hat, also leer ist, kann auch kein Element entfernt werden. Dieser Fall wird in Z. 2 abgefangen.

Sonst wird einfach der eigene head-Pointer auf das Element nach dem aktuellen head, also das zweite Element in der Queue, umgebogen (Z. 4). Dieses wird zum neuen head.

PriorityQueue

Die PriorityQueue ist eine Erweiterung der Queue:

Jedem Element wird beim einfügen eine Priorität zugeordnet, unter Berücksichtigung derer es in der Queue einsortiert wird. So kann man auch Prozesse modellieren, in denen nicht jedes Element gleichberechtigt ist. Beispiel: Eine Schlange am Flughafen, bei der Platin-Kunden schneller einchecken dürfen.

Dabei gilt:

• $p \in \mathbb{N}$
• Haben zwei Elemente die gleiche Priorität, wird das ältere bevorzugt

Dafür muss man die Klasse Node um den int-Wert priority erweitern, dieser lässt sich mit getPriority() abrufen. Außerdem muss die enqueue() Methode angepasst werden:

Es gibt vier Fälle:

1. Die Schlange ist leer.
2. Das Element muss ans Ende der Queue.
3. Das Element muss an den Anfang der Queue.
4. Das Element muss zwischen Anfang und Ende.

// Fall 1: Schlange ist leer
if (isEmpty()) {
  head = newNode;
  tail = newNode;
}

Fall 1 ist identisch mit der normalen Queue.

// Fall 2: newNode muss an den Schluss
if (newNode.getPriority() <= tail.getPriority()){
  tail.setNext(newNode);
  tail = newNode;
}

Fall 2 erkennt man daran, dass die Priorität des neuen Elements kleiner/gleich ist zu der des aktuell letzen Elements.
In diesem Fall verfährt man wie in der normalen Queue.

// Fall 3: newNode muss an den Beginn
if (newNode.getPriority() > head.getPriority()) {
  newNode.setNext(head);
  head = newNode;
}

Fall 3 erkennt man daran, dass die Priorität des neuen Elements größer ist als die des aktuell ersten Elements. In diesem Fall wird der Pointer des neuen Elements auf den aktuellen head (das neue 2. Element) umgebogen (Z. 3). Dann wird der head-Pointer auf das neue Element umgebogen (Z. 4). Das neue Element wird also wie beim Stack “von oben” auf die Schlange aufgeschoben.

PriorityNode node = head;

while (node.getNext().getPriority() >= newNode.getPriority()) node = node.getNext();

newNode.setNext(node.getNext());
node.setNext(newNode);

Interessant ist der Default Case, Fall 4:
Hier muss erst einmal herausgefunden werden, wo das neue Element eingefügt werden muss, Dafür hangelt man sich, von head beginnend (Z. 1), solange durch alle Elemente bis man das Element findet, deren Nachfolger eine kleinere Priorität als das einzufügende Element besitzt (Z. 3). Denn: Zwischen dieser Node node und der nachfolgenden Node node.getNext() musss die neue Node newNode einsortiert werden.

Zuerst wird der Pointer der newNode auf die node.getNext() umgebogen (Z. 5). Dann wird der Pointer der node auf die newNode umgebogen (Z. 6). Das neue Element wird also zwischen dem gefundenen Element node und seinem Nachfolger node.getNext() eingeschoben.

Die fertige enqueue()- Methode sieht so aus:

void enqueue(ContentType content, int priority) {
  if (content == null) return;
  PriorityNode newNode = new PriorityNode(content, priority);

  // Fall 1: Queue ist leer
  if (isEmpty()) {
    head = newNode;
    tail = newNode;
  }
  // Fall 2: newNode muss an den Schluss
  else if (newNode.getPriority() <= tail.getPriority()){
    tail.setNext(newNode);
    tail = newNode;
  }
  // Fall 3: newNode muss an den Beginn
  else if (newNode.getPriority() > head.getPriority()) {
    newNode.setNext(head);
    head = newNode;
  }
  // Default: newNode muss in die Mitte
  else {
    PriorityNode node = head;

    // Node finden, deren Nachfolger eine kleinere Prio als `newNode` hat
    while (node.getNext().getPriority() >= newNode.getPriority()) node = node.getNext();

    // `newNode` zwischen `node` und `node.getNext()` platzieren
    newNode.setNext(node.getNext());
    node.setNext(newNode);
  }
}

Snippets

Queue<Integer> temp = new Queue<Integer>();

while (!queue.isEmpty()) {
  // do something

  temp.enqueue(queue.front());
  queue.dequeue();
}

queue = temp;

Möchte man über eine Queue iterieren, so ist es wichtig, die Werte zwischenzuspeichern. Dafür kann man eine temporäre Queue verwenden und alle Werte, bevor man sie entfernt, in ihr ablegen. Am Ende muss nur die Referenz ändern.

Möchte man den Speicherbedarf niedrig halten, so bietet sich auch folgende Möglichkeit an:

Integer top = queue.front();

while (queue.front() != top) {
  // do something

  queue.enqueue(queue.front());
  queue.dequeue();
}

Man speichert sich eine Referenz auf das oberste Element (Z. 1). Dann iteriert man durch die Queue und fügt das oberste Element immer wieder hinten an - man dreht die Schlange eine Position weiter (Z. 6). Ist der erste Wert einmal durch die Queue gewandert (Z. 3), hat man alle Elemente gesehen und kann abbrechen.

Durch diese Methode hat man deutlich weniger Speicherbedarf.

Nutzungsszenarien

Queues sind sehr hilfreich, um Prozesse zu modellieren. Im Unterricht haben wir zum als Beispiel das Wartezimmer kennengelernt, auch ein Musikplayer lässt sich damit modellieren.

Ein weitere Einsatzbereich ist die Modellierung asynchroner Abläufe: Man kann alle zu erledigenden Aufgaben in eine Schlange ablegen. Möchte man nun eine Aufgabe erledigen, nimmt man sich einfach die oberste herunter und arbeitet sie ab. So wird es ermöglicht, mit einem Prozess Aufgaben zu erstellen, die dann von mehreren Worker-Prozessen abgearbeitet werden. Beispielhaft für diese Arbeitsweise ist die Becherschlange bei Starbucks: Hier gibt es einen Kassierer, der neue Becher/Aufgaben in eine Schlange stellt. Nun gibt es mehrere Baristas/Worker, die diese Schlange abarbeiten ¹.

Der wesentliche Unterschied zwischen Stack und Queue ist, wo neue Elemente angehangen werden. Fügt man einem Stack schneller Elemente hinzu, als man sie wieder entfernt, so wird man die unteren Elemente nie zu sehen bekommen - für eine Aufgabenverwaltung ist das nicht zu gebrauchen.

Fügt man hingegen der Queue schneller Elemente hinzu, als man sie wieder entfernt, wird auch jedes Element wieder entfernt werden - perfekt für eine Aufgabenverwaltung.

Sehr zu empfehlen ist die Visualisierung der University of San Francisco: Hier kann man interaktiv erfahren, wie die Queue arbeitet.