14.4 Der ADT Queue

Das FIFO-Prinzip

Eine Schlange oder Queue arbeitet nach dem FIFO-Prinzip: First in, first out. Das Element, das zuerst eingefügt wurde, wird auch als erstes wieder entfernt. Ein anschauliches Beispiel für eine solche Schlange ist der Einkauf in einem Supermarkt, und zwar in doppelter Hinsicht:

Wenn Sie Ihren Einkauf beendet haben und zahlen wollen, stellen Sie sich hinten an die Warteschlange an. Der Kunde, der sich als erster angestellt hat, wird auch als erster bedient. Der letzte Kunde wird zuletzt bedient.

Sie standen anfangs am Ende der Schlange, kurze Zeit später in der Mitte, weil sich weitere Kunden angestellt haben. Schließlich stehen Sie vorne in der Schlange und können endlich Ihre Waren auf das Transportband legen. Auch hier handelt es sich um eine Schlange. Die Tomatensuppe, die sie zuerst auf das Band gelegt haben, wird von dem Kassierer auch als erstes in die Kasse eingetippt. Und die Ware, die Sie zuletzt auf das Band gelegt haben, wird auch als letzte registriert.

Wir wollen jetzt etwas verallgemeinern:

Der ADT Queue wird durch folgende Operationen definiert:

Init(): Erzeugt eine leere Schlange.
Enqueue(x): Das Element x wird hinzugefügt.
Dequeue(): Das zuerst hinzugefügte Element wird entfernt.
Front(): Der Wert des zuerst hinzugefügten Elementes wird zurückgeliefert.
Empty(): Falls die Queue leer ist, wird TRUE zurückgeliefert, sonst FALSE.

Für Schüler(innen) anschaulicher, aber nicht mehr ganz so abstrakt ist die folgende Formulierung:

Der "ADT" Queue wird durch folgende Operationen definiert:

Init(): Erzeugt eine leere Schlange.
Enqueue(x): Das Element x wird hinten an die Schlange angehängt.
Dequeue(): Das vorderste Element der Schlange wird entfernt.
Front(): Der Wert des vordersten Elementes wird zurückgeliefert.
Empty(): Falls die Queue leer ist, wird TRUE zurückgeliefert, sonst FALSE.

Der Begriff "ADT" steht hier in Anführungszeichen, weil es eigentlich keine abstrakte Definition mehr ist, da von "vorderen" und "hinteren" Elementen die Rede ist, was schon eine starke Konkretisierung darstellt.

Übung 14.4-1 (5 Punkte)

Entwickeln Sie eine Klasse Queue, welche den ADT Queue realisiert (4 Punkte). Entwickeln Sie anschließend ein Testprogramm, welches die Operationen der Klasse Queue testet (1 Punkt).

Leistungsdifferenzierung:

Klausurschreiber und leistungsstarke mündliche Kandidaten programmieren die Klasse Queue bitte so, dass die Schlange Objekte verwaltet. Das Testprogramm muss dann natürlich entsprechende Objekte zur Verfügung stellen, beispielsweise Objekte der Klasse Pixel. Orientieren Sie sich dazu an dem Abschnitt "Die Implementierung eines universellen Stacks" auf der vorherigen Seite.
Mündliche Kandidaten können die einfachere Variante mit int-Zahlen wählen, die allerdings auch weniger Punkte bringt.

Hinweis zu ChatGPT:

Gerne können Sie sich den Quelltext auch von ChatGPT schreiben lassen. Achten Sie dann aber darauf, dass die Methoden genau so heißen wie die in der Definition vorgegebenen und dass die Methoden keine Textausgaben enthalten, was ChatGPT nämlich gerne macht.

Lösungsvorschlag auf den Lehrerseiten / nähere Infos dazu

Aufgaben / 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 (Wichtigkeit) werden chronologisch nach dem FIFO-Prinzip geordnet, wer zuerst angerufen hat, wird also auch zuerst bedient.

Eine priority queue nach Einfügen von 5 Elementen

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

Der einfachste Weg ist sicherlich der, für jede Priorität eine eigene Queue einzurichten. Wenn es nur drei Prioritäten gibt, wie in unserem Beispiel, würde man eine Klasse PriorityQueue entwickeln, die drei Attribute q1, q2, q3 der Klasse Queue besitzt, die wir bereits in der Übung 14.4-1 implementiert haben.

Die insert()-Methode von PriorityQueue würde dann als erstes nachschauen, welche Priorität das als Parameter übergebene Objekt hat, und dieses Objekt dann in die entsprechende Queue einfügen.

Die Methoden max und delete() würden ähnlich verfahren: Zunächst die richtige Queue heraussuchen, und dann den Auftrag an diese weiterleiten.

Übung 14.4-2 (8 Punkte)

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, je kleiner die Zahl, desto höher die 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.

Wertung: 2 Punkte für die Klasse Notruf, 4 Punkte für die Klasse PQueue, und 2 Punkte für das Testprogramm.

Lösungsvorschlag auf den Lehrerseiten / nähere Infos dazu

Die folgende Übung behandelt keine Priority Queue, sondern wieder eine normale Queue. Und zwar sollen Sie eine Methode schreiben, welche eine Queue sortiert. In der Praxis kommt so etwas zwar nicht oft vor, wohl aber im Informatik-Abitur NRW. Daher richtet sich diese Übung vor allem an Schüler(innen), die vorhaben, Informatik als Abiturfach zu wählen.

Experten-Übung 14.4-3 (5 Punkte)

Schreiben Sie eine Klasse QSort mit einer Methode sort(Queue q), welche die als Parameter übergebene Queue aus int-Zahlen sortiert. Die Methode sort darf ausschließlich über die öffentlichen Queue-Methoden auf die übergebene Queue zugreifen. Intern darf die Methode sort einfache Hilfsvariablen vom Typ int sowie eine Hilfsqueue zum Zwischenspeichern von Werten benutzen, mehr nicht.

Lösungshinweise für Schüler(innen)

Lösungsvorschlag auf den Lehrerseiten / nähere Infos dazu

Seitenanfang -
Allgemeines - Abstrakte Datentypen - Stack - Queue - Dictionary - List - ADTs im Abitur - Axiome