Deque mit einem Array implementieren

In diesem Teil der Tutorialserie zeige ich dir, wie man eine Deque mit einem Array implementiert – genauer gesagt: mit einem Ringbuffer (englisch: "circular array").

Wir beginnen mit einem bounded Deque, also einem mit festgelegter Kapazität, und erweitern dieses dann zu einem unbounded Deque, also einem, das unbegrenzt viele Elemente aufnehmen kann.

Falls du den Artikel "Queue mit einem Array implementieren" gelesen hast, wird dir vieles bekannt vorkommen. Denn die Deque-Implementierung ist im Grunde eine Erweiterung der Queue-Implementierung.

Beginnen wir mit dem bounded Deque...

Implementierung eines bounded Deque mit einem Array

Wir beginnen mit einem leeren Array sowie zwei Variablen:

• headIndex – zeigt auf den Kopf des Deques, also das Element, das vom Kopf des Deques als nächstes entnommen werden würde
• tailIndex – zeigt auf ein Feld rechts neben dem Ende des Deques, also das Feld, das am Ende des Deques als nächstes gefüllt werden würde
• numberOfElements – die Anzahl der Elemente im Deque

Wir lassen die Index-Variablen zunächst auf die Mitte des Arrays zeigen, so dass wir ausreichend Platz haben, um sowohl am Kopf als auch am Ende des Deques Elemente hinzuzufügen:

Funktionsweise der Enqueue-Operationen

Um ein Element am Ende des Deques hinzuzufügen, speichern wir es in demjenigen Arrayfeld, auf das tailIndex zeigt; danach erhöhen wir tailIndex um 1.

Die folgende Grafik zeigt das Deque, nachdem wir die Elemente "banana" und "cherry" am Ende des Deques eingefügt haben:

Um ein Element am Kopf des Deques einzufügen, verringern wir headIndex um 1 und speichern das Element dann in demjenigen Arrayfeld, auf das headIndex zeigt.

In der folgenden Grafik siehst du, wie die Elemente "grape", "lemon" und "coconut" (in dieser Reihenfolge) am Kopf des Deques eingefügt wurden:

Funktionsweise der Dequeue-Operationen

Um Elemente zu entnehmen gehen wir genau andersherum vor.

Um ein Element vom Ende des Deques zu entnehmen, verringern wir tailIndex um 1, lesen das Array an Position tailIndex aus und setzen dieses Feld dann auf null.

Die folgende Grafik zeigt das Deque, nachdem wir drei Elemente am Ende ("cherry", "banana", "grape") entnommen haben:

Um ein Element am Kopf des Deques zu entnehmen, lesen wir das Array an Position headIndex aus, setzen das Feld auf null und erhöhen headIndex um 1.

Die folgende Grafik zeigt das Deque, nachdem wir ein Element vom Kopf des Deques ("coconut") entnommen haben:

Damit haben wir die Funktionsweise der vier Grundfunktionen des Deques – Enqueue at front, Enqueue at back, Deque at front und Deque at back – behandelt.

Allerdings könnten wir (ohne zusätzliche Logik) am Kopf des Deques nur noch zwei Elemente hinzufügen, obwohl erst eines von acht Feldern belegt ist. Ebenso könnten wir am Ende des Deques maximal fünf Elemente anhängen.

Um das Deque bis zur Kapazitätsgrenze auffüllen zu können (egal in welcher Richtung), müssen wir aus dem Array einen Ringbuffer (englisch: "circular array") machen.

Wie das funktioniert, erfährst du im nächsten Abschnitt.

Ringbuffer

Um zu zeigen, wie ein Ringbuffer funktioniert, habe ich das Array aus dem vorherigen Beispiel kreisförmig dargestellt:

Um Elemente am Kopf des Deques einzufügen, schreiben wir diese entgegen dem Uhrzeigersinn in das Array. Das folgende Beispiel zeigt, die die Elemente "mango", "fig", "pomelo" und "apricot" an die Positionen 1, 0, 7 und 6 eingefügt wurden:

Wenn wir das Array wieder "flach" darstellen, sieht es wie folgt aus. Der Übersicht halber habe ich am Kopf des Deques einen Pfeil hinzugefügt.

In beiden Darstellungen ist gut erkennbar, dass vor dem Element "fig" an Index 0 das Element "pomelo" an Index 7 steht.

Analog dazu fügen wir Elemente am Ende des Deques ein und entnehmen Elemente. Zusammengefasst gehen wir bei den Operationen wie folgt vor:

