2.2 Stack (Kellerspeicher/Stapel)

Als Speicherelemente werden hier zunächst Int-Zahlen verwendet, es könnten aber auch Objekte sein.

• Elemente werden mit push(e:Typ) auf den Stapel gelegt.
• Mit pop():Typ wird das oberste Element vom Stapel genommen und zurückgegeben.
• peek():Typ (in Forsa: top():Typ) gibt das oberste Element zurück ohne es aus dem Stapel zu entfernen.
• istLeer():Boolean gibt true zurück, wenn Stapel leer ist
• anzahlElemente():GZ gibt die Anzahl der Elemente zurück
• Stacks werden auch LIFO (Last In First Out) Speicher genannt.

Verwendet man ein Array stapel als Stapelspeicher, muss man wissen wo sich das oberste Element befindet. Dazu wird ein Stackpointer (SP) verwendet, eine Variable, die den Index bzw. die Adresse des obersten Elements bzw. der nächsten freien Speicherstelle beinhaltet. Hier zeigt der SP auf den nächsten freien Index des Arrays, der SP wächst nach unten.
push speichert an die Position stapel[SP] und erhöht SP um eins.
pop erniedrigt SP um eins und gibt den Inhalt von stapel[SP] zurück.

Hinweis: pop() gibt oberstes Element zurück und entfernt es aus dem Stapel, top() gibt oberstes Element zurück ohne es zu entfernen.
Implementieren Sie das Klassendiagramm in Java, ergänzen Sie die Vorgabe.
Testen Sie das Programm.

public class Stapel <Typ>{
  private Knoten <Typ> anfang;
  //public Stapel(){}
  public boolean istLeer(){
    return anfang==null;
  }
  public void push(Typ e){
      Knoten  k = new Knoten(e);
      k.setzeNaechsten(anfang);
      anfang=k;
  }
   public Typ pop(){
     
     return null;
  }
  public Typ top(){
    
     return null;
  }
  public int anzahlElemente(){
     int i = 0;
     
     return i;
  }
  public void ausgebenStapel(){
    if(anfang==null){
        System.out.println("Stack ist leer");
    }
    else{
      System.out.print("Stackinhalt: ");
      Knoten k = anfang;
      while (k!=null){
        System.out.print(k.gibInhalt()+" ");
        k=k.gibNaechsten();
      }
      System.out.println();
    }
  }
}

public class Knoten <Typ>{
  private Typ inhalt;
  private Knoten<Typ> naechster;
  public Knoten(Typ e){
    inhalt = e;    
  }
  public void setzeNaechsten(Knoten <Typ> n){
    naechster = n;
  }
  public Knoten<Typ> gibNaechsten(){
      return naechster;
  }
  public Typ gibInhalt(){
      return inhalt;
  }
}

public class Test{
  public static void teste(){
    System.out.print("\f"); // Konsole leeren
    Stapel<Integer> s = new Stapel();
    s.ausgebenStapel();
    s.push(5);
    s.push(3);
    System.out.println("Anzahl: "+s.anzahlElemente());
    s.ausgebenStapel();
    System.out.println("pop: "+s.pop());
    s.ausgebenStapel();
    System.out.println("pop: "+s.pop());
    System.out.println("pop: "+s.pop());
  }
}