ArrayStack in Java

Intermediate Algorithmen und Datenstrukturen Deutsch

Also available: English

Created by Best · 16.08.2026 at 09:13 UTC

Ein ArrayStack legt Elemente in einem Array ab und hält den Index top. push schreibt an top und erhöht den Index. pop verringert top und liefert den Wert. Die Kapazität ist die Arraylänge.

Vorteil: $O(1)$ amortisierte Operationen und gute Lokalität. Nachteil: feste oder teure Verdopplung der Kapazität.

Implementierungsdetail: top zeigt auf den nächsten freien Slot oder auf das oberste Element. Die Klasse muss das konsequent durchhalten.

Aufgabe: implementiere push und pop für einen int-Stack mit fester Kapazität und Exceptions bei Overflow bzw. Underflow.

Wo gebraucht

Lehr-Implementierung für das, was die JVM intern und was ArrayDeque als Stack-Ersatz liefert. In Produktion eher Deque-Methoden (push/pop am gleichen Ende) statt einer eigenen Array-Klasse, ausser die Aufgabe verlangt Kontrolle über Kapazität und Fehlercodes.

Vertiefung

Ein arraybasierter LIFO-Speicher hält belegte Elemente in einem zusammenhängenden Präfix. size bezeichnet zweckmässig zugleich die Anzahl der Elemente und den nächsten freien Index. Einfügen schreibt zuerst an diese Stelle und erhöht danach den Zähler.

Ist das Array voll, wird ein grösseres Array angelegt und das belegte Präfix kopiert. Einzelne Vergrösserungen sind teuer, treten bei geometrischem Wachstum aber immer seltener auf. Über eine lange Operationsfolge verteilt bleibt die mittlere Zusatzarbeit pro Einfügen beschränkt.

Beim Entfernen sollte die frei gewordene Referenz auf null gesetzt werden. Andernfalls hält das interne Array ein Objekt weiter erreichbar, obwohl es logisch nicht mehr enthalten ist. Das ist kein funktionaler Fehler, kann aber Speicher unnötig binden.

Schwierigkeitsstufen

push, pop und peek mit einer size-Invariante verfolgen.
Geometrisches Wachstum über mehrere Kapazitätsgrenzen analysieren.
Veraltete Referenzen und generische Arrayprobleme in Java erklären.

Fallstricke

Nach dem Verkleinern von size muss die alte Zelle gelöscht werden. Bei generischen Arrays führt ausserdem eine unbedachte Typumwandlung zu Warnungen oder unsicheren Laufzeitfehlern.

University approvals: 0

Tasks

Question 1

Vervollständige ArrayStack: push und pop mit IllegalStateException bei Overflow/Underflow.

Hint

size zählt belegte Slots; data[size-1] ist oben.

public class ArrayStack {
  private final int[] data;
  private int size;

  public ArrayStack(int capacity) {
    data = new int[capacity];
    size = 0;
  }

  public void push(int value) {
    // TODO
  }

  public int pop() {
    // TODO
    return 0;
  }

  public int size() { return size; }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Question 2

Welche Laufzeit haben push und pop bei einem ArrayStack ohne Verdopplung (Kapazität reicht)?

O(1)

O(log n)

O(n)

O(n log n)

Question 3

Warum sollte pop die frei gewordene Arrayzelle auf null setzen?

Damit die Arraykapazität sinkt.

Damit der Index nicht negativ wird.

Damit unbenutzte Referenzen Objekte nicht erreichbar halten.

Damit generische Arrays kovariant werden.

Card Info

Topic: Algorithmen und Datenstrukturen
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy