PHP SplStack: Stapel und Warteschlangen richtig nutzen

Ein Stapel Teller beschreibt das Prinzip besser als jede Definition: der zuletzt abgelegte Teller liegt oben und wird zuerst wieder heruntergenommen. Genau dieses Verhalten bildet PHP SplStack ab, eine Klasse aus der Standardbibliothek, die eine Reihenfolge nicht nur erlaubt, sondern zusichert.

Bevor die erste Methode fällt, lohnt ein Blick darauf, wofür man so etwas überhaupt braucht.

Was ist ein Stapel und wofür braucht man ihn?

Ein Stapel arbeitet nach dem Prinzip "zuletzt hinein, zuerst heraus", abgekürzt LIFO. Das klingt akademisch, begegnet aber jedem täglich. Die Zurück-Funktion im Browser ist ein Stapel: die zuletzt besuchte Seite kommt zuerst zurück. Die Rückgängig-Funktion in einem Editor ist ein Stapel. Und wenn PHP eine Funktion aufruft, die eine andere aufruft, verwaltet die Sprache das intern ebenfalls als Stapel.

Das Gegenstück ist die Warteschlange, die nach dem Prinzip "zuerst hinein, zuerst heraus" arbeitet. Wer an der Kasse ansteht, kennt das Verfahren. Aufträge, die der Reihe nach abgearbeitet werden, gehören in eine Warteschlange, nicht auf einen Stapel.

Beide Strukturen lassen sich mit einem gewöhnlichen Array nachbauen, und genau das tun die meisten PHP-Projekte auch. Was PHP SplStack hinzufügt, ist zweierlei: die Reihenfolge steht im Klassennamen statt in einem Kommentar, und das Entfernen am Anfang wird nicht langsamer, wenn die Sammlung wächst. Der zweite Punkt ist der interessantere, und er kommt weiter unten mit einer Messung.

PHP SplStack erzeugen und benutzen

PHP SplStack gehört zur Standard PHP Library und ist ohne Erweiterung verfügbar. Drei Methoden genügen für den Anfang: push() legt ab, pop() nimmt herunter, top() schaut nach, ohne etwas zu entfernen.

<?php

$stapel = new SplStack();



$stapel->push('Seite A');

$stapel->push('Seite B');

$stapel->push('Seite C');



echo $stapel->top();     /* Seite C, bleibt liegen */

echo $stapel->pop();     /* Seite C, wird entfernt */

echo count($stapel);     /* 2 */

Dass count() funktioniert, liegt am Interface Countable, das die Klasse mitbringt. Über ArrayAccess ist zusätzlich der Klammerzugriff möglich. Wie solche Verträge in PHP aufgebaut sind, erklärt das Tutorial zu PHP Interfaces im Detail.

Die Warteschlange funktioniert genauso, nur mit sprechenderen Namen und umgekehrter Reihenfolge.

<?php

$warteschlange = new SplQueue();



$warteschlange->enqueue('Auftrag 1');

$warteschlange->enqueue('Auftrag 2');

$warteschlange->enqueue('Auftrag 3');



echo $warteschlange->dequeue();   /* Auftrag 1, zuerst hinein */

echo $warteschlange->dequeue();   /* Auftrag 2 */

Beide Klassen sehen sich nicht nur ähnlich, sie sind tatsächlich eng verwandt.

PHP SplStack, SplQueue und SplDoublyLinkedList im Vergleich

Unter beiden liegt dieselbe Basisklasse. SplDoublyLinkedList ist eine doppelt verkettete Liste, die an beiden Enden arbeiten kann. PHP SplStack und SplQueue erben davon und legen lediglich fest, in welcher Richtung iteriert wird und welche Methodennamen zusätzlich zur Verfügung stehen.

Die letzte Zeile ist ernst gemeint, und sie führt direkt zur wichtigsten Frage dieses Tutorials.

Warum nicht einfach ein Array?

