Queue mit zwei Stacks implementieren

In diesem Teil der Tutorial-Serie zeige ich dir, wie du eine Queue mit zwei Stacks implementierst – zuerst auf die einfache Art, bei der jedes Einfügen alle Elemente umschichtet, dann so, wie es die klassische Interviewaufgabe erwartet: mit amortisiert konstanter Laufzeit.

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, das 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 hellblau, beschriftet mit „Temporärer Stack“) 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. Der erste und der dritte Schritt sind hier in 1a/1b und 3a/3b aufgeteilt, denn verschoben wird immer ein Element nach dem anderen:

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 eine Deque-Implementierung wie ArrayDeque verwenden – oder die JDK-Klasse Stack, von der allerdings schon ihre eigene Dokumentation abrät. Warum, liest du in „Java Deque vs. Stack: Warum Deque die bessere Wahl ist“.

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();
  }
}

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();
}

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

Laufzeit

Jede enqueue()-Operation verschiebt alle Elemente, die schon auf dem Stack liegen, auf den temporären Stack und wieder zurück. Bei n Elementen sind das 2 n Verschiebungen – enqueue() kostet also O(n). dequeue(), peek() und isEmpty() greifen nur auf das oberste Element des Stacks zu und laufen in konstanter Zeit, O(1).

Du kannst die Kosten auch umdrehen: Das neue Element kommt einfach oben auf den Stack, enqueue() läuft dann in O(1). Dafür muss dequeue() alle Elemente bis auf das unterste auf den temporären Stack schieben, das unterste entnehmen und die anderen wieder zurückschieben – und kostet O(n), genau wie peek().

Es geht aber besser als in diesen beiden Varianten.

Queue mit zwei Stacks in amortisiert O(1)

Der Trick: Wir behalten beide Stacks dauerhaft und geben ihnen feste Rollen. Auf den Eingabe-Stack legt enqueue() die neuen Elemente. Vom Ausgabe-Stack nimmt dequeue() sie herunter. Nur wenn der Ausgabe-Stack leer ist, schichten wir den gesamten Eingabe-Stack auf den Ausgabe-Stack um – das kehrt die Reihenfolge der Elemente um, und das zuerst eingefügte Element liegt oben.

Die folgende Grafik zeigt das für „banana“, „cherry“ und „grape“:

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

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

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

  @Override
  public void enqueue(E element) {
    inputStack.push(element);
  }

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

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

  @Override
  public boolean isEmpty() {
    return inputStack.isEmpty() && outputStack.isEmpty();
  }

  private void refillOutputStackIfEmpty() {
    if (outputStack.isEmpty()) {
      while (!inputStack.isEmpty()) {
        outputStack.push(inputStack.pop());
      }
    }
  }
}

Ein einzelner dequeue()-Aufruf kann immer noch O(n) kosten – dann nämlich, wenn er den Ausgabe-Stack auffüllen muss. Aber jedes Element wird dabei genau einmal vom Eingabe-Stack genommen und einmal auf den Ausgabe-Stack gelegt; dazu kommen das eine push() beim Einfügen und das eine pop() beim Entnehmen. Mehr als diese vier Stack-Operationen fallen für ein Element nie an, egal wie viele Aufrufe dazwischenliegen. Für eine beliebige Folge von n enqueue()- und dequeue()-Aufrufen sind das zusammen höchstens 4 n Operationen – im Durchschnitt also konstant viele pro Aufruf. Diese Betrachtung nennt man amortisierte Laufzeit: enqueue() und dequeue() laufen in amortisiert O(1).

Genau diese Variante ist die Lösung der bekannten Interviewaufgabe „Implement Queue using Stacks“. Auch mit amortisiert konstanter Laufzeit bleibt sie für die Praxis eine Übungsaufgabe: Eine ArrayDeque leistet dasselbe mit einem einzigen Array und ohne Umschichten.

Ausblick

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