SplStack, SplQueue, SplPriorityQueue: SPL-Datenstrukturen praktisch nutzen

1. Warum ein Array nicht immer die richtige Wahl ist

PHP-Arrays sind geordnete Hashmaps mit eingebauter Unterstützung für array_push, array_pop, array_shift und array_unshift. Damit lässt sich technisch jede Stack- oder Queue-Semantik nachbauen, und genau das tun viele Entwickler auch, ohne über die Konsequenzen nachzudenken. Das Problem liegt nicht in der Funktionalität, sondern in zwei Punkten: der Performance bei großen Datenmengen und der fehlenden semantischen Klarheit im Code.

Wer im Code liest array_push($stack, $item), muss aus dem Variablennamen und dem Kontext erschließen, dass hier eine Stack-Semantik gemeint ist. Nichts hindert einen anderen Entwickler daran, versehentlich array_shift auf dieselbe Variable anzuwenden und damit die Reihenfolge stillschweigend zu verändern. Eine SplStack-Instanz dagegen bietet ausschließlich Methoden, die zur Stack-Semantik passen, und macht Fehlanwendungen dieser Art durch die Typsignatur unmöglich.

2. Die gemeinsame Basis: SplDoublyLinkedList

SplStack und SplQueue sind beides Spezialisierungen von SplDoublyLinkedList, einer doppelt verketteten Liste. Jeder Knoten kennt seinen Vorgänger und Nachfolger, wodurch das Einfügen und Entfernen an beiden Enden in konstanter Zeit möglich ist, unabhängig von der Länge der Liste. Das steht im Gegensatz zu einem PHP-Array, das intern zwar ebenfalls über eine Hashtabelle mit verketteten Buckets realisiert ist, bei array_shift jedoch alle numerischen Schlüssel neu indizieren muss.

Diese Neuindizierung ist der eigentliche Kostenpunkt: array_shift entfernt nicht nur das erste Element, sondern verschiebt implizit jeden nachfolgenden numerischen Index um eins nach unten. Bei einem Array mit hunderttausend Elementen bedeutet ein einzelner array_shift-Aufruf damit einen Durchlauf über nahezu die gesamte Struktur. SplQueue umgeht dieses Problem vollständig, weil kein Element seinen Index kennen oder pflegen muss.

$list = new SplDoublyLinkedList();
$list->push('a');
$list->push('b');
$list->unshift('z'); // O(1), kein Reindexing nötig

foreach ($list as $item) {
    echo $item . PHP_EOL; // z, a, b
}

3. SplStack: Undo-Funktionalität sauber implementieren

Ein klassischer Anwendungsfall für einen Stack ist eine Undo-Funktion, etwa in einem Editor für Content-Blöcke oder einem CLI-Tool mit mehreren rückgängig machbaren Schritten. SplStack erweitert die doppelt verkettete Liste um eine LIFO-Iterationsrichtung und die Methoden push, pop und top, die alle in konstanter Zeit arbeiten. Der Code liest sich dadurch fast wie eine Spezifikation, ohne dass man raten muss, welches Ende des Arrays als aktuelles Ende der Historie gilt.

Wichtig ist dabei, dass SplStack Objekte referenziert, keine Kopien anlegt. Wer veränderliche Objekte auf den Stack legt und danach weiter verändert, verändert damit auch den gespeicherten Zustand. Für echte Undo-Historien sollte man daher entweder unveränderliche Zustandsobjekte verwenden oder vor dem Push explizit klonen, sonst zeigt pop() später einen bereits mutierten Zustand statt des ursprünglichen.

final class UndoHistory
{
    private SplStack $stack;

    public function __construct()
    {
        $this->stack = new SplStack();
    }

    public function record(EditorState $state): void
    {
        // Klonen ist Pflicht, sonst zeigt pop() später denselben mutierten Zustand
        $this->stack->push(clone $state);
    }

    public function undo(): ?EditorState
    {
        return $this->stack->isEmpty() ? null : $this->stack->pop();
    }
}

4. SplQueue: FIFO-Verarbeitung ohne Reindizierungskosten

