Ds\Stack — Klasse · PHP-Referenz

Signatur

class Ds\Stack implements Ds\Collection

Beschreibung

Ds\Stack ist eine Datenstruktur, die das LIFO-Prinzip (Last In, First Out) implementiert: Das zuletzt eingefügte Element wird als erstes wieder entnommen. Die Klasse ist Teil der Data Structures-Erweiterung (ext-ds) und bietet gegenüber Array-basierten Stapeln mit array_push/array_pop eine typsichere, speichereffizientere und semantisch klarere Alternative.

Intern basiert Ds\Stack auf einem Ds\Vector, was Einfüge- und Entnahmeoperationen am Ende in amortisierter O(1)-Zeit ermöglicht. Der Zugriff per Index oder eine Iteration über beliebige Positionen ist bewusst nicht vorgesehen – der Stack soll ausschließlich über seine Stapel-Schnittstelle (push, pop, peek) genutzt werden.

Typische Einsatzgebiete sind Aufruf-Stacks, Undo-/Redo-Mechanismen, das Auswerten von Ausdrücken (z. B. beim Parsen), die Tiefensuche in Graphen sowie überall dort, wo die Verarbeitungsreihenfolge umgekehrt zur Einfügereihenfolge sein muss.

Hinweis: Die Erweiterung muss separat installiert werden (pecl install ds). Sie steht nicht standardmäßig in PHP zur Verfügung.

Beispiele

Grundlegende Verwendung: Push, Peek und Pop

<?php
// Erweiterung laden (falls nicht auto-loaded)
// extension=ds

$stack = new Ds\Stack();

$stack->push('Erster');
$stack->push('Zweiter');
$stack->push('Dritter');

echo 'Oberster Eintrag (peek): ' . $stack->peek() . PHP_EOL;
echo 'Anzahl Elemente: ' . $stack->count() . PHP_EOL;

while (!$stack->isEmpty()) {
    echo $stack->pop() . PHP_EOL;
}

Oberster Eintrag (peek): Dritter Anzahl Elemente: 3 Dritter Zweiter Erster

Undo-Mechanismus für eine einfache Text-Bearbeitung

<?php

$history = new Ds\Stack();
$text = '';

$applyChange = function (string $newText) use (&$text, $history): void {
    $history->push($text); // alten Zustand speichern
    $text = $newText;
};

$undo = function () use (&$text, $history): void {
    if ($history->isEmpty()) {
        echo 'Nichts zum Rückgängigmachen.' . PHP_EOL;
        return;
    }
    $text = $history->pop();
};

$applyChange('Hallo');
$applyChange('Hallo Welt');
$applyChange('Hallo Welt!');

echo 'Aktuell: ' . $text . PHP_EOL; // Hallo Welt!

$undo();
echo 'Nach Undo: ' . $text . PHP_EOL; // Hallo Welt

$undo();
echo 'Nach Undo: ' . $text . PHP_EOL; // Hallo

$undo();
echo 'Nach Undo: ' . $text . PHP_EOL; // (leer)

Aktuell: Hallo Welt! Nach Undo: Hallo Welt Nach Undo: Hallo Nach Undo:

Stack aus einer bestehenden Sammlung initialisieren

<?php

// Ds\Stack akzeptiert ein iterierbares Argument im Konstruktor
$stack = new Ds\Stack([10, 20, 30]);

// Achtung: die Reihenfolge beim Pop ist LIFO bezogen auf die interne Speicherung
while (!$stack->isEmpty()) {
    echo $stack->pop() . PHP_EOL;
}

30 20 10

// Wichtig · Fallstricke

Kein Index-Zugriff: Im Gegensatz zu Arrays erlaubt Ds\Stack keinen direkten Zugriff per Index ($stack[0]). Versuche, dies zu tun, führen zu einem Fehler. Das ist beabsichtigt, um die Stapel-Semantik zu erzwingen.

pop() auf leerem Stack: Ein Aufruf von pop() oder peek() auf einem leeren Stack wirft eine UnderflowException. Prüfe vorher mit isEmpty().

Speicher freigeben: Mit clear() werden alle Elemente entfernt und der interne Speicher freigegeben. Die Kapazität kann mit allocate() vorab reserviert werden, um häufige Reallokatierungen zu vermeiden.

Serialisierung: Ds\Stack implementiert Serializable und kann mit serialize()/unserialize() persistiert werden. json_encode() gibt die Elemente als JSON-Array in LIFO-Reihenfolge aus.

Siehe auch

Ds\Queue Ds\Deque Ds\Vector Ds\Collection SplStack