Stack mit einem Array implementieren

Im letzten 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-Collection-Klassen – mit einem Array implementiert.

Im Grunde ist das ganz einfach: Wir legen ein leeres Array an und füllen dieses 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 das Arrays nicht ändern müssen, ist die Implementierung relativ einfach, wie der folgende Java-Code zeigt (Klasse BoundedArrayStack in 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;
  }
}Code-Sprache: Java (java)

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

Implementierung eines Stacks mit einem Array variabler Größe

Stattdessen müssen wir (wenn das Array voll ist):

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

Das folgende Diagramm stellt diese drei Schritte grafisch dar:

All das können wir in Java mit dem Aufruf der Methode Arrays.copyOf() in einem Schritt erledigen. Dazu müssen wir der Methode bloß die gewünschte Größe des neuen Arrays übergeben.

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

Der folgende Code zeigt einen Stack, der initial mit einem Array für zehn Elemente angelegt wird. Bei jedem Aufruf der push()-Methode wird geprüft, ob das Array voll ist. Ist das der Fall, wird die grow()-Methode aufgerufen.

Diese wiederum ruft calculateNewCapacity() auf, um die neue Größe des Arrays zu berechnen. Im Beispiel wird das Array immer um den Faktor 1,5 vergrößert. Im Code ist außerdem eine Maximalgröße für das Array festgelegt. Wenn diese erreicht ist und ein weiteres Element gepusht wird, wird eine Exception geworfen (sofern es nicht schon vorher zu einem OutOfMemoryError kam).

Hier ist der Code (Klasse ArrayStack in 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) {
    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 currentCapacity / 2;
  }

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

}Code-Sprache: Java (java)

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 verkleinern (wir wollen ja nicht übermäßig viel Speicherplatz verschwenden). Versuch doch selbst einmal die Implementierung dahingehend zu erweitern.

Wie BoundedArrayStack und ArrayStack eingesetzt werden können, kannst du dir im Programm StackDemo ansehen.

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.

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.