Implementierung

Nur Leistungskurs. Die Operationen einer dynamischen Datenstruktur selbst zu implementieren, gehört zu den zusätzlichen Anforderungen des Leistungskurses. Im Grundkurs genügt es, den Aufbau der Warteschlange zu erläutern (Aufbau und Funktionsweise) und sie über ihre Dokumentation zu benutzen – so, wie es auch im Zentralabitur vorausgesetzt wird.

Aufgaben

Implementiere die Methode enqueue. Sie soll das Content-Objekt (pContent) ans Ende der Warteschlange anhängen.
Implementiere die Methode dequeue. Sie soll den ersten Knoten der warteschlange entfernen.
Implementiere die Methode front. Sie soll den Inhalt des ersten Knotens zurückgeben.
Implementiere die Methode isEmpty. Sie soll zurückgeben, ob die Warteschlange leer ist.

Da in der Online-IDE bereits eine Klasse Queue existiert, benennen wir die Klasse in NRWQueue um.

Hilfe: Code-Puzzle und Schreibtischtest

Die Puzzles zeigen dieselben Methoden, die du oben schreiben sollst – in Einzelteilen. Der Schreibtischtest am Ende prüft, ob du den Ablauf im Kopf hast.

Tipp: Zwei Enden, zwei Verweise

Anders als der Stapel arbeitet die Warteschlange an beiden Enden: enqueue hinten, front und dequeue vorne. Deshalb gibt es zwei Verweise.

Zwei Sonderfälle entscheiden über richtig und falsch: Was ist, wenn die Schlange leer ist und der erste Knoten dazukommt? Und was, wenn der letzte Knoten entnommen wird?

Lösung. Erfrage das Passwort bei deiner Lehrkraft.

Selbsttest

1. Welche Verweise braucht eine Schlange?

{r1{nur einen auf das vorderste Element}}

{r1{!je einen auf das vorderste und das hinterste Element}}

{r1{einen auf jedes Element}}

{h{An beiden Enden wird gearbeitet.}} {H{Richtig!}}

2. Was muss beim Einfügen in eine leere Schlange beachtet werden?

{r2{nichts}}

{r2{!beide Verweise müssen auf den neuen Knoten zeigen}}

{r2{es muss zuerst front aufgerufen werden}}

{h{Der einzige Knoten ist gleichzeitig der vorderste und der hinterste.}} {H{Richtig!}}

3. Was muss beim Entfernen des letzten verbliebenen Elements beachtet werden?

{r3{nichts}}

{r3{!auch der Verweis auf das hinterste Element muss auf null gesetzt werden}}

{r3{die Schlange muss neu erzeugt werden}}

{h{Sonst zeigt der hintere Verweis noch auf einen entfernten Knoten.}} {H{Richtig! Das ist der häufigste Fehler bei dieser Implementierung.}}

4. Welche Aufwandsklasse haben alle Operationen der Schlange?

{r4{linear}}

{r4{!konstant}}

{r4{logarithmisch}}

{h{Es wird nur an den beiden Enden gearbeitet, nie durchlaufen.}} {H{Richtig!}}