Queue mit einem Array implementieren

Im letzten Teil der Tutorialserie ging es darum, wie man eine Queue mit einer verketteten Liste implementiert. In diesem Teil implementieren wir eine Queue mit einem Array – zunächst eine bounded Queue (also eine mit fester Kapazität) – und dann eine unbounded Queue (also eine, deren Kapazität sich ändern kann). Falls du neu in die Serie einsteigst: Was eine Queue ist und wie das FIFO-Prinzip funktioniert, erklärt der erste Teil.

Beginnen wir mit der einfachen Variante, der bounded Queue.

Implementierung einer bounded Queue mit einem Array

Wir legen ein leeres Array an und füllen dieses von links nach rechts (also von Index 0 an aufsteigend) mit den in die Queue eingefügten Elementen.

Die folgende Grafik zeigt eine Queue mit einem Array namens elements, das acht Elemente fassen kann. Bisher wurden sechs Elemente in die Queue eingefügt. Der tailIndex zeigt immer die nächste Einfügeposition:

Beim Entnehmen der Elemente lesen wir diese ebenfalls von links nach rechts aus und entfernen sie aus dem Array. Der headIndex zeigt dabei immer die nächste Leseposition.

Die folgende Darstellung zeigt die Queue, nachdem wir vier der sechs Elemente wieder entnommen haben:

Da wir nun kurz vor dem Ende des Arrays angekommen sind, könnten wir (ohne zusätzliche Logik) nur noch zwei Elemente in die Queue schreiben. Um die Queue wieder auf acht Elemente aufzufüllen, gibt es zwei Lösungsmöglichkeiten:

1. Wir schieben die verbleibenden Elemente nach links, an den Anfang des Arrays. Diese Operation ist, insbesondere bei großen Arrays, sehr teuer.
2. Die bessere Lösung ist ein Ringpuffer (englisch: „ring buffer“ oder „circular array“). Das bedeutet, dass wir, wenn wir am Ende des Arrays angekommen sind, am Anfang des Arrays fortfahren. Das gilt sowohl für die Schreib- als auch die Leseoperation.

Ringpuffer

Um die Funktionsweise des Ringpuffers zu verdeutlichen, habe ich das Array aus dem Beispiel kreisförmig dargestellt:

Weitere Elemente fügen wir im Uhrzeigersinn ein, im folgenden Beispiel „mango“, „fig“, „pomelo“ und „apricot“ an die Positionen 6, 7 – und dann 0 und 1:

Zurück in der „flachen“ Darstellung sieht das Array nunmehr wie folgt aus:

Sowohl in der Kreisdarstellung als auch in dieser ist gut zu sehen, dass nach dem Element „fig“ an Index 7 das Element „pomelo“ an Index 0 folgt.

Das Entnehmen der Elemente erfolgt analog. Mit jeder Dequeue-Operation wandert der headIndex um eine Position nach rechts, wobei auf die 7 nicht die 8, sondern die 0 folgt.

Volle Queue vs. leere Queue

tailIndex und headIndex liegen sowohl bei einer leeren als auch bei einer vollen Queue auf derselben Position. Damit wir erkennen können, wann die Queue voll ist, speichern wir zusätzlich die Anzahl der Elemente.

So könnte eine volle Queue aussehen:

Und so eine leere (z. B. nachdem aus der eben dargestellten Queue alle acht Elemente entnommen wurden):

Das Speichern der Anzahl der Elemente ist nicht die einzige Möglichkeit, eine volle von einer leeren Queue zu unterscheiden, aber die einfachste. Die beiden anderen Wege – ein Feld immer frei lassen oder den Inhalt des Feldes prüfen, auf das beide Indizes zeigen – und welche Klasse des JDK welchen Weg geht, erkläre ich im Abschnitt „Voll oder leer? Drei Antworten“ des Artikels über den Ringpuffer.

Quellcode für die bounded Queue mit einem Array

Die Implementierung einer bounded Queue mit einem Array ist recht einfach. Du findest den folgenden Code auch in der Klasse BoundedArrayQueue im GitHub-Repository.

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

  private final Object[] elements;
  private int headIndex;
  private int tailIndex;
  private int numberOfElements;

  public BoundedArrayQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }

  @Override
  public void enqueue(E element) {
    if (numberOfElements == elements.length) {
      throw new IllegalStateException("The queue is full");
    }
    elements[tailIndex] = element;
    tailIndex++;
    if (tailIndex == elements.length) {
      tailIndex = 0;
    }
    numberOfElements++;
  }

  @Override
  public E dequeue() {
    final E element = elementAtHead();
    elements[headIndex] = null;
    headIndex++;
    if (headIndex == elements.length) {
      headIndex = 0;
    }
    numberOfElements--;
    return element;
  }

  @Override
  public E peek() {
    return elementAtHead();
  }

  private E elementAtHead() {
    if (isEmpty()) {
      throw new NoSuchElementException();
    }

    @SuppressWarnings("unchecked")
    E element = (E) elements[headIndex];

    return element;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}