Für eine einfache Task-Queue ohne Priorisierung, etwa das sequenzielle Abarbeiten eingehender Webhook-Events innerhalb eines Requests, bietet sich SplQueue an. Die Klasse erweitert dieselbe doppelt verkettete Liste, stellt aber enqueue und dequeue als semantisch klare FIFO-Methoden bereit. Intern ruft enqueue lediglich push und dequeue lediglich shift auf der Basisklasse auf, beide in konstanter Zeit, ganz ohne die Reindizierungsprobleme eines Arrays.

Ein praktisches Beispiel ist die Verarbeitung mehrerer voneinander abhängiger Import-Batches, bei denen die Reihenfolge garantiert eingehalten werden muss. Statt eines Arrays mit manuellem array_shift in einer Schleife sorgt SplQueue dafür, dass der Code seine Absicht klar ausdrückt und gleichzeitig auch bei tausenden Batches performant bleibt, weil jede einzelne Dequeue-Operation unabhängig von der Restgröße der Queue ist.

$queue = new SplQueue();
foreach ($importBatches as $batch) {
    $queue->enqueue($batch);
}

while (!$queue->isEmpty()) {
    $batch = $queue->dequeue(); // O(1), Reihenfolge bleibt FIFO
    $importer->process($batch);
}

5. SplPriorityQueue: Aufgaben nach Dringlichkeit abarbeiten

Sobald die Verarbeitungsreihenfolge nicht mehr rein zeitlich, sondern von einer Priorität abhängt, kommt SplPriorityQueue ins Spiel. Intern verwendet die Klasse einen Max-Heap, wodurch das Einfügen eines Elements in logarithmischer Zeit und das Entnehmen des Elements mit höchster Priorität ebenfalls in logarithmischer Zeit erfolgt. Ein Array müsste für dasselbe Verhalten entweder bei jedem Insert komplett sortiert werden, was insgesamt quadratisch skaliert, oder bei jedem Extract das Maximum linear suchen.

Praktisch relevant ist das etwa bei einer Job-Queue, in der kritische Systemwartungs-Tasks vor regulären Report-Generierungen abgearbeitet werden sollen, unabhängig davon, in welcher Reihenfolge sie eingereiht wurden. Standardmäßig gibt extract() nur den Wert zurück. Über setExtractFlags() lässt sich das Verhalten so umstellen, dass sowohl Wert als auch Priorität oder ein Array mit beiden Informationen zurückgegeben werden, was in der Praxis fast immer sinnvoller ist.

$queue = new SplPriorityQueue();
$queue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);

$queue->insert('report:monthly', 1);
$queue->insert('maintenance:disk-cleanup', 10);
$queue->insert('report:daily', 3);

while (!$queue->isEmpty()) {
    $item = $queue->extract();
    echo "{$item['data']} (Priorität {$item['priority']})" . PHP_EOL;
}
// Ausgabe: maintenance:disk-cleanup (10), report:daily (3), report:monthly (1)

6. Stabilität bei gleicher Priorität und eigene Vergleichslogik

Ein Detail, das in der Praxis leicht übersehen wird: SplPriorityQueue garantiert bei gleicher Priorität keine stabile Reihenfolge nach Einfügezeitpunkt. Zwei Elemente mit identischer Priorität können in beliebiger Reihenfolge extrahiert werden, weil der zugrunde liegende Heap nur die Priorität als Sortierkriterium kennt. Wer eine deterministische Reihenfolge bei Gleichstand benötigt, sollte die Priorität um eine zweite, feinere Komponente erweitern, etwa einen absteigenden Zeitstempel.

Für komplexere Vergleichslogik lässt sich SplPriorityQueue auch durch eine eigene Unterklasse erweitern, die compare() überschreibt. Das ist etwa dann sinnvoll, wenn die Priorität kein einfacher Integer ist, sondern sich aus mehreren Feldern eines Objekts zusammensetzt. Alternativ bietet sich für reine Min-Heap-Anwendungsfälle die verwandte Klasse SplMinHeap an, während SplMaxHeap dem Standardverhalten von SplPriorityQueue ohne die zusätzliche Prioritätsdimension entspricht.

