Zwei Schlangen
Zwei Schlangen
Prompt: Ulrich Helmich 2026, Creator: ChatGPT.
Dieses Bild zeigt zwei Schlangen! Die erste Warteschlange besteht aus den Kunden, die vor der Kasse anstehen. Die zweite Schlange besteht aus den Waren, die auf dem Kassenband liegen.
Beide Schlangen arbeiten nach dem FIFO-Prinzip: First in, first out. Das Element, das zuerst eingefügt wurde, wird auch als erstes wieder entfernt. In der Informatik wird eine solche Schlange durch den abstrakten Datentyp Queue beschrieben.
Der ADT Queue wird durch folgende Operationen definiert:
- Init(): Erzeugt eine leere Schlange.
- Enqueue(x): Das Element x wird am Ende der Schlange hinzugefügt.
- Dequeue(): Das Element am Anfang der Schlange wird entfernt.
- Front(): Liefert das Element am Anfang der Schlange zurück, ohne es zu entfernen.
- Empty(): Falls die Queue leer ist, wird TRUE zurückgeliefert, sonst FALSE.
Aufgabe 14.4-1
Wenn Sie eine Klasse Stack implementiert haben, sollte es Ihnen nicht schwer fallen, auch eine Klasse Queue zu programmieren, in der int- oder double-Zahlen nach dem Queue-Prinzip gespeichert werden.
- Erstellen Sie eine solche Klasse Queue mit den oben genannten Operationen (Init() wird durch den Konstruktor realisiert).
- Schreiben Sie eine Testklasse, mit der Sie die fünf Operationen der Schlange überprüfen können.
- Für das Testen der Schlange wäre es außerdem hilfreich, wenn die Klasse Queue noch über eine show()-Methode verfügen würde, mit der Sie sich den Inhalt der Schlange in der Konsole ausgeben lassen können. Ergänzen Sie Queue um eine solche Methode.
Der ADT Queue im Abitur
Im Zentralabitur Informatik des Landes NRW spielt der ADT Queue eine wesentliche Rolle, die Schlange scheint fast noch wichtiger zu sein als der Stack. Aus diesem Grund habe ich eine Extra-Seite zum Thema "ADTs im Abitur NRW" geschrieben. Im Anschluss an die allgemeinen Ausführungen gibt es hier eine Seite mit anspruchsvolleren Aufgaben zum Thema Queue.
Alle Klausurkandidaten und vor allem alle Leute, die Informatik im Abitur wählen, sollten diese Aufgaben durcharbeiten. Natürlich sind auch leistungsstarke GK-Schüler, die noch Zeit haben und Punkte brauchen, eingeladen, diese Aufgaben zu bearbeiten.
Der ADT Priority Queue
Kommen wir nun zu einem ganz wichtigen ADT, der Priority Queue. Eine Priority queue oder Prioritäts-Warteschlange ist eine Sonderform der Queue. Hier werden neue Elemente nicht einfach hinten in die Schlange eingefügt, sondern nach Priorität (Wichtigkeit).
Stellen Sie sich die Polizeiwache einer Großstadt vor, in der pro Viertelstunde acht oder mehr Notrufe eingehen. Manche dieser Notrufe sind wichtig ("Ich habe ein Messer im Rücken..."), andere eher unwichtig ("Die Nachbarn sind wieder so laut..."). Die Zahl der Einsatzwagen ist begrenzt, daher kann die Polizei nicht sofort auf jeden Notruf reagieren. Die Notrufe werden in einer Warteschlange gespeichert. Allerdings haben dabei die wichtigen Notrufe ("Messer im Rücken...") Vorrang, werden also vorne in der Warteschlange untergebracht. Eher unwichtige Notrufe kommen weiter hinten in die Schlange. Notrufe mit der gleichen Priorität (Dringlichkeit) werden chronologisch nach dem FIFO-Prinzip geordnet, wer zuerst angerufen hat, wird also auch zuerst bedient.
Die Operation Max() liefert das vorderste / erste Element mit der höchsten Priorität (also der kleinsten Zahl), ohne aber die Schlange zu verändern. Die Operation Delete() löscht das vorderste Element.
In unserem Beispiel würde Max() den Notruf 4 liefern. Das ist zwar nicht der erste Notruf, der in dem Zeitraum eingegangen ist, aber der erste Notruf mit der höchsten Priorität. Mit Delete() würde dann der Notruf 4 aus der Schlange gelöscht.
Der ADT priority Queue wird durch folgende Operationen definiert:
- Init(): Erzeugt eine leere Schlange.
- Insert(x): Das Element x wird entsprechend seiner Priorität hinzugefügt.
Elemente mit gleicher Priorität werden nach der Reihenfolge des Einfügens gespeichert - wie bei einer normalen Schlange. - Delete(): Das Element mit der höchsten Priorität wird entfernt.
- Max(): Der Wert des Elements mit der höchsten Priorität wird zurückgeliefert.
- Empty(): Falls die Schlange leer ist, wird TRUE zurückgeliefert, sonst FALSE.
Überlegungen zur Implementierung
Das Schöne an abstrakten Datentypen ist ja, dass ihre Definition allein durch die möglichen Operationen und deren Verhalten festgelegt wird. Es wird nicht vorgeschrieben, wie ein solcher Datentyp intern implementiert werden muss. Um eine Priority Queue zu implementieren, können wir also verschiedene Wege einschlagen. Wichtig ist nur, dass die fünf Operationen genau so funktionieren, wie es in der Definition festgelegt wurde.
Eine einfache Implementierung
Eine normale Queue zu implementieren, ist recht einfach. Für eine Priority Queue mit drei Prioritätsstufen können wir einfach drei solcher normalen Queues einsetzen, eine für jede Priorität. Innerhalb jeder dieser Queues gilt das FIFO-Prinzip: Das zuerst eingefügte Element wird auch als erstes wieder entfernt. Elemente mit höherer Priorität werden jedoch grundsätzlich vor Elementen mit niedrigerer Priorität berücksichtigt.
Die Operation init() würde durch den Konstruktor der Klasse PriorityQueue umgesetzt. In diesem Konstruktor würden wir drei Instanzvariablen vom Typ Queue initialisieren, die wir beispielsweise q1, q2 und q3 nennen könnten. Dabei soll q1 die höchste und q3 die niedrigste Prioritätsstufe repräsentieren. Wenn mehr als drei Prioritätsstufen gewünscht werden, könnte man auch ein Array mit entsprechend vielen Queue-Objekten verwenden.
Die insert()-Methode würde zunächst die Priorität des neuen Elementes ermitteln und das Element dann hinten in die entsprechende Queue einfügen.
Die max()-Methode würde zunächst in der Queue mit der höchsten Priorität nachschauen, ob noch mindestens ein Element vorhanden ist und dann dessen Wert zurückliefern, ohne es zu entfernen. Wenn diese Queue leer ist, wird die Queue mit der nächstniedrigen Priorität untersucht und so weiter.
Entsprechend würde die Methode delete() verfahren. Allerdings wird hier das vorderste Element der Queue mit der höchsten aktuell vorhandenen Priorität entfernt.
Die Methode empty() müsste überprüfen, ob alle drei Queues leer sind. Nur wenn dies der Fall ist, liefert sie den Wert true zurück, andernfalls false.
Übung 14.4-2
Erstellen Sie zunächst eine Klasse Notruf mit folgenden Attributen:
- int-Attribut nummer (Nummer des Auftrags, chronologische Reihenfolge)
- String-Attribut beschreibung mit einer Beschreibung des Auftrags, zum Beispiel "Ruhestörung".
- int-Attribut stunde (Eingang des Auftrags)
- int-Attribut minute (Eingang des Auftrags)
- int-Attribut sekunde (Eingang des Auftrags)
- int-Attribut prio mit der Priorität 1, 2 oder 3 (1 = höchste Priorität).
Entwickeln Sie eine Klasse PQueue, die in der Lage ist, Objekte der Klasse Notruf nach dem oben beschriebenen Verfahren (Priority queue mit drei einzelnen Schlangen) zu verwalten.
Was jetzt noch fehlt, ist ein Testprogramm, mit dem Sie die Klasse PQueue testen können. Das Testprogramm erzeugt ein leeres Objekt der Klasse PQueue und fügt dann acht Notrufe in die Priority queue ein, Sie können sich dabei gern an der Abbildung 1 orientieren. Anschließend soll eine ausgeben()-Methode die acht Notrufe in der Konsole anzeigen, und zwar so, wie sie in der Schlange gespeichert sind. Dazu sollten Sie die Klasse Notruf mit einer eigenen ausgeben()-Methode ausstatten, die dann einfach vom Testprogramm aufgerufen werden kann.
Axiomatische Definition
Für Studierende der Informatik
Aufgabe 14.4-3
Erklären Sie die einzelnen Axiome.
Überprüfen Sie, ob diese axiomatische Defintion des ADT Queue mit der im Text dargestellten Definition übereinstimmt.
Seitenanfang -
Allgemeines -
Abstrakte Datentypen -
Stack -
Queue -
Dictionary -
List -
ADTs im Abitur -
Axiome