Programmieren II (WF2)

Aufgabenblatt 5: Generische Datentypen

Aufgabe 5.1: Stapelspeicher für Zeichenketten (Stack)

Stapelspeicher (engl. Stacks) sind neben Arrays und verketteten Listen zentrale Datenstrukturen in der Informatik.

Obenstehendes Bild verdeutlicht die Funktionsweise: Der Stack funktioniert wie ein Stapel, auf dem Elemente abgelegt werden können ("push") und das obenliegende Element wieder weggenommen werden kann ("pop"). Zusätzlich kann das oberste Element angeschaut werden, ohne es vom Stapel zu nehmen ("peek"). Weiter "unten" liegende Elemente sind nicht zugänglich.

Aufgrund dieser Funktionsweise werden Stacks auch als LIFO-Struktur (Last-in-First-out) bezeichnet.

Eine Analogie in der realen Welt ist ein Stapel aus Büchern (unter der Annahme, dass Sie kein Buch aus der Mitte herausziehen können).

Anwendungen für Stacks sind z.B.

• Mikroprozessoren: Jeder Mikroprozessor nutzt einen Stack um abzuspeichern, an welcher Adresse bei Rücksprung aus einer Unterfunktion oder Methode die Programmausführung fortgesetzt werden soll. Zusätzlich werden lokale Variablen auf dem Stack (und in Registern des Prozessors) abgelegt.
• Die Java VM nutzt einen ähnlichen Mechanismus für Methodenaufrufe, Parameter und lokale Variablen.
• Bei der Berechnung von geklammerten und priorisierten Termen (z.B. 3 + 5 * (4 + sin(3x) + 8/2)* können Zwischenergebnisse auf den Stapel gelegt und nach Auswertung einer Klammer wieder zurückgeholt werden.
• Spielstrategien, z.B. für die "Türme von Hanoi" ¹.

Möchte man einen Stack in Java realisieren, können die Elemente in einer verketteten Liste oder in einem Array abgelegt werden.

Aufgabe:

Realisieren Sie ein Klasse StringStack, die einen Stapelspeicher für Zeichenketten in Java implementiert. Ihre Klasse sollte die Zeichenketten intern in einem Array verwalten und folgende extern zugängliche Methoden bieten:

• Konstrukturen mit einem optionalen Parameter für die maximale Größe des Stapels. Wird kein Parameter übergeben, kann der Stack maximal 100 Einträge enthalten.

• Methoden zum Zugriff auf die Elemente:

  • boolean push(String element): Legt ein Element auf den Stapel, falls maximale Anzahl der Einträge nicht überschritten wird. Gibt im Erfolgsfall true zurück.
  • String pop(): Entfernt ein Element vom Stapel und gibt es zurück. Falls der Stapel leer ist liefert die Methode null zurück.
  • String peek(): Liefert das oberste Element vom Stapel, entfernt es aber nicht. Falls der Stapel leer ist, gibt die Methode null zurück.

• Weitere Methoden:

  • int getSize(): Gibt die Anzahl der Elemente auf dem Stapel zurück.
  • boolean isEmpty(): Gibt true zurück, wenn der Stapel leer ist.
  • boolean isFull(): Gibt true zurück, wenn der Stapel voll ist und kein Element mehr hinzugefügt werden kann.
  • public String toString(): Gibt die Größe und den Inhalt des Stapels als Zeichenkette zurück.

Implementieren Sie entwicklungsbegleitend auch eine Testklasse StringStackTest, die Ihre Implementierung auf Herz und Nieren prüft, indem ein Objekt erzeugt und die Methoden in unterschiedlichen Szenarien aufgerufen werden. Prüfen Sie insbesondere auch Grenzwerte und besondere Situationen!

Optionale Zusatzaufgabe:

Erweitern Sie Ihre Implementierung so, dass die maximale Größe des Stapels bei Objekterzeugung nicht mehr angegeben werden muss. Der Stapel soll, wenn er voll ist, automatisch seine Größe anpassen, indem ein neues größeres Array erzeugt wird und die bisherigen Inhalte kopiert werden.

Hinweis:

• Ob der Stapel intern im Array „nach unten“ oder „nach oben“ wächst ist für die Funktionsweise egal. Wählen Sie die für Sie praktischere Variante.

Aufgabe 5.2: Eine eigene Stack-Klasse als generischer Datentyp

Realisieren Sie basierend auf Ihrer existierenden Implementierung für Zeichenketten eine generische Klasse MyStack<E> die einen Stapelspeicher für beliebige Elemente in Java implementiert!

Ihre generische Klasse soll alle öffentlichen Methoden der StringStack-Klasse bieten.

Schreiben Sie zusätzlich eine Testklasse MyStackTest, die Ihren Stack gründlich testet.

Aufgabe 5.3: Stack-Utilities

Schreiben Sie eine Klasse MyStackUtils, die ein paar statische Hilfsmethoden zur Arbeit mit Stacks enthält.

Realisieren Sie folgende Methoden:

• combine: Erhält zwei gleichartige Stacks s1 und s2 als Parameter und liefert einen neuen Stack zurück, der zunächst alle Elemente aus s1, darauf dann alle Elemente von s2 enthält.

  Beispiel:

  

• shuffle: Erhält zwei gleichartige Stacks s2 und s2 als Parameter und liefert einen neuen Stack zurück, der die Elemente der Stacks abwechselnd durchmischt enthält. Falls einer der Stacks größer ist als der andere, liegen die übriggebliebenen Elemente zuoberst.

  Beispiel:

  

Wählen Sie für die Parameter geeignete Wildcards!