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).

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 Ringbuffer (englisch: "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.

Ringbuffer

Um die Funktionsweise des Ringbuffers 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, aber eine sehr simple, um eine volle von einer leeren Queue zu unterscheiden. Alternativen sind z. B.:

• Man speichert (neben der Anzahl der Elemente) nur den tailIndex oder den headIndex und berechnet den jeweils anderen aus der Anzahl der Elemente (das macht den Code aber deutlich komplexer).
• Man speichert die Anzahl der Elemente nicht und erkennt eine volle Queue daran, dass tailIndex und headIndex gleich sind und dass das Array an der Position tailIndex kein Element enthält.
• Man füllt die Queue nicht komplett, sondern lässt immer mindestens ein Feld frei.

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;
  }
}
Code-Sprache: Java (java)

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();
}Code-Sprache: Java (java)

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.

(Aus Platzgründen in der grafischen Darstellung erhöhen wir die Kapazität nur um zwei Elemente. In der Realität findet man Erweiterungen um Faktor 1,5 oder 2,0.)

Wir müssten diesen freien Platz allerdings zwischen Ende und Anfang der Queue, also innerhalb des Arrays schaffen:

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 Konstrukturen: 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 hat einen ausgefeilteren Algorithmus und stellt sicher, dass eine bestimmte Maximalgröße nicht überschritten wird. 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

}
Code-Sprache: Java (java)

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. Evtl. muss unsere Queue nur bei Lastspitzen eine hohen 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.

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.

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.