ADT Keller

Der abstrakte Datentyp 'Keller' (engl. 'stack') soll folgendes leisten:

• Ein Keller soll nach seiner Erzeugung leer sein.
• Ein Keller soll Elemente aufnehmen können.
• Ein Keller soll Elemente löschen können.
• Ein Keller soll Elemente ausgeben können, ohne sie dabei aus dem Speicher zu löschen.

Mit diesen Forderungen ist der Datenspeicher soweit beschrieben, dass wir Methoden zur Bedienung des Kellers angeben können. Das macht man in Java am besten in Form eines Interfaces.

public interface Keller {

  public boolean empty(); // liefert true, falls Keller leer, false sonst

  public void push(Object x); // legt Objekt x auf den Keller

  public Object top(); // liefert oberstes Kellerelement

  public void pop(); // entfernt oberstes Kellerelement

}

Keller.java

Beachte:
Hier wird als Typ für ein Kellerelement bewusst der allgemeinste Objekttyp Object benutzt, um das Speichern von Daten eines beliebigen Objekttyps zu ermöglichen. Die Bedienung des Datenspeichers mit push und pop soll ja immer gleich erfolgen, egal was gespeichert wird.

Ein Keller ist ein linearer abstrakter Datentyp. Seine Elemente sind in einer (oft vertikalen) Reihe linear angeordnet. Das Element, das als letztes im Keller gespeichert wurde, ist jeweils oben zu sehen (d.h. würde von top zurückgeliefert) und wird beim nächsten pop als Erstes wieder entfernt. Man spricht von einem LIFO-Speicher (LIFO = last in - first out).

Das Interface legt nur die Funktionalität des Kellers fest, für die eigentliche Implementation gibt es verschiedene Möglichkeiten, die der Anwender gar nicht zu kennen braucht.

Implementation mit Hilfe eines Arrays

Eine Klasse, die das Keller-Interface implementieren möchte, muss alle im Interface festegelegten Methoden in exakt der angegebenen Form implementieren. Als erstes soll der ADT Keller mit Hilfe eines Arrays umgesetzt werden, auch wenn die Größe des Kellers in diesem Fall leider festgelegt werden muss, was eine Obergrenze für die Anzahl der speicherbaren Element bedeutet.

public class ArrayKeller implements Keller {

    Object[] keller;     // Array als Speicher für Kellerelemente
    int topindex;        // Indexposition der nächsten freien Speicherstelle im Keller
   
    public ArrayKeller(){
        topindex = 0;
        keller = new Object[10];
    }
   
    public boolean empty(){
        return topindex==0;        // liefert true, wenn Keller leer, sonst false
    }

    public Object top(){
        if(empty()){
            throw new RuntimeException("Keller.top: Keller leer");
        }
        else {
            return keller[topindex-1];
        }
    }

    public void push(Object o){
        if(topindex<keller.length){
            keller[topindex] = o;
            topindex++;
        }
        else {
            throw new RuntimeException("Keller.push: Keller voll");
        }
    }
   
    public void pop(){
        if (empty()) {
            throw new RuntimeException("Keller.pop: Keller leer");
        }
        topindex--;                
        keller[topindex] = null;
    }

}

ArrayKeller.java

Hier ein kleines Testprogramm für den ArrayKeller, relalisiert in einer neuen Klasse 'ArrayKellerTest':

public class ArrayKellerTest{

  public static void main(String[] argv){

    ArrayKeller k = new ArrayKeller(); // neuen ArrayKeller erzeugen

    k.push("A"); // drei String-Objekte im Keller speichern
    k.push("B");
    k.push("C");

    while(!k.empty()){ // Solange der Keller nicht leer ist...
      System.out.println(k.top()); // oberstes Kellerelement ausgeben
      k.pop(); // oberstes Kellerelement löschen
    }

  }

}

ArrayKellerTest.java

Dynamischer Keller