final class DeterministicPriorityQueue extends SplPriorityQueue
{
    public function compare(mixed $priority1, mixed $priority2): int
    {
        // Bei Gleichstand entscheidet die zweite Komponente (Timestamp)
        return $priority1 <=> $priority2;
    }
}

7. Performance im direkten Vergleich zu Array-Funktionen

Der Unterschied zwischen array_shift und SplQueue::dequeue() wird erst bei realistischen Datenmengen sichtbar. Bei kleinen Listen mit wenigen hundert Elementen ist der Unterschied kaum messbar, weil beide Operationen im Mikrosekundenbereich liegen. Ab einigen zehntausend Elementen zeigt sich jedoch ein klarer Trend: Ein Array, aus dem wiederholt am Anfang entfernt wird, verschlechtert sich mit wachsender Größe linear pro Operation, während SplQueue konstant bleibt.

Wichtig ist die Einschränkung, dass dieser Vorteil ausschließlich Operationen an den Enden betrifft. Für den wahlfreien Zugriff über einen numerischen Index ist ein Array weiterhin klar im Vorteil, weil der Zugriff auf ein Hashtabellen-Element in konstanter Zeit erfolgt, während eine verkettete Liste für denselben Zugriff im schlimmsten Fall die gesamte Liste durchlaufen muss. Die Wahl der Datenstruktur sollte sich also immer am tatsächlichen Zugriffsmuster orientieren, nicht an einer pauschalen Präferenz.

8. Iterationsmodus und Speicherverhalten verstehen

Ein oft übersehenes Detail bei SplDoublyLinkedList und ihren Ableitungen ist der konfigurierbare Iterationsmodus. Über setIteratorMode() lässt sich einstellen, ob die Iteration Elemente entnimmt, also den Stack oder die Queue dabei leert, oder ob sie den Bestand unverändert lässt. Der Standardmodus IT_MODE_LIFO bei SplStack beziehungsweise IT_MODE_FIFO bei SplQueue entfernt standardmäßig keine Elemente, aber die Kombination mit IT_MODE_DELETE ist eine bewusste Option für destruktive Verarbeitung.

In Bezug auf Speicherverbrauch gilt: Eine doppelt verkettete Liste benötigt pro Element zusätzlichen Speicher für die Vorgänger- und Nachfolgerreferenz, während ein PHP-Array intern kompakter organisiert sein kann. Für sehr große, aber selten an den Enden manipulierte Datenmengen kann ein Array daher sogar speichereffizienter sein. Die SPL-Strukturen gewinnen ihren Vorteil gezielt bei häufigen Einfüge- und Entnahmeoperationen an den Enden, nicht als generelle Speicheroptimierung.

9. Entscheidungshilfe: Welche Struktur für welchen Anwendungsfall

In der Praxis lohnt sich SplStack immer dann, wenn eine klare LIFO-Semantik mit häufigen Push- und Pop-Operationen an einer wachsenden Struktur gefragt ist, etwa bei Undo-Historien, Klammer-Validierung in Parsern oder rekursiven Traversierungen, die iterativ statt rekursiv implementiert werden sollen. SplQueue passt dagegen zu FIFO-Szenarien wie sequenzieller Batch-Verarbeitung oder einfachen Warteschlangen ohne Priorisierungsbedarf.

SplPriorityQueue ist die richtige Wahl, sobald eine Rangfolge existiert, die über die reine Einfügereihenfolge hinausgeht, etwa bei Job-Schedulern, Event-Loops mit unterschiedlicher Dringlichkeit oder Dijkstra-ähnlichen Graphalgorithmen. Für kleine, überschaubare Listen mit gemischten Zugriffsmustern bleibt ein normales Array oft die pragmatischste Wahl, weil der zusätzliche Objekt-Overhead der SPL-Strukturen sich erst bei nennenswerter Größe oder häufiger Randmanipulation wirklich auszahlt.

10. Zusammenfassung

11. FAQ: SPL-Datenstrukturen: Das Wichtigste auf einen Blick