Ein Array ist vertraut, braucht kein Objekt und funktioniert mit allen array_*-Funktionen. Für einen Stapel gibt es zudem array_push() und array_pop(), und beide arbeiten am Ende des Arrays, wo sie schnell sind. Wer nur einen Stapel braucht, gewinnt mit PHP SplStack vor allem Lesbarkeit.

Anders sieht es bei der Warteschlange aus. array_shift() entfernt das erste Element und vergibt anschliessend alle numerischen Schlüssel neu, damit die Lücke am Anfang verschwindet. Bei zehn Einträgen fällt das nicht auf, bei 50.000 sehr wohl: jeder einzelne Aufruf berührt den gesamten Rest. SplQueue::dequeue() hängt dagegen nur einen Verweis um.

<?php

$anzahl = 50000;



$array = range(1, $anzahl);

$start = microtime(true);

while ($array !== []) {

    array_shift($array);          /* vergibt alle Schluessel neu */

}

printf("array_shift: %.3f s\n", microtime(true) - $start);



$queue = new SplQueue();

for ($i = 1; $i <= $anzahl; $i++) {

    $queue->enqueue($i);

}

$start = microtime(true);

while (!$queue->isEmpty()) {

    $queue->dequeue();

}

printf("dequeue: %.3f s\n", microtime(true) - $start);

Wer dieses Skript laufen lässt, sieht einen Unterschied von mehreren Grössenordnungen, und er wächst mit der Anzahl weiter. Wie sich solche Messungen sauber aufsetzen lassen, zeigt das Tutorial zu PHP microtime.

Beim Speicherverbrauch gibt es übrigens nichts zu gewinnen. Ein Objekt mit verketteter Liste braucht eher mehr Platz als ein einfaches Array. Der Vorteil liegt bei der Laufzeit des Entfernens und bei der Ausdruckskraft, nicht beim Speicher.

Praxis: ein Undo-Speicher mit PHP SplStack

Der anschaulichste Einsatz ist eine Rückgängig-Funktion. Vor jeder Änderung wandert der bisherige Zustand auf den Stapel, und pop() holt ihn zurück.

<?php

class Editor

{

    private SplStack $verlauf;

    private string $text = '';



    public function __construct()

    {

        $this->verlauf = new SplStack();

    }



    public function schreibe(string $neu): void

    {

        $this->verlauf->push($this->text);

        $this->text = $neu;

    }



    public function zurueck(): void

    {

        if ($this->verlauf->isEmpty()) {

            return;

        }

        $this->text = $this->verlauf->pop();

    }



    public function text(): string

    {

        return $this->text;

    }

}



$editor = new Editor();

$editor->schreibe('Erste Fassung');

$editor->schreibe('Zweite Fassung');

$editor->zurueck();



echo $editor->text();   /* Erste Fassung */

Die Abfrage mit isEmpty() ist kein Schmückwerk. Ein pop() auf einem leeren Stapel wirft eine RuntimeException und liefert kein null zurück.

Praxis: Baum durchlaufen ohne Rekursion

Der zweite klassische Einsatz von PHP SplStack ist das Durchlaufen verschachtelter Strukturen. Statt sich rekursiv aufzurufen und dabei irgendwann an die Grenze zu stossen, verwaltet die Schleife die offenen Knoten selbst.

<?php

$baum = [

    'name' => 'Wurzel',

    'kinder' => [

        ['name' => 'Technik', 'kinder' => [

            ['name' => 'PHP', 'kinder' => []],

        ]],

        ['name' => 'Sport', 'kinder' => []],

    ],

];



$stapel = new SplStack();

$stapel->push($baum);



while (!$stapel->isEmpty()) {

    $knoten = $stapel->pop();

    echo $knoten['name'] . "\n";



    foreach ($knoten['kinder'] as $kind) {

        $stapel->push($kind);

    }

}

