Vorlesung Informatik 2 - Teil B: Theorie
3.2 Queue
Wird auch als FIFO bezeichnet: First In First Out.
Eine Queue ist eine Warteschlange, sie hat genau zwei Operationen:
Queue<T>:
offfer(T x): void fügt x in die Warteschlange ein
poll():T
holt das nächste Element aus der Warteschlange.
Wie bei dem Stack haben diese Operationen die Komplexität O(1), sind also unabhängig von der Größe der Queue.
In der Praxis hat eine Queue häufig noch weitere Methoden wie isEmpty, peek, size.
Anwendungen für Queues:
- Warteschlange der rechenwilligen Prozesse im Betriebssystem. Wenn mehr Prozesse gerade eine CPU brauchen als die Zahl der logischen Prozessoren, werden die Prozesse in einer Queue angeordnet, die vom Scheduler verwaltet wird.
- Druckerwarteschlange: gemeinsam genutzte Drucker im Netzwerk haben eine Warteschlange.
- Internet: die Switche und Router im Netz haben Warteschlangen für die Pakete, die sie weiterschicken.
- In verteilten Systemen spielen Warteschlangen eine entscheidende Rolle,
- Mail: E-Mail MTA's (Mail Transfer Agent) nehmen E-MAils entgegen und senden sie weiter. Sie verwalten die Mails in Warteschlangen.
- Spiele: Tetris, Snake, Multiplayer-Spiele (Warten auf einen freien Raum in Overwatch u.s.w.),
- die Warteschlange beim Anruf einer Hotline,
- Verteilung des Covid-19 Impfstoffes,
- Wareschlangen beim Kauf von begrenzten Artikeln, Versteigerungen, ...
Implementierung mit einem Array (Ringpuffer):
Zu Beginn wächst der Inhalt des Arrays um neue Elemente, d.h. die Queue wird von lins nach rechts aufgefüllt. Eine Queue mit den Elementen ABCDEFG steht also zunächst so in einem Array der Länge 10:
A B C D E F G H _ _
Entfernt man die Element A, B und C und sieht das Array so aus
_ _ _ D E F G H _ _
^ ^
kopf ende
d.h. der Anfang der Queue steht am Index 3 und das Ende am Index 7.
Entfernt man D und E und fügt I J K und L hinzu hat man folgende Situation:
K L _ _ _ F G H I J
^ ^
ende kopf
Beim Einfügen eines neuen Elements und einer array-Länge n berechnet sich Ende zu
ende = (ende+1)%n
und das gleiche gilt beim Entfernen eines Elements für den Kopf:
kopf = (kopf+1)%n
Diese Implementierung ist ideal für Warteschlangen die nur eine maximale Anzahl von Elementen aufnehmen kann (Blocking Queue). Muss das Array vergrößert werden, hat die Umsortierung die Komplexität O(N).
Implementierung mit zirkulär verketteter Liste:
Hier schreiben wir uns wieder eine innere Hilfsklasse wie beim Stack:
private class Eintrag<T>{ // innere Klasse-------------------
T inhalt;
Eintrag next; // Zeiger auf den nächsten Eintrag der verketten Liste
}// Ende der inneren Klasse Eintrag ---------------------------Die Queue Klasse selbst hat nur eine einzige Eigenschaft: -ende: Eintrag
Ende Kopf -------------------------
| F | E | D | C | B | A |
-------------------------
die Queue wird so abgebildet:
--------------------------------------------------------------------
| |
V
------- ------- ------- ------- ------- ------- |
| A | +---->| B | +---->| C | +---->| D | +---->| E | +---->| F | +---- -------- ------- ------- ------- ------- -------
d.h. die Variable ende zeigt auf den letzten Eintrag, während ende.next auf den Kopf der Warteschlange zeigt.
Ein neuer Eintrag wird jetzt so hinzugefügt ( offer(x) ):
ende.next = new Eintrag(x, ende.next)
ende = ende.next
Und das Entfernen des letzten Eintrags geht so (poll() ):
ende.next = ende.next.next
In beiden Fällen müssen noch die Spezialfälle bedacht werden, dass die Queue leer (ende==null) ist bzw. nur einen Eintrag hat (ende=ende.next).