Einstieg: Wer zuerst kommt
An der Supermarktkasse gilt eine Regel, die niemand aufschreiben muss: Wer zuerst da war, ist zuerst dran. Wer dazukommt, stellt sich hinten an. Bedient wird vorne. Dazwischen passiert nichts – man kann sich nicht in die Mitte stellen und auch niemanden aus der Mitte herausziehen.
Genau diese Regel – und genau diese Beschränkung – ist die Warteschlange.
Eine Warteschlange (englisch queue) ist eine lineare Datenstruktur mit zwei Zugriffsstellen:
- hinten wird eingefügt (
enqueue), - vorne wird gelesen (
front) und entfernt (dequeue).
Das Prinzip heißt FIFO – First In, First Out: Was zuerst hineinkommt, kommt zuerst wieder heraus.
Dass man nicht in die Mitte greifen kann, ist kein Mangel, sondern der Zweck. Eine Struktur, die nur zwei Operationen zulässt, kann man nicht falsch bedienen – und sie lässt sich so bauen, dass beide Operationen gleich schnell sind, egal wie lang die Schlange ist.
Wo dir das im Rechner begegnet: Druckaufträge, eingehende Netzwerkpakete, Tastatureingaben, Aufgaben in einer Warteliste.
Von außen zeigt die Abiturklasse Queue nur diese Methoden. Wie sie innen aufgebaut ist, spielt für das Benutzen keine Rolle.
classDiagram
class Queue~ContentType~ {
+Queue()
+isEmpty() boolean
+enqueue(pContent: ContentType)
+dequeue()
+front() ContentType
}
Erst einmal ausprobieren
Unten liegt eine Operationsfolge bereit. Sage zuerst voraus, welche Ausgaben sie erzeugt, und lass sie dann ablaufen.
a) Notiere die erwarteten Ausgaben, trage sie ein und lass die Folge ablaufen.
b) Nur front() und isEmpty() liefern überhaupt etwas. Erkläre, warum dequeue() keinen Rückgabewert braucht. Wie kommt man an das Element, das gleich entfernt wird?
c) Reihe danach von Hand drei Namen ein und nimm sie wieder heraus. In welcher Reihenfolge kommen sie heraus?
Weiterdenken: Die Schlange hat keine Methode, die sagt, wie viele Elemente in ihr stehen. Wie könntest du es trotzdem herausfinden – nur mit enqueue, dequeue, front und isEmpty? Und was ist danach mit der Schlange passiert?
Wer kommt als Nächstes dran?
Entscheide jeweils, ob eine Warteschlange passt. Begründe mit dem FIFO-Prinzip.
a) Ein Drucker im Schulnetz bekommt Aufträge von mehreren Rechnern.
b) Ein Textprogramm soll die letzte Änderung rückgängig machen.
c) Eine Arztpraxis ruft Patientinnen und Patienten in der Reihenfolge ihrer Ankunft auf.
d) Ein Server bekommt mehr Anfragen, als er gleichzeitig beantworten kann.
Weiterdenken: In der Notaufnahme wird nicht nach Ankunft, sondern nach Dringlichkeit behandelt. Wie könnte man das mit mehreren Warteschlangen lösen?