Bei dem Stack handelt es sich um eine Datenstruktur, die es ermöglicht Elemente in einem Container zu speichern. Die Elemente werden in diesem Container (Stack) aufeinander gestapelt. Man spricht deshalb auch von einem Stapelspeicher.

Beispiel

Wir haben eine Container, in dem Boxen mit einem Deckel aufeinander gestapelt sind. Da die Boxen aufeinander gestapelt sind, komme ich nur an den Inhalt der obersten Box und nicht an den Inhalt der anderen Boxen. Um an die anderen zu kommen, müsste immer die oberste Box entfernt werden.

Wie im oberen Bild zu erkennen hat jede Box den Namen Node und der Container wird als Stack bezeichnet. Jede Node hat einmal ihren Inhalt und dann die Verbindung zu der Node unter ihr gespeichert. Der Stack kennt nur die oberste Node, die auch head genannt wird.

Möglichkeiten

push fügt ein neues Element als oberste Node in den Stack ein.

pop löscht das oberste Element aus dem Stack.

top gibt den Inhalt des obersten Stapels zurück.

Vorgehen

In der unten stehenden Bidabfolge werden folgende Befehle ausgeführt:

stapel.push("Hallo"); 
stapel.push("Informatik");
stapel.pop(); 
stapel.push("Kurs");

Zuerst wird ein Stapel mit dem head "Hallo" erstellt.

Da man nicht einfach zwischen dem head und dem Stack ein Element einfügen kann, erstellen wir einen zusätzlichen Stack mit dem Namen temp in diesem wird dann die neue Node erstellt.

Im Anschluss wird dann die Node mit Informatik als head und die hallo-Node als Nachfolger von der Informatik-Node festgelegt. Informatik ist nun erfolgreich in den Stack eingefügt worden.

Um nun Informatik wieder aus dem Stack zu entfernen, wird der head auf Hallo gesetzt. Da Informatik nicht mehr erreicht werden kann, wird es durch den GarbageCollector wieder entfernt.

Kurs wird mit dem gleichen Verfahren wie bei Informatik eingefügt.

Mit dem momentanen Status ist nur das oberste Objekt erreichbar. Um Hallo zu erreichen, müsste der head entfernt werden.

Implementierung

Um eine Datenstruktur für verschiedene Datentypen zu schaffen verwenden wir ContentType. Dabei geben wir bei dem Erstellen eines neuen Stacks diesen an, indem wir den Datentyp in kleiner und größer Zeichen schreiben:

Stack<String> stapel = new Stack<>();

Natürlich muss auch diese Form im Kopf der Klasse wieder auftauchen:

public class Stack<ContentType> {}

In einem Methodenaufruf wird dann anstatt der Angabe eines spezifischen Datentypes der ContentType zurückgegeben:

public ContentType top() {}

Methoden

isEmpty()

Wenn head auf kein Element zeigt, so ist auch kein Element in dem Stack vorhanden. isEmpty() ist somit false.

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

top()

Die Methode gibt das oberste Element zurück. Deshalb hat sie als Rückgabewert auch ContentType. Um eine NullPointerException zu vermeiden, wird überprüft, ob der Stack leer ist, da es dann auch keinen Rückgabewert geben kann. In diesem Fall wird dann null zurückgegeben.

public ContentType top() {
    if (head != null) return head.getContent();
    return null;
}

pop()

Die Methode löscht das oberste Element. Genauso wie bei der top() Methode darf der Stack nicht leer sein.

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

Sollte es nur ein Element in dem Stack geben, so liefert head.getNext() als Rückgabewert null. Der Stack wäre damit leer, da head auch auf null zeigt.

push()

push() fügt eine Node vom Typ ContentType an oberster Stelle in den Stack ein. Damit ist die neu eingefügte Node der head. Dafür wird zuerst überprüft, ob der Inhalt nicht null ist, und dann eine neue Node mit dem als Parameter übergebenen Inhalt erstellt. Sollte nun der Stack leer sein, so wir head auf die neue Node gesetzt. Sonst wird head als Nachfolger der neuen Node gesetzt und dann die neue Node auf head.

public void push(ContentType pContent) {
    if (pContent != null) {
        Node<ContentType> n = new Node<ContentType>(pContent);
        if (isEmpty()) head = n;
        else {
            n.setNext(head);
            head = n;
        }
    }
}

Anwendungsbeispiel

Weihnachtsstack

Bei dieser Aufgabe sollte ein Raster erweitert werden, dass einen Weihnachtssack darstellt. Dabei kann der Benutzer seinen jeweiligen Wunsch aufschreiben, und dieser wird dann in dem Weihnachtssack gespeichert. Findet nun die Bescherung statt, so wird immer der oberste Wunsch unter den Weihnachtsbaum gelegt.

Zur Lösung der Aufgabe wird ein Stack benötigt, der die Geschenke speichert. Fügt der Benutzer nun ein Geschenk in den Sack ein, so muss dieses auch in den Stack eingefügt werden:

public void btnWuenschen_ActionPerformed(ActionEvent evt) {
  geschenke.push(txtWunsch.getText());
  lblNaechstesGeschenk.setText(geschenke.top());
} 

Für die Bescherung muss zunächst überprüft werden, ob überhaupt Geschenke in dem Stack vorhanden sind. Sollte das nicht der Fall sein, so bekommt der Weihnachtssack die Aufschrift "leer". Sind allerdings Geschenke in dem Sack vorhanden, so wird das oberste Geschenk aus dem Stack unter den Baum gelegt und aus dem Stack entfernt. Das neue oberste Geschenk wird dann auf den Sack geschrieben, es sei denn der Stack ist leer, dann wird auch auf den Sack "leer" geschrieben. Für die Weihnachtiliche Stimmung wird dann noch eine kurze Soundfile abgespielt.

public void btnKlingeln_ActionPerformed(ActionEvent evt) {
  if(geschenke.isEmpty()) lblNaechstesGeschenk.setText("Leer");
  else{
    lblGeschenkUnterBaum.setText(geschenke.top());
    geschenke.pop();
    lblNaechstesGeschenk.setText(geschenke.top());
  }
  if(geschenke.isEmpty()) lblNaechstesGeschenk.setText("Leer");
  //Sound abspielen
  new Sound("XMasBell.wav").start();
}