prev up next

Previous: Liste Up: Abstrakte Datentypen Next: Schlange

Keller

Def.:
Ein Keller ist eine (ggf. leere) Folge von Elementen zusammen mit einem so genannten (ggf. undefinierten) Top-Element.

Schnittstelle des ADT Keller (Prinzip LIFO: Last in, first out):

empty : Keller $\rightarrow$ boolean liefert true, falls Keller leer ist, false sonst
           
push : Keller $\times$ Objekt $\rightarrow$ Keller legt Element auf Keller
           
top : Keller $\rightarrow$ Objekt liefert oberstes Element
           
pop : Keller $\rightarrow$ Keller entfernt oberstes Element
           

Semantik der Kelleroperationen:

A1)
Ein neu konstruierter Keller ist leer.
A2)
Nach einer Push-Operation ist ein Keller nicht leer.
A3)
Nach einer Push-Pop-Operation ist der Keller unverändert.
A4)
Nach der Push-Operation mit dem Element $x$ liefert die Top-Operation das Element $x$.

Source: Keller.java     JavaDoc: Keller.html    

Implementation eines Kellers mit Verweisen


Implementation eines Kellers mit einem Array (LIFO: Last in, first out)


Source: VerweisKeller.java     JavaDoc: VerweisKeller.html     Die folgenden beiden Beispiele zeigen, dass zum Speichern von Werten aus primitiven Datentypen zunächst das Verpacken der Werte mithilfe der bereits erwähnten Wrapperklassen erforderlich ist. So wird durch den Konstruktor new Integer(i) ein Integer-Objekt erzeugt mit dem (nicht mehr veränderbaren) Wert i. Der Wert dieses Objekts kann über die Methode intValue() ermittelt werden.

Source: Reverse.java     JavaDoc: Reverse.html     Applet:

Source: Klammer.java     JavaDoc: Klammer.html     Applet:

Um die Lesbarkeit der Programme zu erhöhen, soll nun das Einpacken und Auspacken der Wrapper-Klassen-Objekte gekapselt werden. Hierzu leiten wir vom Interface Keller das Interface CharKeller ab und von der Klasse VerweisKeller leiten wir die Klasse VerweisCharKeller ab. Erforderlich wird eine neue Methode ctop(), da Java nicht zwei identische Signaturen mit unterschiedlichem Rückgabewert erlaubt. Getestet wird die Implementation in der Klasse Postfix, welche einen eingelesenen Infix-Ausdruck in die entsprechende Postfix-Notierung überführt.

Source: CharKeller.java     JavaDoc: CharKeller.html    

Source: VerweisCharKeller.java     JavaDoc: VerweisCharKeller.html    

Source: Postfix.java     JavaDoc: Postfix.html     Applet:


prev up next
Previous: Liste Up: Abstrakte Datentypen Next: Schlange