Der Vorteil gegenüber der Rekursion ist die Kontrolle. Die Tiefe ist nur durch den verfügbaren Speicher begrenzt, und die Schleife lässt sich jederzeit anhalten oder fortsetzen. Genau dieses Muster steckt hinter jedem Verzeichnisdurchlauf und jedem Kategorienbaum.

Bevor das in den Produktivcode geht, gibt es allerdings eine Überraschung, die fast jeden einmal erwischt.

Die foreach-Falle bei PHP SplStack

Ein foreach über PHP SplStack läuft rückwärts. Das ist logisch, weil ein Stapel von oben abgetragen wird, überrascht aber jeden, der die Einfügereihenfolge erwartet. Bei SplQueue ist es genau umgekehrt.

<?php

$stapel = new SplStack();

$stapel->push('A');

$stapel->push('B');

$stapel->push('C');



foreach ($stapel as $eintrag) {

    echo $eintrag;      /* CBA, zuletzt abgelegt zuerst */

}

echo count($stapel);    /* 3, der Stapel bleibt vollstaendig */



$warteschlange = new SplQueue();

$warteschlange->enqueue('A');

$warteschlange->enqueue('B');

$warteschlange->enqueue('C');



foreach ($warteschlange as $eintrag) {

    echo $eintrag;      /* ABC, in Einfuegereihenfolge */

}

Anders als oft behauptet wird der Stapel dabei nicht geleert. Der voreingestellte Iteratormodus ist IT_MODE_KEEP, der Inhalt bleibt also erhalten. Verbrauchend wird die Schleife erst, wenn man das ausdrücklich einstellt.

<?php

$stapel = new SplStack();

$stapel->push('A');

$stapel->push('B');



/* Jetzt entfernt die Schleife jedes Element beim Durchlaufen */

$stapel->setIteratorMode(

    SplDoublyLinkedList::IT_MODE_LIFO

    | SplDoublyLinkedList::IT_MODE_DELETE

);



foreach ($stapel as $eintrag) {

    echo $eintrag;

}

echo count($stapel);   /* 0, jetzt ist der Stapel leer */

Das ist ein nützlicher Modus, wenn eine Warteschlange in einem Durchgang abgearbeitet werden soll. Nur sollte man ihn bewusst setzen und nicht unterstellen, er sei die Voreinstellung.

Weitere Stolperfallen

Zum Abschluss eine Übersicht, die bei der Auswahl hilft.

flowchart TD
    A[Werte in Reihenfolge noetig] --> B{Welche Reihenfolge?}
    B -->|Zuletzt zuerst| C[SplStack]
    B -->|Zuerst zuerst| D[SplQueue]
    B -->|Beide Enden| E[SplDoublyLinkedList]
    C --> F[push und pop]
    D --> G[enqueue und dequeue]
    F --> H{Beim Lesen entfernen?}
    G --> H
    H -->|Ja| I[IT_MODE_DELETE setzen]
    H -->|Nein| J[Standard behaelt alles]

Fazit

PHP SplStack ist kein Ersatz für das Array, sondern ein Werkzeug für den Fall, dass die Reihenfolge Teil der Zusage sein soll. Der Klassenname sagt, was passiert, und niemand muss im Kommentar nachlesen, ob hier vorne oder hinten entfernt wird.

Der messbare Gewinn liegt bei der Warteschlange: array_shift() wird mit der Länge teurer, dequeue() nicht. Wer zehn Einträge verwaltet, merkt davon nichts und darf beim Array bleiben. Wer zehntausende verarbeitet, sollte umsteigen.

Und wer das erste Mal mit der Klasse arbeitet, sollte sich eine Zeile merken: ein foreach läuft über einen Stapel rückwärts, lässt ihn aber unangetastet. Geleert wird er nur, wenn IT_MODE_DELETE ausdrücklich gesetzt ist. Wer sich weiter für Objekte mit Array-Verhalten interessiert, findet mit PHP ArrayObject die passende Ergänzung aus derselben Bibliothek.