Queue mit einem Stack implementieren

In diesem Teil der Tutorialserie zeige ich dir, wie man eine Queue mit einem Stack (genauer gesagt: mit zwei Stacks) implementiert.

Diese Variante hat keinen praktischen Nutzen, sondern ist in erster Linie eine Übungsaufgabe. Als solche ist sie das Gegenstück zur Implementierung eines Stacks mit einer Queue.

Zur Erinnerung: ein Stack ist eine Datenstruktur, bei der die Elemente in der umgekehrten Reihenfolge des Einfügens abgerufen werden, also eine Last-in-first-out-Datenstruktur (LIFO).

Wie können wir damit eine Queue, also eine First-in-first-out-Datenstruktur (FIFO) implementieren?

Die Lösung – Schritt für Schritt

Das erste Element, dass wir in die Queue einfügen, legen wir auf einen Stack (im Beispiel: "banana"). Um es aus der Queue zu entnehmen, holen wir es wieder vom Stack:

Mit dem zweiten Element funktioniert das so schon nicht mehr, denn der Stack arbeitet ja nach dem LIFO-Prinzip. Wenn z. B. "banana" und "cherry" auf dem Stack liegen, müssten wir "cherry" als erstes wieder entnehmen:

Bei einer Queue wollen wir jedoch das zuerst eingefügte Element (also "banana") auch als erstes wieder entnehmen.

Das ist mit einem Stack allein nicht möglich.

Stattdessen gehen wir beim Einfügen eines Elements in die Queue wie folgt vor:

1. Wir erzeugen einen temporären Stack (in der Grafik unten orange dargestellt) und verschieben alle Elemente des ursprünglichen Stacks auf den temporären Stack.
2. Wir legen das neue Element auf den ursprünglichen Stack.
3. Wir schieben alle Elemente zurück vom temporären Stack auf den ursprünglichen Stack. Der temporäre Stack wird dann nicht mehr benötigt.

Die folgende Grafik zeigt die drei Schritte:

Danach liegen die Elemente so auf dem Stack, dass wir als erstes das zuerst eingefügte Element "banana" entnehmen können und dann das als zweites eingefügte Element "cherry".

Das funktioniert so nicht nur mit zwei Elementen, sondern mit beliebig vielen. Die folgende Grafik zeigt, wie wir ein drittes Element "grape" in die Queue einfügen:

Danach können wir die Elemente in First-in-First-out-Reihenfolge aus der Queue entnehmen, also erst die zuerst eingefügte "banana", dann die "cherry", und dann die zuletzt eingefügte "grape".

Quellcode für die Queue mit Stacks

Der Quellcode für diesen Algorithmus benötigt nur wenige Zeilen Java-Code.

Als Stack verwende ich den im Stack-Tutorial vorgestellten ArrayStack. Genauso gut könntest du die JDK-Klasse Stack oder eine beliebige Deque-Implementierung, z. B. ein ArrayDeque, verwenden.

Du findest den Code in der Klasse StackQueue im GitHub-Repository.

public class StackQueue<E> implements Queue<E> {

  private final Stack<E> stack = new ArrayStack<>();

  @Override
  public void enqueue(E element) {
    // 1. Move elements from main stack to a temporary stack
    Stack<E> temporaryStack = new ArrayStack<>();
    while (!stack.isEmpty()) {
      temporaryStack.push(stack.pop());
    }

    // 2. Push new element on the main stack
    stack.push(element);

    // 3. Move elements back from temporary stack to main stack
    while (!temporaryStack.isEmpty()) {
      stack.push(temporaryStack.pop());
    }
  }

  @Override
  public E dequeue() {
    return stack.pop();
  }

  @Override
  public E peek() {
    return stack.peek();
  }

  @Override
  public boolean isEmpty() {
    return stack.isEmpty();
  }
}Code-Sprache: Java (java)

Beachte, dass hier nicht das java.util.Queue-Interface implementiert wird. Dieses erbt von java.util.Collection, sodass wir wesentlich mehr Methoden implementieren müssten.

Stattdessen habe ich für dieses Tutorial ein eigenes Queue-Interface geschrieben, das nur die Methoden enqueue(), dequeue(), peek() und isEmpty() definiert:

public interface Queue<E> {
  void enqueue(E element);
  E dequeue();
  E peek();
  boolean isEmpty();
}Code-Sprache: Java (java)

Zum Einsatz der Queue kannst du dir das Demo-Programm QueueDemo ansehen.

Ausblick

Im nächsten Teil des Tutorials erfährst du, wie man eine Queue mit einer verketteten Liste implementiert.

Wenn du noch Fragen hast, stelle sie gerne über die Kommentar-Funktion. Möchtest du über neue Tutorials und Artikel informiert werden? Dann klicke hier, um dich für den HappyCoders.eu-Newsletter anzumelden.