In dequeue() setzt die Methode das Feld auf null, bevor sie headIndex weiterrückt. Ohne diese Zeile hielte das Array eine Referenz auf das entnommene Element, bis das Feld überschrieben wird – und der Garbage Collector könnte das Objekt so lange nicht freigeben.

Beachte, dass BoundedArrayQueue nicht das Interface java.util.Queue implementiert, sondern ein eigenes, das nur die vier Methoden enqueue(), dequeue(), peek() und isEmpty() definiert (s. Queue im GitHub-Repository):

public interface Queue<E> {
  void enqueue(E element);
  E dequeue();
  E peek();
  boolean isEmpty();
}

Beide Klassen dieses Artikels sind nicht threadsicher. Eine Array-Queue, die mehrere Threads gleichzeitig benutzen dürfen, ist die ArrayBlockingQueue des JDK.

Wie du die BoundedArrayQueue (und alle anderen Implementierungen des Queue-Interfaces) benutzt, kannst du dir im Programm QueueDemo ansehen.

Implementierung einer unbounded Queue mit einem Array

Etwas komplexer wird die Implementierung für eine unbounded Queue, also eine Queue ohne Größenbeschränkung. Ein Array kann ja nicht wachsen. Und selbst wenn – es dürfte nicht am Ende wachsen, sondern müsste an genau der Stelle freien Platz erzeugen, an der sich tailIndex und headIndex befinden.

Schauen wir uns noch einmal die volle Queue vom Ende des vorherigen Beispiels an:

Um ein weiteres Element einzufügen, müssen wir die Kapazität der Queue erhöhen, indem wir das Array vergrößern.

Der zusätzliche Platz müsste allerdings zwischen Ende und Anfang der Queue entstehen, also innerhalb des Arrays:

Das ist nicht ohne Weiteres möglich. Ein Array kann nicht wachsen – schon gar nicht in der Mitte. Stattdessen müssen wir ein neues Array erzeugen und die bestehenden Elemente dorthinein kopieren.

Wenn wir die Elemente aber ohnehin umkopieren müssen, können wir sie dabei auch in der richtigen Reihenfolge an den Anfang des neuen Arrays kopieren, z. B. so:

Der Code dafür ist gar nicht so kompliziert, wie du im nächsten Abschnitt sehen wirst.

Quellcode für die unbounded Queue mit einem Array

Der folgende Code zeigt die Klasse ArrayQueue aus dem Tutorial-GitHub-Repository.

Es gibt zwei Konstruktoren: einen, bei dem man die initiale Größe des Arrays angeben kann, und einen Default-Konstruktor, der die initiale Kapazität auf zehn setzt.

Bei jedem Aufruf der enqueue()-Methode wird geprüft, ob das Array voll ist. Wenn das der Fall ist, wird die grow()-Methode aufgerufen.

Diese ruft zunächst calculateNewCapacity() auf, um die neue Größe des Arrays zu berechnen. Ich habe diese Methode hier in vereinfachter Form wiedergegeben: Sie multipliziert die aktuelle Größe mit 1,5.

Die calculateNewCapacity()-Methode im GitHub-Repository verdoppelt kleine Arrays, vergrößert Arrays ab 64 Feldern um die Hälfte und überschreitet Integer.MAX_VALUE - 8 nicht – die Grenze, die auch ArrayList und ArrayDeque als Maximalgröße für ihre Arrays ansetzen. Der Fokus dieses Artikels soll jedoch nicht auf der Bestimmung der neuen Größe liegen, sondern auf der eigentlichen Erweiterung des Arrays.

