Stack

Funktionsweise

"Ein Stapel (Stack) kann eine beliebige Menge von gleich langen Informationsstrukturen (Objekte) aufnehmen und gibt diese, in entgegengesetzter Reihenfolge zur Aufnahme, wieder zurück." (Wikipedia)

Schnittstellenbeschreibung (Zentralabitur)

Download als PDF: Stack Schnittstellenbeschreibung (PDF)

Konstruktor Stack()

Ein leerer Stapel wird erzeugt. Objekte, die in diesem Stapel verwaltet werden, müssen vom Typ ContentType sein.

Anfrage isEmpty(): boolean

Die Anfrage liefert den Wert true, wenn der Stapel keine Objekte enthält, sonst liefert sie den Wert false.

Auftrag push (ContentType pContent)

Das Objekt pContent wird oben auf den Stapel gelegt. Falls pContent gleich null ist, bleibt der Stapel unverändert.

Auftrag pop()

Vorher: Der Stapel ist nicht leer.

Nachher: Das zuletzt eingefügte Element ist aus dem Stapel entfernt.

Anfrage top(): ContentType

Die Anfrage liefert das oberste Stapelobjekt. Der Stapel bleibt unverändert. Falls der Stapel leer ist, wird null zurückgegeben.

Veranschaulichung: Stapel von Spielkarten

Einen Stack kann man sich als einen Stapel von Spielkarten vorstellen. Für den Kartenstapel sind folgende Handlungen möglich:

• Die oberste Karte anschauen: Methode top()
• Die oberste Karte wegnehmen: Methode pop()
• Auf den Stapel eine Karte drauflegen: Methode push(neueKarte)
• Man kann abfragen, ob der Stapel überhaupt eine Karte enthält: Methode isEmpty()

Objektdiagramm eines Stacks

Der Stack selber hat also nur das eine Attribut head, er "kennt" also eigentlich nur den obersten Knoten. Dies reicht aus, da Stack-Operationen (Knoten anschauen, hinzufügen, löschen) immer nur oben möglich sind und die StackNodes untereinander ja verbunden sind (jeder StackNode hat ein Attribut nestNode, in dem eine Referenz auf das darunter liegende StackNode-Objekt gespeichert ist).

Implementierung

Für die Implementierung der Klasse Stack wird die interne Klasse StackNode benutzt.

 public class Stack<ContentType> {
       // der oberste Node eines Stacks
       private StackNode head;
        
       public Stack() {
          head = null;
       }

       public boolean isEmpty() {
          return (head == null);
       }

       public void push(ContentType pContent) {
          if (pContent != null) {
             StackNode node = new StackNode(pContent);
             node.setNext(head);
             head = node;
          }
       }

       public void pop() {
          if (!isEmpty()) {
             head = head.getNext();
          }
       }

       public ContentType top() {
          if (!this.isEmpty()) {
             return head.getContent();
          } else {
          return null;
          }
       }
 }

Verwendung von Stacks

Um mit den Elementen eines Stacks sinnvoll arbeiten zu können, muss man sie nach und nach vom Stack "runternehmen".

Damit man den Stack dabei nicht zerstört, muss man die runtergenommenen Elemente auf einen Hilfs-Stack ablegen und nach der Bearbeitung wieder zurückschichten.

Klassendiagramm der Klasse Buch

Die Verwendung von Stacks wird hier aufgezeigt für Stacks, die Objekte vom Typ Buch enthalten (vgl. Klassendiagramm rechts)

Beispiel: Methode Anzahl

public int anzahl(Stack<Buch> pStack){
   Stack<Buch> hilfsStack = new Stack<>();                     
   int ergebnis = 0;                                   
   while(pStack.isEmpty() == false){
      Buch oberstesBuch = pStack.top();
      hilfsStack.push(oberstesBuch);
      ergebnis++;                       
      pStack.pop();
   }
   while(hilfsStack.isEmpty() == false){
      Buch oberstesBuch = hilfsStack.top();
      pStack.push(oberstesBuch);
      hilfsStack.pop();
   }
 }

Methode Enthaelt

public boolean enthaelt(Stack<Buch> pStack, Buch pBuch){
   boolean ergebnis = false;
   Stack<Buch> hilfsStack = new Stack<>();
   while (pStack.isEmpty() == false) {
      Buch oberstesBuch = pStack.top();
      if (oberstesBuch.getTitel().equals(pBuch.getTitel())) {
         ergebnis = true;
      }
      hilfsStack.push(oberstesBuch);
      pStack.pop();
   }
   // Buecher auf pStack zurueck legen
   while (!hilfsStack.isEmpty()) {
      Buch oberstesBuch = hilfsStack.top();
      pStack.push(oberstesBuch);
      hilfsStack.pop();
   }
   return ergebnis;
}

Methode Löschen

public void loeschen(Stack<Buch> pStack, Buch pBuch) {
   Stack<Buch> hilfsStack = new Stack<>();
   while (!pStack.isEmpty()) {
      Buch oberstesBuch = pStack.top();
      if (oberstesBuch.getTitel().equals(pBuch.getTitel())) {
         pStack.pop();
      }
      hilfsStack.push(oberstesBuch);
   }
   while (!hilfsStack.isEmpty()){
      Buch oberstesBuch = hilfsStack.top();
      pStack.push(oberstesBuch);
      hilfsStack.pop();
   }
}

Methode Unterstes Element

Die folgende Methode löscht das unterste Buch aus einem Stack und gibt es zurück.

public Buch unterstesBuch(Stack<Buch> pStack){
   Stack<Buch> hilfsStack = new Stack<>();
   while (!pStack.isEmpty()) {
      hilfsStack.push(pStack.top());
      pStack.pop();
   }
   Buch dasUnterste = hilfsStack.top();
   while (!hilfsStack.isEmpty()) {
      pStack.push(hilfsStack.top());
      hilfsStack.pop();
   }
   return dasUnterste;
}

Methode Buch unten einfügen

public void buchUntenEinfuegen(Stack<Buch> pStack, Buch pBuch){
   Stack<Buch> hilfsStack = new Stack<>();
   while (!pStack.isEmpty()) {
      hilfsStack.push(pStack.top());
      pStack.pop();
   }
   pStack.push(pBuch);
   while (!hilfsStack.isEmpty()) {
      pStack.push(hilfsStack.top());
      hilfsStack.pop();
   }
}

Methode mischen

public Stack<Buch> mischen(Stack<Buch> s1, Stack<Buch> s2){
   Stack<Buch> ergebnis= new Stack<>();
   while (!s1.isEmpty() && !s2.isEmpty()){
      ergebnis.push(s1.top());
      s1.pop();
      ergebnis.push(s2.top());
      s2.pop();
   }
   // jetzt den Rest von s1 (wenn es einen gibt)
   while (!s1.isEmpty()){
      ergebnis.push(s1.top());
      s1.pop();
   }
   // jetzt den Rest von s2 (wenn es einen gibt)
   while (!s2.isEmpty()){
      ergebnis.push(s2.top());
      s2.pop();
   }
   return ergebnis;
}