Stack mit einer Queue implementieren

Im vorherigen Teil dieser Tutorial-Serie ging es darum, wie man einen Stack mit einer verketteten Liste implementiert. In diesem Teil zeige ich dir, wie du einen Stack mit einer Queue implementieren kannst – zuerst mit zwei Queues, dann mit einer einzigen.

Diese Variante hat kaum praktischen Nutzen und wird in erster Linie als Übungsaufgabe verwendet (als Gegenstück gibt es übrigens auch eine Übung zur Implementierung einer Queue mit Stacks). Von daher: Versuch doch einmal selbst auf die Lösung zu kommen!

Zur Erinnerung: Eine Queue ist eine Datenstruktur, bei der du Elemente auf einer Seite einfügst und auf der anderen Seite wieder entnimmst – also eine First-in-First-out-Datenstruktur (FIFO).

Wie können wir damit einen Stack, also eine Last-in-First-out-Datenstruktur (LIFO) implementieren?

Die Lösung – Schritt für Schritt

Das erste Element, das wir auf den Stack schieben (im Beispiel: „apple“), fügen wir in eine Queue ein. Um es vom Stack zu entnehmen, holen wir es wieder aus der Queue:

Das zweite Element können wir nicht einfach auch in diese Queue schreiben. Denn die funktioniert ja nach dem FIFO-Prinzip. Wenn wir „apple“ und dann „orange“ in die Queue schieben, müssen wir auch „apple“ zuerst wieder entnehmen:

Bei einem Stack müssen wir jedoch das zuletzt auf den Stack geschobene Element „orange“ zuerst wieder entnehmen – und nicht den zuerst eingefügten „apple“.

Mit einer Queue allein, in die wir die Elemente nur einfügen, geht das nicht.

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

1. Wir erzeugen eine neue Queue (in der Grafik unten die hellblaue „Neue Queue“) und schieben auf diese das einzufügende Element.
2. Wir verschieben das Element aus der ersten Queue in die neu erstellte Queue.
3. Wir ersetzen die bestehende Queue durch die neue Queue.

Die folgende Grafik zeigt die drei Schritte:

Danach liegen die Elemente so in der Queue, dass wir als erstes das zuletzt eingefügte Element „orange“ entnehmen können und danach das zuerst eingefügte Element „apple“.

Das funktioniert so nicht nur mit zwei Elementen, sondern mit beliebig vielen. Die folgende Grafik zeigt, wie wir ein drittes Element „pear“ auf den Stack schieben. Der zweite Schritt aus der vorherigen Grafik ist hier in die Schritte 2a und 2b aufgeteilt: Zuerst wird „orange“ aus der alten Queue in die neue verschoben, danach „apple“.

Danach können wir die Elemente in Last-in-First-out-Reihenfolge aus dem Stack entnehmen, also erst die zuletzt eingefügte „pear“, dann die „orange“, dann den zuerst eingefügten „apple“.

Quellcode für den Stack mit Queues

Im Folgenden siehst du, dass der Quellcode für die Lösung kurz ist.

Als Queue verwende ich die übliche Queue-Implementierung, ArrayDeque. Dass es sich auch um ein Deque handelt, stört uns nicht, denn wir weisen es ja einer Variablen zu, deren Typ das Queue-Interface ist.

Stack ist das kleine Interface der Tutorial-Serie mit push(), pop(), peek() und isEmpty() (Stack.java auf GitHub) – nicht java.util.Stack.

Du findest den Quellcode in der Klasse QueueStack im GitHub-Repository.

public class QueueStack<E> implements Stack<E> {

  private Queue<E> queue = new ArrayDeque<>();

  @Override
  public void push(E element) {
    Queue<E> newQueue = new ArrayDeque<>();
    newQueue.add(element);

    while (!queue.isEmpty()) {
      newQueue.add(queue.remove());
    }

    queue = newQueue;
  }

  @Override
  public E pop() {
    return queue.remove();
  }

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

  @Override
  public boolean isEmpty() {
    return queue.isEmpty();
  }
}

Die zweite Queue entsteht hier bei jedem push() neu. Du kannst sie genauso gut wiederverwenden: zwei Felder statt einem, und nach dem Umschichten tauschst du die beiden Referenzen.

Das Demo-Programm StackDemo zeigt dir, wie du den QueueStack einsetzen kannst.

Laufzeit

Jeder push() schiebt alle Elemente, die schon im Stack liegen, in die neue Queue. Bei n Elementen sind das n Verschiebungen – push() kostet also O(n). pop(), peek() und isEmpty() greifen nur auf den Kopf der Queue zu und laufen in konstanter Zeit, O(1).

Du kannst die Kosten auch umdrehen: Das neue Element kommt einfach ans Ende der Queue, push() läuft dann in O(1). Dafür muss pop() alle Elemente bis auf das letzte in die zweite Queue schieben, bevor es das letzte entnehmen kann – und kostet O(n), genau wie peek(). Welche Variante besser ist, hängt davon ab, welche Operation seltener vorkommt.

Ein Stack, bei dem push() oder pop() linear mit der Anzahl der Elemente teurer wird, taugt nicht für den produktiven Einsatz. Deshalb bleibt diese Implementierung eine Übungsaufgabe.

Stack mit nur einer Queue

Die zweite Queue ist gar nicht nötig. Es reicht, das neue Element in die Queue einzufügen und anschließend alle anderen Elemente einmal durchzurotieren: jedes am Kopf entnehmen und hinten wieder einfügen – so oft, bis das neue Element am Kopf steht.

Die folgende Grafik zeigt, wie „pear“ auf den Stack mit „apple“ und „orange“ kommt: einmal einfügen, zweimal rotieren.

Die Klasse SingleQueueStack im GitHub-Repository setzt das so um:

public class SingleQueueStack<E> implements Stack<E> {

  private final Queue<E> queue = new ArrayDeque<>();

  @Override
  public void push(E element) {
    queue.add(element);
    for (int i = 1; i < queue.size(); i++) {
      queue.add(queue.remove());
    }
  }

  // pop(), peek(), isEmpty() as in QueueStack
}

Nach dem Einfügen von „apple“, „orange“ und „pear“ liefert queue.toString() die Ausgabe [pear, orange, apple], den Kopf zuerst – genau die Reihenfolge, in der pop() die Elemente zurückgibt. An der Laufzeit ändert sich nichts: push() bleibt bei O(n), es entfällt nur das Anlegen der zweiten Queue.

Ausblick

Im nächsten und letzten Teil des Tutorials behandeln wir eine weitere Übungsaufgabe: Wie kann man einen Stack per Rekursion umkehren?