• Enqueue at back: erhöhe tailIndex um 1; wenn tailIndex 8 erreicht, setze es auf 0.
• Enqueue at front: vermindere headIndex um 1; wenn headIndex -1 erreicht, setze es auf 7.
• Deque at back: vermindere tailIndex um 1; wenn tailIndex -1 erreicht, setze es auf 7.
• Deque at front: erhöhe headIndex um 1; wenn headIndex 8 erreicht, setze es auf 0.

Die Indexe 8 und 7 gelten für das Beispiel oben. Allgemein verwenden wir elements.length statt 8 und element.length - 1 statt 7.

Volles Deque vs. leeres Deque

Sowohl bei einem vollen als auch bei einem leeren Deque zeigen tailIndex und headIndex auf dasselbe Arrayfeld. Um zu erkennen, ob das Deque voll oder leer ist, speichern wir zusätzlich die Anzahl der Elemente in numberOfElements.

Es gibt noch andere Möglichkeiten, um ein volles von einem leeren Deque zu unterscheiden:

• Wir speichern die Anzahl der Elemente – und den tailIndex oder den headIndex. Den jeweils anderen Index können wir dann durch Addition oder Subtraktion der Anzahl der Elemente berechnen. Diese Variante führt zu komplexerem und schlechter lesbaren Code.
• Wir speichern die Anzahl der Elemente nicht und erkennen ein leeres Deque daran, dass – wenn tailIndex und headIndex identisch sind – das Array an dieser Position leer ist.
• Wir füllen das Deque nicht komplett, sondern lassen mindestens ein Feld frei. Wir verschwenden dabei zwar ein Feld des Arrays, sparen uns dafür aber den Speicherplatz für die numberOfElements-Variable.

Quellcode für das bounded Deque mit einem Array

Die Implementierung des oben beschriebenen Algorithmus ist nicht kompliziert, wie du im folgenden Beispiel-Code sehen wirst. Du findest den Code in der Klasse BoundedArrayDeque im GitHub-Repository.

public class BoundedArrayDeque<E> implements Deque<E> {

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

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

    elements = new Object[capacity];
  }

  @Override
  public void enqueueFront(E element) {
    if (numberOfElements == elements.length) {
      throw new IllegalStateException("The deque is full");
    }
    headIndex = decreaseIndex(headIndex);
    elements[headIndex] = element;
    numberOfElements++;
  }

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

  @Override
  public E dequeueFront() {
    E element = elementAtHead();
    elements[headIndex] = null;
    headIndex = increaseIndex(headIndex);
    numberOfElements--;
    return element;
  }

  @Override
  public E dequeueBack() {
    E element = elementAtTail();
    tailIndex = decreaseIndex(tailIndex);
    elements[tailIndex] = null;
    numberOfElements--;
    return element;
  }

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

  @Override
  public E peekBack() {
    return elementAtTail();
  }

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

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

    return element;
  }

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

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

    return element;
  }

  private int decreaseIndex(int index) {
    index--;
    if (index < 0) {
      index = elements.length - 1;
    }
    return index;
  }

  private int increaseIndex(int index) {
    index++;
    if (index == elements.length) {
      index = 0;
    }
    return index;
  }

  @Override
  public boolean isEmpty() {
    return numberOfElements == 0;
  }
}
Code-Sprache: Java (java)

Bitte beachte, dass BoundedArrayDeque nicht das Deque-Interface des JDK implementiert, sondern ein eigenes, das nur die Methoden enqueueFront(), enqueueBack(), dequeueFront(), dequeueBack(), peekFront(), peekBack() und isEmpty() definiert (s. Deque-Interface im GitHub-Repository):

public interface Deque<E> {
  void enqueueFront(E element);
  void enqueueBack(E element);
  E dequeueFront();
  E dequeueBack();
  E peekFront();
  E peekBack();
  boolean isEmpty();
}Code-Sprache: Java (java)

Wie du BoundedArrayDeque benutzen kannst, siehst du im Demo-Programm DequeDemo.

Implementierung eines unbounded Deque mit einem Array

Wenn unser Deque nicht größenbeschränkt, also unbounded sein soll, wird es etwas komplizierter. Denn dazu müssen wir das Array wachsen lassen. Da das nicht direkt möglich ist, müssen wir ein neues, größeres Array erstellen und die bestehenden Elemente dorthin kopieren.

Dabei müssen wir den Ringbuffer-Charakter des Arrays berücksichtigen. D. h. wir können die Elemente nicht einfach an den Anfang des neuen Arrays kopieren.

