26.5 Der abstrakte Datentyp Keller?
 
 

Ein Keller oder Stapel oder noch anders (engl.) stack ist ein Datentyp der folgende 4 Operationen erlaubt.

  • Man kann fragen, ob er leer ist
  • Man kann auf etwas 'einkellern', oder anders ausgedrückt, man kann etwas auf den Stapel legen. Es ist das oberste Element.
  • Man kann fragen, was das oberste Etwas eines nicht leeren Keller ist.
  • Man kann , wenn der Keller nicht leer ist, das oberste Element vom Keller entfernen.

Es ist leichter sich über Datentyp Keller zu unterhalten, wenn wir einige Abkürzungen einführen. Kürzen wir den Keller mit K und die Dinge, die wir im Keller ablegen können mit e ab. Die 4 oben genannten Operationen heißen isEmpty, push, top und pop.
 

isEmpty() Die Methode isEmpty() liefert true, falls der Keller leer ist, also kein Element enthält und liefert false, falls er nicht leer ist, also bereits Elemente eingekellert sind.
push(e) Mit der Methode push(e) lassen sich Elemente einkellern, also auf den Stapel legen.
top() Die Methode top(): e gibt den Wert des zu oberst auf dem Stapel liegenden Elements aus.
pop() Die Methode pop() schließlich entfernt das zu oberst liegende Element aus dem Keller.
 
  Wir beschreiben also einen Datentyp mitsamt den auf ihm möglichen Operationen, ohne nach der Realisierung zu fragen.  Solche Datentypen nennen wir abstrakt. Der Keller ist also abstrakt, weil wir zunächst nichts darüber aussagen, welchen Typ von Werten wir in ihm ablegen wollen und wie wir die Operationen realisieren.
Keller zum 'Spielen'

In die obere Zeile gibt man die Elemente ein, die man einkellern möchte. Die Kommentare werden im unteren Ausgabefeld angezeigt. 'Einkellern' kann man alles, was man tippen kann. Geben Sie z.B. eine Reihe von Elementen in den Keller ein. Was stellen Sie fest, wenn Sie im Wechsel top und pop ausführen bis der Keller leer ist.

Realisierung Es fällt auf, dass die Keller-Operationen sich in den Methoden von LIFO wieder finden. Dies lässt sich im folgenden Quelltext leicht nachvollziehen. Wir modellieren also eine Klasse Keller, in dem wir auf die Klasse LIFO aus dem Paket listen zugreifen.


Abb.: 25.5.1 UML-Klassendiagramm Keller
 

Download:
Keller.java
package listen.adt;
import listen.*;

public class Keller {
  private LIFO lifo;
  public  Keller(){
    lifo = new LIFO();
  }
  public void push(Object wert){
    lifo.haengeAn(wert);
  }
  public void pop(){
    lifo.loescheElement();
  }
  public Object top(){
    return lifo.getKopfWert();
  }
  public boolean isEmpty(){
    return lifo.isEmpty();
  }
}
API Wir legen die Klasse Keller im Paket listen.adt ab; dabei steht adt für abstrakten Datentyp und Keller.class muss im Verzeichnis adt, einem Unterverzeichnis von listen liegen.
zu 26.6 Übungen
zur Startseite www.pohlig.de  (C) MPohlig 2004