LIFO-Stapel mit Arrays variabler Größe (Algorithmus 1.1)

So geht’s: Oben ein Wort mit push auf den Stapel legen, ein Zufallswort nehmen oder mit pop() das oberste Element herunterholen. Jede Operation läuft danach Schritt für Schritt ab, vor und zurück. Das Array a zeigt alle Plätze bis a.length. Freie Plätze sind gestrichelt, die Leiste darunter zeigt, wie voll es ist. Ist das Array voll, zieht der Stapel um: Darunter erscheint das neue, doppelt so große Array, und jede einzelne Kopie ist ein eigener Schritt. Beim pop() geht es umgekehrt, sobald nur noch ein Viertel belegt ist. „for (x : stapel)“ zeigt den Iterator, der von oben nach unten läuft. Das „Buchbeispiel“ spielt die Eingabe to be or not to - be - - that - - - is ab, jedes Wort ist ein push, jeder Strich ein pop(). Der Zähler rechnet mit, wie viele Kopien im Schnitt auf eine Operation kommen.

Erklärung

LIFO-Stapel mit Arrays variabler Größe (Algorithmus 1.1), Klasse ResizingArrayStack. Ein Stack (Last In, First Out): Was zuletzt draufgelegt wurde, kommt zuerst wieder runter. Das Besondere ist, dass das Array mitwächst und mitschrumpft.

Aufbau:

• a[] hält die Elemente, N zählt sie. Das oberste Element liegt in a[N-1].
• Generisch über Item, also für jeden Typ nutzbar.
• (Item[]) new Object[1]: Java erlaubt kein new Item[] bei generischen Typen, daher der Umweg über Object[] mit Cast.

Die Operationen:

• push(item): Ist das Array voll (N == a.length), wird es per resize(2*a.length) verdoppelt. Dann a[N++] = item.
• pop(): Oberstes Element holen mit a[--N], Platz auf null setzen (gegen Loitering, wie in [12]). Ist das Array danach nur noch zu einem Viertel gefüllt, wird es per resize(a.length/2) halbiert.
• resize(max): Neues Array der Größe max anlegen und alle N Elemente umkopieren.

Warum Viertel und nicht Hälfte? Würde man schon bei halb voll halbieren, könnte ein Wechsel von push/pop genau an der Grenze ständig verdoppeln und halbieren, jedes Mal mit komplettem Umkopieren (Thrashing). Mit der Viertel-Regel ist das Array nach dem Halbieren wieder halb voll, also mit Puffer in beide Richtungen.

Kosten:

• Einzelne push/pop sind meist konstant. Ein resize kostet N, kommt aber so selten vor, dass es sich verteilt: amortisiert konstante Zeit pro Operation.
• Speicher: Das Array ist immer zwischen 25 % und 100 % gefüllt, also nie mehr als viermal so groß wie nötig.

Iterator:

• implements Iterable<Item> erlaubt for (Item x : stack).
• ReverseArrayIterator läuft von N-1 runter auf 0, also von oben nach unten im Stapel, passend zu LIFO.
• remove() bleibt leer, weil Entfernen beim Iterieren nicht unterstützt wird.

Einordnung: Das ist das Grundmuster, das später überall auftaucht, auch die Heap-Vorrangwarteschlange [12] könnte statt des festen maxN genau dieses Resizing nutzen. Darauf verweist der Text dort mit Übung 2.4.19.