Die folgende Grafik (ich habe das Deque aus dem vorherigen Beispiel noch um die Elemente "papaya" am Ende sowie "melon" und "kiwi" am Kopf erweitert) zeigt, was dabei passieren würde:

Die leeren Felder liegen zwar am Ende des Arrays, aber in der Mitte der Elemente des Deques.

Daher müssen wir beim Kopieren in das neue Array entweder die rechten Elemente (also den linken Teil des Deques) an den rechten Rand des neuen Arrays kopieren. Oder wir kopieren die rechten Elemente an den Anfang des neuen Arrays und die linken Elemente (den rechten Teil des Deques) dahinter.

Die folgende Grafik zeigt die zweite Strategie, die im Code einfacher zu implementieren ist:

Somit liegen die leeren Felder vor dem ersten Element ("kiwi") bzw. hinter dem letzten Element ("papaya") des Deques, und wir können auf beiden Seiten das Deques neue Elemente einfügen.

Quellcode für ein unbounded Deque mit einem Array

Im folgenden findest du den Code für ein circular-array-basiertes, unbounded Deque.

Die Klasse hat zwei Konstruktoren: einen, bei dem man die Startkapazität des Deques als Parameter übergeben kann und einen Default-Konstruktor, der die Startkapazität auf zehn Elemente setzt.

Die Methoden enqueueFront() und enqueueBack() prüfen, ob die Kapazität des Deques erreicht ist. Wenn ja, rufen sie die Methode grow() auf. Diese wiederum ruft calculateNewCapacity() auf, um die neue Kapazität zu berechnen, und dann growToNewCapacity(), um die Elemente – wie oben gezeigt – in ein neues, größeres Array zu kopieren.

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

public class ArrayDeque<E> implements Deque<E> {

  private static final int DEFAULT_INITIAL_CAPACITY = 10;

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

  public ArrayDeque() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

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

    elements = new Object[capacity];
  }

  @Override
  public void enqueueFront(E element) {
    if (numberOfElements == elements.length) {
      grow();
    }
    headIndex = decreaseIndex(headIndex);
    elements[headIndex] = element;
    numberOfElements++;
  }

  @Override
  public void enqueueBack(E element) {
    if (numberOfElements == elements.length) {
      grow();
    }
    elements[tailIndex] = element;
    tailIndex = increaseIndex(tailIndex);
    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: from tailIndex to end of old array
    int oldArrayLength = elements.length;
    int numberOfElementsAfterTail = oldArrayLength - tailIndex;
    System.arraycopy(elements, tailIndex, newArray, 0, numberOfElementsAfterTail);

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

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

  // The remaining methods are the same as in BoundedArrayDeque:
  // - dequeFront(), dequeBack(), 
  // - peekFront(), peekBack(), 
  // - elementAtHead(), elementAtTail(), 
  // - decreaseIndex(), increaseIndex(), isEmpty()

}
Code-Sprache: Java (java)

Die in den Kommentaren am Ende des Quellcodes aufgelisteten Methoden gleichen denen des im vorletzten Abschnitt dargestellten BoundedArrayDeque. Daher habe ich hier auf einen erneuten Abdruck verzichtet.

Die calculateNewCapacity()-Methode habe ich hier im Vergleich zum Code auf GitHub stark vereinfacht dargestellt. Die Methode im Repository verdoppelt die Arraygröße solange es kürzer als 64 Elemente ist; danach vergrößert sie es nur noch um Faktor 1,5. Außerdem prüft die Methode, ob eine Maximalgröße für Arrays erreicht ist.

Unser ArrayDeque wächst jetzt, sobald seine Kapazität für ein neues Element nicht mehr ausreicht.

Was es nicht kann, ist wieder zu schrumpfen, wenn sehr viele Elemente wieder entnommen wurden und ein Großteil der Arrayfelder nicht mehr benötigt wird. Gerne überlasse ich dir eine solche Erweiterung als Übungsaufgabe.

Zusammenfassung und Ausblick

Im heutigen Teil der Tutorialserie hast du ein Deque mit einem Array implementiert (genauer gesagt: mit einem Ringbuffer). Schau dir gerne auch einmal den Artikel "Queue mit einem Array implementieren" an – dort findest du eine ähnliche Implementierung für eine Queue.

In den zwei kommenden Teilen der Deque-Serie werde ich noch einmal die Unterschiede zwischen einem Deque und einem Stack bzw. zwischen einem Deque und einer Queue zusammenfassen.

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.