Stack

Der Stack, zu deutsch Stapel, ist eine dynamische Listenstruktur. Vorstellen kann man sich dies ganz gut wie einen Stapel Klausuren:
Ich kann nur die oberste sehen, sie entfernen, ich kann weitere Klausuren darauf legen und ich kann sehen, ob der Stapel leer ist.
Ich weiß nicht, wie viele Klausuren im Stapel enthalten sind.

Wenn ich eine Klausur auf den Stapel auflege, wird diese schneller aus dem Stapel entfernt werden als die, die unter ihr liegt. Dieses Konzept nennt sich “Last in, First out” (“LIFO”) und charakterisiert den Stapel.

Modellierung

Der Stack lässt sich durch zwei Klassen modellerien: Der Stack verwaltet die Elemente - Er kennt das oberste Element head und stellt alle Zugriffsmethoden bereit. Die Node ist stellt ein Element der Liste dar: Sie hat einen Wert content und zeigt auf das nachfolgende Element.

Ein Stack könnte in etwa so aussehen:

Der head zeigt auf das erste Element mit dem Inhalt “Wert 1”.
Dieses zeigt auf das nächste Element mit dem Inhalt “Wert 2”.

Algorithmen

Die Node ist ganz simpel aufgebaut:

• .getNext() gibt eine Referenz zur nachfolgenden Node zurück
• .setNext() ändert die nachfolgende Node
• .getContent() gibt den Inhalt des Elements zurück

Darüber hinaus gibt es vier Methoden, die den Stack charakterisieren.

isEmpty()

Gibt zurück, ob der Stack leer ist.

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

top()

Gibt den Inhalt des obersten Elements zurück.

ContentType top() {
  if (isEmpty()) return null;

  return head.getContent();
}

Falls der Stack leer ist, wird null zurückgegeben (Z. 2). Sonst wird mit .getContent() der Wert des obersten Elements zurückgegeben.

push()

Fügt dem Stack ein neues Element element hinzu.

void push(ContentType content) {
  if (content == null) return;

  Node element = new Node(content);
  element.setNext(head);
  head = element;
}

Es wird ein neues Element erzeugt (Z. 4). Das aktuell oberste Element wird zu dessen nächsten (Z. 5), das Element wird der neue head (Z. 6).

Je nach Modellierung ist es notwendig, den eingefügten Wert auf Zulässigkeit zu überprüfen (Z. 2).

pop()

Entfernt das oberste Element.

void pop {
  head = head.getNext();
}

Dafür wird einfach der Nachfolger des head zum neuen head.

Besonderheiten

Um die Elemente des Stacks zu betrachten, muss man diese entfernen. Um die Daten nicht zu verlieren, sollte man diese also irgendwo zwischenspeichern.

int size(Stack<String> stack) {
  Stack<String> temp = new Stack<>();
  int i = 0;

  while (!stack.isEmpty()) {
      temp.push(stack.top());
      i++;
      stack.pop();
  }

  // Funktioniert nicht:
  // stack = temp;

  while (!temp.isEmpty()) {
    stack.push(temp.top())
    temp.pop();
  }

  return i;
}

Dies erreicht man mit einem temporären Stack. Nach erfolgreichem Zählen könnte man nun auf die Idee kommen, den Zeiger auf Stack umzubiegen (stack = temp), aber dadurch sind die Elemente in der falschen Reihenfolge (siehe Bild oben). Stattdessen muss man die Elemente wieder “umschichten”, damit sie in der ursprünglichen Reihenfolge erhalten bleiben.

Eine weitere Besonderheit des Stacks: Füge ich zu diesem schneller neue Elemente hinzu, als ich alte entferne, so werde ich die unteren Elemente nie zu Gesicht bekommen.

Snippets

Stack<Integer> temp = new Stack<Integer>();

while (!stack.isEmpty()) {
  // Do something

  temp.push(stack.top());
  stack.pop();
}

while (!temp.isEmpty()) {
  stack.push(temp.top());
  temp.pop();
}

Möchte man über einen Stack iterieren, so ist es wichtig, die Werte zwischenzuspeichern. Dafür kann man einen temporären Stack verwenden (Z. 1) und alle Werte, bevor man sie entfernt (Z. 5), in ihm ablegen (Z. 4). Am Ende muss man diese noch zurück übertragen (Z. 9-12) - sonst ist die Reihenfolge verkehrt.

Nutzungsszenarien

Der Stack ist äußerst hilfreich, um Prozesse zu modellieren. Als Beispiel kann der Klausurenstapel dienen, auch in der Logistik wird das “LIFO”-Prinzip gerne angewendet. Besonders wichtig ist er auch für die Parallelisierung von Arbeitsabläufen: Neue Aufgaben können einfach aufgelegt werden, dann können Arbeiter diese asynchron abarbeiten.

Interessant sind diese dynamischen Listenstrukturen vor allem, weil sie keine vordefinierte Länge haben und somit sehr flexibel einsetzbar sind.

Sämtliche Aktionen auf diesem Array haben konstante Laufzeit, dies macht es sehr effizient.

Sehr zu empfehlen ist die Visualisierung der University of San Francisco: Hier kann man interaktiv erfahren, wie der Stack arbeitet.