Die Klasse Queue
Eine Queue (Schlange) ist ein Abstrakter Datentyp (ADT), der nach dem FIFO-Prinzip arbeitet: First in, first out. Genau wie bei einer Warteschlange vor einer Supermarkt-Kasse wird derjenige, der zuerst kommt, auch zuerst bedient, und wer sich hinten an die Schlange anstellt, wird auch als letzter bedient.
Die Operationen des ADT Queue sind:
- init() - erzeugt eine neue leere Schlange
- enqueue(x) - fügt das Element x hinten in die Schlange ein
- dequeue() - entfernt das vordere Element der Schlange
- front() - liefert das erste Element der Schlange zurück, ohne es zu entfernen
- empty() - liefert den Wert True, wenn die Schlange keine Element enthält
Ein bekanntes Beispiel für eine Queue in der Computertechnik ist die Druckerwarteschlange, in der die Druckaufträge verwaltet werden.
Eine Sonderform der Schlange ist die Priority Queue, bei der die Schlangen-Elemente eine Priorität besitzen, die dann die Position in der Warteschlange bestimmt.
Abituraufgaben
Der ADT Queue bzw. Implementationen dieses ADTs werden in folgenden Abituraufgaben eingesetzt:
2022-HT2: Sitzplanreservierung in der Turing-Schule
Weiterführende Links
Der ADT Schlange auf u-helmich.de