Dazu wird in der Methode growToNewCapacity() das neue Array angelegt, die Elemente an die entsprechenden Positionen im neuen Array kopiert und headIndex sowie tailIndex neu gesetzt.

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

  private static final int DEFAULT_INITIAL_CAPACITY = 10;

  private Object[] elements;
  private int headIndex;
  private int tailIndex;
  private int numberOfElements;

  public ArrayQueue() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

  public ArrayQueue(int capacity) {
    if (capacity < 1) {
      throw new IllegalArgumentException("Capacity must be 1 or higher");
    }

    elements = new Object[capacity];
  }

  @Override
  public void enqueue(E element) {
    if (numberOfElements == elements.length) {
      grow();
    }
    elements[tailIndex] = element;
    tailIndex++;
    if (tailIndex == elements.length) {
      tailIndex = 0;
    }
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = calculateNewCapacity(elements.length);
    growToNewCapacity(newCapacity);
  }

  static int calculateNewCapacity(int currentCapacity) {
    return currentCapacity + currentCapacity / 2;
  }

  private void growToNewCapacity(int newCapacity) {
    Object[] newArray = new Object[newCapacity];

    // Copy to the beginning of the new array: tailIndex to end of the old array
    int oldArrayLength = elements.length;
    int numberOfElementsAfterTail = oldArrayLength - tailIndex;
    System.arraycopy(elements, tailIndex, newArray, 0, numberOfElementsAfterTail);

    // Append to the new array: beginning to tailIndex of the old array
    if (tailIndex > 0) {
      System.arraycopy(elements, 0, newArray, numberOfElementsAfterTail, tailIndex);
    }

    // Adjust head and tail
    headIndex = 0;
    tailIndex = oldArrayLength;
    elements = newArray;
  }

  // dequeue(), peek(), elementAtHead(), isEmpty() are the same as in
  // BoundedArrayQueue

}

Die Methoden dequeue(), peek(), elementAtHead() und isEmpty() gleichen denen in der BoundedArrayQueue aus dem vorletzten Abschnitt. Ich habe sie daher nicht noch einmal mit abgedruckt.

Vielleicht ist dir aufgefallen, dass die Queue zwar wachsen, aber nicht wieder schrumpfen kann. Möglicherweise muss unsere Queue nur bei Lastspitzen eine hohe Zahl von Elementen speichern und würde danach den Speicher mit einem größtenteils leeren Array belegen. Wir könnten die Queue dahingehend erweitern, dass sie nach einer gewissen Karenzzeit ihren Inhalt wieder in ein kleineres Array umkopiert.

Diese Erweiterung überlasse ich dir als Übungsaufgabe.

Zeitkomplexität der Queue mit einem Array

Eine Einführung in das Thema Zeitkomplexität findest du im Artikel „O-Notation und Zeitkomplexität – anschaulich erklärt“.

enqueue() und dequeue() schreiben oder lesen ein Array-Feld und rücken einen Index weiter – unabhängig davon, wie viele Elemente die Queue enthält. Die Zeitkomplexität beider Operationen ist also O(1).

Wächst das Array, kopiert growToNewCapacity() alle Elemente um. Diese eine Operation kostet O(n). Sie fällt aber mit jedem Wachstum seltener an: Nach dem Umkopieren von n Elementen passen n/2 weitere hinein, bevor das Array erneut wächst. Über viele Einfügungen gemittelt bleibt es bei O(1) pro enqueue() – man spricht von amortisiert O(1).

Vor- und Nachteile der Implementierung der Queue mit einem Array

Die Implementierung mit einem Array hat gegenüber der verketteten Liste zwei Vorteile: Die Referenzen auf die Elemente liegen dicht nebeneinander im Array, ohne ein Knoten-Objekt pro Element – das spart Speicher und ist cache-freundlicher als eine Kette von Knoten, die über den Heap verteilt liegen. Und der Garbage Collector hat weniger zu tun, weil er statt einer Kette von Knoten ein einziges Array durchgeht.

Dafür verschwendet ein Array Speicher durch unbelegte Felder – nach einem Wachstum um die Hälfte ist ein Drittel des Arrays leer. Das Umkopieren beim Wachsen kostet Zeit, und die Ringpuffer-Logik macht den Code aufwendiger als die zwei Referenzen der verketteten Liste.

In der Regel überwiegen die Vorteile der Array-Implementierung. Im JDK ist ArrayDeque darum meine Empfehlung für eine Queue in single-threaded Anwendungen – welche Queue sich für welchen Zweck eignet, steht im Abschnitt „Queue-Implementierungen in Java: Welche einsetzen?“ des Artikels über das Queue-Interface.

Ausblick

Im nächsten und gleichzeitig letzten Teil dieser Tutorialserie zeige ich dir, wie man eine PriorityQueue selbst implementiert, und zwar auf Basis eines Min-Heaps.