Umkehrung eines Stacks mit Rekursion

In diesem letzten Teil des Stack-Tutorials zeige ich dir, wie man die Reihenfolge der Elemente eines Stacks ausschließlich per Rekursion (also ohne Iteration) umkehren kann.

Genau wie die Implementierung eines Stacks mit Queues hat auch der in diesem Artikel gezeigte Algorithmus in erster Linie Schulungs-Character. Von daher: Versuch gerne zuerst einmal selbst auf die Lösung zu kommen.

Die Lösung – Schritt für Schritt

Wir lösen die Aufgabe mit zwei Methoden, die ich in den folgenden zwei Abschnitten erklären werde.

1. Die reverse()-Methode

Wir implementieren zunächst eine reverse()-Methode, die wie folgt vorgeht:

Schritt 1:

Solange Elemente auf dem Eingabe-Stack sind, nehmen wir sie vom Stack und rufen die reverse()-Methode rekursiv auf. Dadurch werden alle Elemente vom obersten bis zum untersten Element in den Call Stack verschoben:

Schritt 2:

Beim Ausstieg aus der Rekursion schieben wir die Elemente vom Call Stack zurück auf den Ziel-Stack – aber in umgekehrter Reihenfolge!

Dazu erstellen wir eine Methode insertAtBottom(), welche ein Element am Boden eines Stacks einfügt. (Wie diese Methode funktioniert, siehst du im nächsten Abschnitt.)

Fertig! Der Ziel-Stack enthält die Elemente des Eingabe-Stacks in umgekehrter Reihenfolge.

2. Die insertAtBottom()-Methode

Doch wie fügen wir Elemente am Boden des Stacks ein?

Dazu implementieren wir eine zweite Methode – insertAtBottom(). Auch für diese setzen wir ausschließlich auf Rekursion.

Die folgenden Grafiken zeigen den letzten insertAtBottom()-Aufruf des vorherigen Diagramms. Also den Aufruf, bei dem das Element "peach" am Boden des Ziel-Stacks eingefügt wird. Dieser enthält zu dem Zeitpunkt bereits die Elemente "apple", "orange" und "pear".

Der Einfüge-Vorgang besteht aus drei Schritten:

Schritt 1:

Solange Elemente auf dem Ziel-Stack sind, entnehmen wir diese und rufen insertAtBottom() rekursiv auf. Dadurch werden die Elemente des Ziel-Stacks auf den Call Stack verschoben:

Schritt 2:

Sobald der Ziel-Stack leer ist, wird das Element, das am Boden des Stacks eingefügt werden soll, auf den Ziel-Stack gelegt:

Schritt 3:

Beim Ausstieg aus der Rekursion schieben wir die Elemente vom Call Stack zurück in den Ziel-Stack:

Damit hat die insertAtBottom()-Methode ihre Aufgabe erledigt: Das Element "peach" wurde am Boden des Ziel-Stacks eingefügt.

Quellcode für die Umkehrung eines Stacks per Rekursion

Der Java-Quellcode für die Umkehrung des Stacks besteht aus nur wenigen Zeilen für die zwei Methoden. Du findest den Code in der Klasse Stacks im GitHub-Repo:

public class Stacks {

  public static <E> void reverse(Stack<E> stack) {
    if (stack.isEmpty()) {
      return;
    }
    E element = stack.pop();
    reverse(stack);
    insertAtBottom(stack, element);
  }

  private static <E> void insertAtBottom(Stack<E> stack, E element) {
    if (stack.isEmpty()) {
      stack.push(element);
    } else {
      E top = stack.pop();
      insertAtBottom(stack, element);
      stack.push(top);
    }
  }
}Code-Sprache: Java (java)

Den Klassennamen Stacks habe ich übrigens analog zu Java-Utility-Klassen wie Collections und Arrays gewählt.

Umsetzung mit Default-Methode im Interface

Moderner ist es die Methoden direkt im Stack-Interface zu implementieren:

public interface Stack<E> {

  // ...

  default void reverse() {
    if (isEmpty()) {
      return;
    }
    E element = pop();
    reverse();
    insertAtBottom(element);
  }

  private void insertAtBottom(E element) {
    if (isEmpty()) {
      push(element);
    } else {
      E top = pop();
      insertAtBottom(element);
      push(top);
    }
  }
}

Code-Sprache: Java (java)

Diese Variante findest du nicht im GitHub-Repository, da ich bei der Vorstellung des Stack-Interfaces zu Beginn des Tutorials nicht mit der reverse()-Methode verwirren wollte.

Fazit

Damit endet die Tutorial-Serie zum Thema Stack. Wenn du alle Teile gelesen hast, hast du gelernt, wie ein Stack funktioniert, welche Stack-Implementierungen es im JDK gibt, wie man Stacks auf verschiedene Arten selbst implementiert und – in diesem Artikel – wie man einen Stack per Rekursion umkehren kann.

Wenn dir die Serie gefallen hat, hinterlasse mir gerne einen Kommantar oder teile die Artikel über die Share-Buttons am Ende. Wenn du noch Fragen hast, kannst du sie gerne über die Kommentar-Funktion stellen.

Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.