Übungsaufgabe zur Veranstaltung Programmieren 2 im Bachelorstudiengang Wirtschaftsinformatik an der Hochschule Rosenheim.
In dieser Übung implementieren wir Iteratoren für die Datenstrukturen Stack und Set aus den letzten beiden Übungen.
Gegeben ist eine generische Implementierung für das Set, in Anlehnung an die Musterlösung der Übung 3.
- Implementieren Sie durch das Interface
Iterablevorgeschriebene Methodeiterator. - Implementieren Sie dazu einen Iterator, welche alle Elemente besucht.
- Stellen Sie sicher, dass der Testcase
TestSet.testStringSetkorrekt durchläuft.
- Die Verwendung einer Agenda ist zwingend notwendig!
- Was ändert sich an der Besuchsreihenfolge, wenn Sie für die Agenda statt einer Liste einen Stack verwenden?
Gegeben ist eine generische Implementierung eines Stapels (stack), in Anlehnung an die Musterlösung der Übung 3.
Ein Stack ist eine Datenstruktur, dessen Reihenfolge bei der Entnahme (pop) umgekehrt zur Reihenfolge des hinzufügens (push) ist.
Das heisst, das zuletzt mit push hinzugefügte Element das wird als nächstes mit pop entnommen (last in, first out).
- Implementieren Sie (nur) die durch das Interface
Iterablevorgeschriebene Methodeiterator. - Implementieren Sie dazu einen Reverse-Iterator, der die Elemente in umgekehrter Reihenfolge besucht. Für einen Stack bedeutet das: in der Reihenfolge, in der die Elemente hinzugefügt wurden, also first in, first out.
- Stellen Sie sicher, dass der Testcase
StackTest.testStackkorrekt durchläuft.
Ein Beispiel: Werden in einen Stack<Integer> die Werte 1, 4, 5, 2 gepusht, so ist die Reihenfolge bei pop 2, 5, 4, 1.
Stack<Integer> stack = new StackImpl<>();
stack.push(1);
stack.push(4);
stack.push(5);
stack.push(2);
stack.pop(); // 2
stack.pop(); // 5
stack.pop(); // 4
stack.pop(); // 1Iteriert man hingegen darüber, so soll die Einfügereihenfolge eingehalten werden:
Stack<Integer> stack = new StackImpl<>();
stack.push(1);
stack.push(4);
stack.push(5);
stack.push(2);
for (int i : stack)
System.out.println(i);
// 1
// 4
// 5
// 2- Auch die Iteration einer sequenzielle Datenstruktur kann mit einer Agenda realisiert werden; wie verhält sich diese über die Lebensdauer?
- Welche Datenstruktur eignet sich, um die Reihenfolge zu invertieren?
- Implementieren Sie die Methode
SetImpl<T>.leafIterator. - Implementieren Sie diesen Iterator so, dass nur Blätter zurückgegeben werden, also Elemente ohne Nachfolger.
- Stellen Sie sicher, dass der Testcase
SetTest.testLeafIteratorkorrekt durchläuft.
Diese Aufgabe ist aussergewöhnlich trickreich!
Die Hauptschwierigkeit besteht darin, dass auch die hasNext Methode verlässlich funktioniert.
Eine Herangehensweise ist, neben der Agenda für die Traversierung der Baumstruktur auch eine Referenz auf das nächste Blatt zu unterhalten.
Wird nun das nächste Element angefordert, so kann man dieses schnell zurückgeben, muss aber anschließend gleich versuchen, das nächste zu finden.