Der ArrayKeller ist zwar voll funktionsfähig, aber durch den Einsatz eines Arrays fester Größe zur Speicherung der Kellerelemente noch nicht optimal. Nun soll eine dynamische Struktur zum Einsatz kommen.

Eine Variable von einem Objekttyp speichert die Adresse des Speicherbereichs, in dem ihr(e) Wert(e) hinterlegt ist (sind). Man spricht auch von Referenzdatentypen, da sie eine Referenz (einen Bezug) auf einen Speicherbereich enthalten. Eine Referenz wird häufig durch einen Pfeil (Zeiger) symbolisiert. Hat eine Variable von einem Objekttyp leeren Inhalt, speichert sie eben keine Adresse bzw. zeigt nirgendwo hin. Sie hat in diesem Fall den Wert null, symbolisiert durch einen Punkt.

Unsere Kellerelemente sollen nun durch einen eigenen Datentyp 'KellerElement' modelliert werden.

public class KellerElement{
  Object inhalt;
  KellerElement next;
}

Ein Objekt vom Typ KellerElement enthält neben seinem Elementinhalt selbst wieder (einen Zeiger auf) ein KellerElement. Mit diesem Ansatz lässt sich die folgende, verkettete Struktur von KellerElementen aufbauen. Im ZeigerKeller muss man sich nur (in der Variable top) merken, welches das oberste KellerElement ist.

public class ZeigerKeller implements Keller {

  private KellerElement top; // verweist auf oberstes KellerElement

  public ZeigerKeller() { // legt leeren Keller an
    top = null;
  }
 
  public boolean empty() { // liefert true, falls Keller leer ist
    return (top == null);
  }

  public void push(Object x) { // legt Objekt x auf den Keller
    KellerElement hilf = new KellerElement();
    hilf.inhalt = x;
    hilf.next = top;
    top = hilf;
  }

  public Object top() { // liefert Top-Element
    return top.inhalt;
  }

  public void pop() { // entfernt Top-Element
    top = top.next;
  }
 
}

ZeigerKeller.java

Die Klasse 'KellerElement' ist speziell für unseren ZeigerKeller konzipiert. Es gibt vermutlich keine anderen Klassen, die Objekte von Typ KellerElement instanziieren möchten. Aus diesem Grund bietet es sich hier an, die Klasse KellerElement nicht in einer eigenen Datei abzulegen (was natürlich dennoch möglich ist), sondern sie als sogenannte innere Klasse innerhalb der Klasse ZeigerKeller zu implementieren. Eine innere Klasse kann von der umgebenden Klasse ganz normal benutzt benutzt werden. Nun muss allerdings erst ein ZeigerKeller-Objekt existieren, bevor sich ein KellerElement-Objekt erzeugen lässt. Im Code taucht die innere Klasse als eigener Block innerhalb der Klasse ZeigerKeller auf:

public class ZeigerKeller implements Keller {
  
  private class KellerElement{ // innere Klasse
    Object inhalt;
    KellerElement next;
  }
  
  private KellerElement top; // verweist auf oberstes KellerElement

  ...

Zum Testen erzeugt man im Programm ArrayKellerTest einfach einen ZeigerKeller anstelle eines ArrayKellers und schon hat man einen ZeigerKellerTest.

KellerAnwendung 1: Verschiebebahnhof

Auf Gleis A eines Verschiebebahnhofs stehen n Wagons, die beliebige Nummern tragen. Sie sollen mittels einer Lokomotive und eines Hilfsgleises B so auf Gleis C rangiert werden, daß die Wagons in lexikographisch aufsteigender Reihenfolge (von links nach rechts) mit Buchstaben (String-Objekten) bezeichnet sind. Die Lokomotive kann jeweils nur einen Wagon transportieren.

Da die Zugriffe auf die Gleise durch die Lok nur von vorne erfolgen, läßt sich die Datenstruktur KELLER als geeigneter abstrakter Datentyp einsetzen. Für den lexikographischen Vergleich von zwei String-Objekten gibt es in der Klasse String die Methode compareTo.

» drucken: pdf | html