Stack mit einem Array implementieren (Java)

Im vorigen Teil haben wir einen Stack als Adapter um ein ArrayDeque geschrieben. In diesem Teil des Tutorials zeige ich dir, wie man einen Stack – ganz ohne Java-Collections-Klassen – mit einem Array implementiert.

Das Prinzip ist einfach: Wir legen ein leeres Array an und füllen es von links nach rechts (also von Index 0 an aufsteigend) mit den auf den Stack gelegten Elementen. Beim Entnehmen der Elemente lesen wir diese von rechts nach links aus dem Array aus (und entfernen sie aus dem Array).

Die folgende Grafik zeigt einen Stack mit einem Array namens elements, das acht Elemente fassen kann. Bisher wurden vier Elemente auf den Stack gelegt.

Die Anzahl der Elemente (nicht die Größe des Arrays) wird in der Variablen numberOfElements gespeichert. Der Wert dieser Variablen zeigt uns, an welcher Position im Array wir ein Element einfügen bzw. auslesen müssen:

• Einfügen: an Position numberOfElements
• Auslesen: an Position numberOfElements - 1

Quellcode für den Stack mit einem Array fester Größe

Solange wir die Größe des Arrays nicht ändern müssen, ist die Implementierung einfach, wie der folgende Java-Code zeigt (Klasse BoundedArrayStack auf GitHub):

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

  private final Object[] elements;

  private int numberOfElements;

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

    elements = new Object[capacity];
  }

  @Override
  public void push(E item) {
    if (numberOfElements == elements.length) {
      throw new IllegalStateException("The stack is full");
    }
    elements[numberOfElements] = item;
    numberOfElements++;
  }

  @Override
  public E pop() {
    E element = elementAtTop();
    elements[numberOfElements - 1] = null;
    numberOfElements--;
    return element;
  }

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

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

    @SuppressWarnings("unchecked")
    E element = (E) elements[numberOfElements - 1];

    return element;
  }

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

pop() setzt den frei gewordenen Platz auf null. Ohne diese Zeile hielte das Array weiter eine Referenz auf das entnommene Element – und der Garbage Collector könnte es nicht freigeben, solange der Stack in Gebrauch ist und kein späteres push() den Platz überschreibt.

Etwas komplizierter wird es, wenn mehr Elemente auf den Stack geschoben werden sollen, als das Array fassen kann. Ein Array kann ja nicht wachsen. Wie es trotzdem geht, zeige ich dir im nächsten Kapitel.

Implementierung eines Stacks mit einem Array variabler Größe

Ist das Array voll, müssen wir:

1. ein neues, größeres Array anlegen,
2. die Elemente des ursprünglichen Arrays in das neue Array kopieren und
3. schließlich das alte Array verwerfen.

Die folgende Grafik zeigt diese drei Schritte für ein volles Array mit sechs Elementen, das auf zwölf Plätze verdoppelt wird:

Die ersten beiden Schritte erledigt in Java ein einziger Aufruf von Arrays.copyOf(): Wir übergeben der Methode das alte Array und die gewünschte Größe des neuen. Den dritten Schritt übernimmt der Garbage Collector, sobald elements auf das neue Array zeigt.

Quellcode für den Stack mit einem Array variabler Größe

Der folgende Code zeigt einen Stack, der anfangs mit einem Array für zehn Elemente angelegt wird. Eine Anfangskapazität unter 1 lehnt der Konstruktor ab, wie schon beim BoundedArrayStack: Für ein leeres Array würde calculateNewCapacity() wieder die Kapazität 0 berechnen – das Array könnte nie wachsen.

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

Die grow()-Methode wiederum ruft calculateNewCapacity() auf, um die neue Größe des Arrays zu berechnen. Solange das Array weniger als 64 Elemente fasst, wird es verdoppelt, danach um den Faktor 1,5 vergrößert – ähnlich wie bei ArrayDeque. Bei der Anfangsgröße von zehn Elementen wächst das Array also auf 20, 40, 80, 120, 180 Plätze usw.

Dass das Array um einen Faktor wächst und nicht um eine feste Zahl von Plätzen, hat einen Grund: Jedes Umkopieren kostet O(n), kommt aber umso seltener vor, je größer das Array wird. Auf alle Aufrufe verteilt braucht push() damit amortisiert konstante Zeit, also O(1). Wüchse das Array dagegen beispielsweise um jeweils zehn Plätze, müsste es alle zehn Aufrufe umkopiert werden – das wäre O(n) pro push().

Im Code ist außerdem eine Maximalgröße für das Array festgelegt: Integer.MAX_VALUE - 8. Das ist derselbe Wert, den das JDK als ArraysSupport.SOFT_MAX_ARRAY_LENGTH verwendet, denn HotSpot lehnt Arrays mit einer Länge nahe Integer.MAX_VALUE mit einem OutOfMemoryError ab – auch wenn genug Heap frei ist. Ist die Maximalgröße erreicht und wird ein weiteres Element gepusht, wirft calculateNewCapacity() eine IllegalStateException (sofern es nicht schon vorher zu einem OutOfMemoryError kam).

Hier ist der Code (Klasse ArrayStack auf GitHub):

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

  public static final int MAX_SIZE = Integer.MAX_VALUE - 8;
  private static final int DEFAULT_INITIAL_CAPACITY = 10;
  private Object[] elements;
  private int numberOfElements;

  public ArrayStack() {
    this(DEFAULT_INITIAL_CAPACITY);
  }

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

    elements = new Object[initialCapacity];
  }

  @Override
  public void push(E item) {
    if (elements.length == numberOfElements) {
      grow();
    }
    elements[numberOfElements] = item;
    numberOfElements++;
  }

  private void grow() {
    int newCapacity = calculateNewCapacity(elements.length);
    elements = Arrays.copyOf(elements, newCapacity);
  }

  static int calculateNewCapacity(int currentCapacity) {
    if (currentCapacity >= MAX_SIZE) {
      throw new IllegalStateException("Can't grow further");
    }

    int newCapacity = currentCapacity + calculateIncrement(currentCapacity);

    if (newCapacity > MAX_SIZE || newCapacity < 0 /* overflow */) {
      newCapacity = MAX_SIZE;
    }

    return newCapacity;
  }

  private static int calculateIncrement(int currentCapacity) {
    return Math.max(1, currentCapacity < 64 ? currentCapacity : currentCapacity / 2);
  }

  // pop(), peek(), elementAtTop(), isEmpty() are the same as in BoundedArrayStack

}

Die Methoden pop(), peek(), elementAtTop() und isEmpty() gleichen denen im oben vorgestellten BoundedArrayStack. Ich habe sie daher nicht noch einmal mit abgedruckt.

Was der ArrayStack in der abgedruckten Form noch nicht kann, ist, das Array auch wieder zu verkleinern (wir wollen ja nicht übermäßig viel Speicherplatz verschwenden). Versuch doch selbst einmal, die Implementierung dahingehend zu erweitern.

Ein Tipp dazu: Halbiere das Array erst, wenn es nur noch zu einem Viertel gefüllt ist. Halbierst du es schon bei halber Füllung, ist es danach voll – und schon das nächste push() kopiert es wieder in ein größeres Array.

Wie du BoundedArrayStack und ArrayStack einsetzt, zeigt das Programm StackDemo.

Ausblick

Im nächsten Teil der Serie lernst du eine Variante kennen, die nicht auf einem Array, sondern auf einer verketteten Liste basiert und damit vollautomatisch bei jedem push() wächst und sich mit jedem pop() wieder verkleinert.