Konrad-Adenauer-Gymnasium Langenfeld

Informatik Grundkurs Q1

Stapelklasse

Ist die Klasse doppeltveketteteListe geeignet für die Lösung?

Alle diese Operationen sind in der Klasse doppeltverketteteListe vorhanden, so dass eine Implementierung unter Verwendung der Klasse doppeltverketteteListe einfach möglich ist. Sie ist jedoch nicht optimal, da die Klasse doppeltverketteteListe weitere Operationen besitzt, die bei diesem Rangierproblem nicht möglich sind.

Beispiel:

Die Methoden einfuegen, aktuellesEntfernen sind außer für Spezialfälle "technisch" im Rangierbetrieb nicht möglich, könnten aber als Listen-Methoden verwendet werden.

Klasse Stapel

Wir wollen also von doppeltverketteteListe eine neue Klasse Stapel ableiten, die genau die oben genannten Operationen erlaubt. Man bezeichnet die spezielle Listenstruktur, die das Einfügen, Entfernen und Lesen des aktuellen Elements nur am Anfang erlaubt, als eine Keller- oder Stapel-Struktur (englisch: Stack): Der Wert, der als erstes "auf den Stapel" gelegt wurde, kann nur als letztes, also wenn alle anderen Werte, die später hinzugefügt wurden, bereits wieder entfernt sind, entfernt werden, also wenn dieser Wert wieder der erste auf dem Stapel ist. In der Informatik spricht man auch von einer LIFO-Struktur: Last in, First out .

Operation:	Stapel-Methode:
Erzeugen eines neuen Stapels	public Stapel()
Anfügen eines neuen Elements	public void push(Object o)
Lesen des aktuellen Elements	public Object aktuellesElement()
Löschen des obersten Elements	public void pop()
Test, ob Stapel leer	public boolean istLeer()

Die Namen der Methoden entsprechen den in der Informatik eingeführten Bezeichnungen. Die Methode aktuellesElement wird in der Informatik meist mit Top benannt. Die Methode istLeer wird meist mit isEmpty bezeichnet.

public class Stapel 
{
	private StapelElement Kopf, Aktuell;

	public Stapel()
	{
		//Konstruktor
	}

	public void push(Object o)
	{
		//legt ein neues Objekt auf den Stapel
	}

	public void pop()
	{
		//löscht das oberste Object des Stapels
	}


	public Object aktuellesElement()
	{
		//Top-Methode
		return Kopf;
	}


	public boolean isEmpty()
	{
		//Test, ob Stapel leer ist
		return true;
	}


}

Aufgaben:

Welche Möglichkeiten gibt es die Klasse Stapel zu implementieren? (Mindestens drei Alternativen!)
Versuchen Sie mit der angegebenen Klassenhülse ein Lösung des Rangierproblems.