Einstieg: Wer zuerst kommt
Stell dir vor, du stehst an der Supermarktkasse. Die Regel ist klar: Wer zuerst da war, ist zuerst an der Reihe. Du stellst dich hinten an, und die Kassiererin bedient die Person vorne. Niemand kann sich einfach in die Mitte drängeln – das wäre unfair und würde das System durcheinanderbringen. Genau dieses Prinzip steckt hinter der Warteschlange in der Informatik.
Doch Warteschlangen sind nicht nur im Alltag wichtig. Sie spielen auch eine zentrale Rolle in vielen technischen Systemen:
- Druckaufträge: Wenn mehrere Personen gleichzeitig etwas ausdrucken, werden die Aufträge in einer Warteschlange abgearbeitet.
- Netzwerkpakete: Datenpakete, die über das Internet versendet werden, müssen in der richtigen Reihenfolge ankommen – auch hier sorgt eine Warteschlange für Ordnung.
- Serveranfragen: Ein Webserver bekommt oft hunderte Anfragen pro Sekunde. Diese werden in einer Warteschlange zwischengespeichert und nacheinander bearbeitet.
Beispiel aus dem Alltag: Du bist in einem Callcenter. Die Anrufe kommen rein, und die Mitarbeiter:innen nehmen sie in der Reihenfolge entgegen, in der sie eingehen. Wer zuerst anruft, wird zuerst bedient. Das ist eine klassische Warteschlange!
Beispiel aus der Technik: Ein 3D-Drucker bekommt mehrere Druckaufträge. Der Drucker arbeitet sie nacheinander ab – der erste Auftrag, der eingeht, wird auch zuerst gedruckt.
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 du nicht in die Mitte greifen kann, ist kein Mangel, sondern der Zweck. Eine Struktur, die nur zwei Operationen zulässt, kannst du 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 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 kommst du an das Element, das 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 ermitteln – nur mit enqueue, dequeue, front und isEmpty? Welchen Zustand hat die Schlange danach?
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?