SplStack, SplQueue, SplPriorityQueue: Using SPL Data Structures in Practice

1. Why an array isn't always the right choice

PHP arrays are ordered hashmaps with built-in support for array_push, array_pop, array_shift, and array_unshift. That means you can technically rebuild any stack or queue semantics with them, and that is exactly what many developers do without thinking through the consequences. The problem isn't functionality, it comes down to two things: performance at scale and the lack of semantic clarity in the code itself.

Anyone reading array_push($stack, $item) has to infer from the variable name and surrounding context that stack semantics are intended here. Nothing stops another developer from accidentally calling array_shift on that same variable and silently changing the order. A SplStack instance, by contrast, only exposes methods that fit stack semantics, making that class of mistake impossible through the type signature alone.

2. The shared foundation: SplDoublyLinkedList

SplStack and SplQueue are both specializations of SplDoublyLinkedList, a doubly linked list. Every node knows its predecessor and successor, which makes inserting and removing at either end possible in constant time, regardless of the list's length. Contrast that with a PHP array, which internally also relies on a hashtable with linked buckets, but which still has to reindex all numeric keys on array_shift.

That reindexing is the actual cost driver: array_shift doesn't just remove the first element, it implicitly shifts every subsequent numeric index down by one. On an array with a hundred thousand elements, a single array_shift call therefore means walking almost the entire structure. SplQueue sidesteps this problem entirely because no element needs to know or maintain its own index.

$list = new SplDoublyLinkedList();
$list->push('a');
$list->push('b');
$list->unshift('z'); // O(1), no reindexing required

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

3. SplStack: implementing undo functionality cleanly

A classic use case for a stack is an undo feature, for example in an editor for content blocks or a CLI tool with several reversible steps. SplStack extends the doubly linked list with LIFO iteration order and the methods push, pop, and top, all of which run in constant time. The code ends up reading almost like a specification, without anyone having to guess which end of an array counts as the current end of the history.

It matters that SplStack references objects rather than copying them. If you push mutable objects onto the stack and keep mutating them afterward, you're also mutating the stored state. For a genuine undo history you should either use immutable state objects or clone explicitly before pushing, otherwise a later pop() returns an already mutated state instead of the original one.

final class UndoHistory
{
    private SplStack $stack;

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

    public function record(EditorState $state): void
    {
        // Cloning is mandatory, otherwise pop() later returns the mutated state
        $this->stack->push(clone $state);
    }

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

4. SplQueue: FIFO processing without reindexing cost

For a simple task queue without prioritization, for example sequentially processing incoming webhook events within a request, SplQueue is a good fit. The class extends the same doubly linked list but exposes enqueue and dequeue as semantically clear FIFO methods. Internally, enqueue simply calls push and dequeue simply calls shift on the base class, both in constant time, without any of an array's reindexing overhead.

A practical example is processing several mutually dependent import batches where the order absolutely must be preserved. Instead of an array with a manual array_shift inside a loop, SplQueue makes the code's intent explicit while staying performant even with thousands of batches, because each dequeue operation is independent of the queue's remaining size.

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

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

5. SplPriorityQueue: processing tasks by urgency

Once the processing order no longer depends purely on time but on a priority, SplPriorityQueue comes into play. Internally the class uses a max heap, so inserting an element runs in logarithmic time and extracting the highest-priority element also runs in logarithmic time. An array would need either a full sort on every insert, which scales quadratically overall, or a linear scan for the maximum on every extract to achieve the same behavior.

This matters in practice for something like a job queue where critical maintenance tasks must run before regular report generation, regardless of the order in which they were enqueued. By default, extract() only returns the value. Via setExtractFlags() you can change that so both value and priority, or an array containing both, are returned, which is almost always more useful in practice.

$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']} (priority {$item['priority']})" . PHP_EOL;
}
// Output: maintenance:disk-cleanup (10), report:daily (3), report:monthly (1)

6. Stability with equal priority and custom comparison logic

One detail that's easy to overlook in practice: SplPriorityQueue does not guarantee a stable order by insertion time for elements with equal priority. Two elements with identical priority can be extracted in either order, because the underlying heap only knows priority as its sort criterion. If you need deterministic ordering on ties, extend the priority with a second, finer component, for example a descending timestamp.

For more complex comparison logic, you can also extend SplPriorityQueue with a subclass that overrides compare(). That's useful when priority isn't a simple integer but is composed of several fields on an object. Alternatively, for pure min-heap use cases the related class SplMinHeap is a good fit, while SplMaxHeap matches the default behavior of SplPriorityQueue minus the extra priority dimension.

final class DeterministicPriorityQueue extends SplPriorityQueue
{
    public function compare(mixed $priority1, mixed $priority2): int
    {
        // On ties, the secondary component (timestamp) decides
        return $priority1 <=> $priority2;
    }
}

7. Performance head to head against array functions

The difference between array_shift and SplQueue::dequeue() only becomes visible at realistic data volumes. With small lists of a few hundred elements the difference is barely measurable, because both operations sit in the microsecond range. Past tens of thousands of elements, a clear trend emerges: an array that repeatedly has elements removed from the front degrades linearly per operation as it grows, while SplQueue stays constant.

The important caveat is that this advantage applies exclusively to operations at the ends. For random access via a numeric index, an array is still clearly ahead, because accessing a hashtable element runs in constant time, while a linked list may in the worst case have to walk the entire list for the same access. So the choice of data structure should always be driven by the actual access pattern, not by a blanket preference.

8. Understanding iteration mode and memory behavior

A detail that's often overlooked with SplDoublyLinkedList and its descendants is the configurable iteration mode. Via setIteratorMode() you can control whether iteration consumes elements, emptying the stack or queue in the process, or leaves the contents unchanged. The default mode, IT_MODE_LIFO on SplStack and IT_MODE_FIFO on SplQueue, doesn't remove elements by default, but combining it with IT_MODE_DELETE is a deliberate option for destructive processing.

Regarding memory footprint: a doubly linked list needs extra memory per element for the predecessor and successor references, while a PHP array can be organized more compactly internally. For very large datasets that are rarely manipulated at the ends, a plain array can therefore even be more memory-efficient. The SPL structures earn their advantage specifically with frequent insert and remove operations at the ends, not as a general memory optimization.

9. Decision guide: which structure fits which use case

In practice, SplStack pays off whenever you need clear LIFO semantics with frequent push and pop operations on a growing structure, for example undo histories, bracket validation in parsers, or recursive traversals reworked into an iterative form. SplQueue fits FIFO scenarios instead, such as sequential batch processing or simple queues without any prioritization requirement.

SplPriorityQueue is the right choice as soon as a ranking exists that goes beyond plain insertion order, for example job schedulers, event loops with varying urgency, or Dijkstra-like graph algorithms. For small, manageable lists with mixed access patterns, a plain array often remains the most pragmatic choice, because the extra object overhead of the SPL structures only pays off at meaningful size or with frequent manipulation at the ends.

10. Summary

11. FAQ: SPL data structures: the essentials at a glance