PHP SPL data structures: stack, queue, and heap
Use the standard SplStack, SplQueue, SplMinHeap, and SplPriorityQueue classes.
<?php
$stack = new SplStack();
$stack->push("a");
$stack->push("b");
$stack->push("c");
echo $stack->pop(), " ", $stack->top(), " ", count($stack), "\n";
$queue = new SplQueue();
$queue->enqueue(1);
$queue->enqueue(2);
$queue->enqueue(3);
echo $queue->dequeue(), " ", $queue->dequeue(), " ", count($queue), "\n";
$heap = new SplMinHeap();
foreach ([5, 1, 8, 3] as $value) {
$heap->insert($value);
}
echo $heap->extract(), " ", $heap->top(), "\n";
$tasks = new SplPriorityQueue();
$tasks->insert("low", 1);
$tasks->insert("high", 10);
$tasks->insert("medium", 5);
$order = [];
while (!$tasks->isEmpty()) {
$order[] = $tasks->extract();
}
echo implode(" > ", $order), "\n";c b 2 1 2 1 1 3 high > medium > low
Explanation
The Standard PHP Library (SPL) provides ready-made data structures. SplStack is last-in, first-out with push, pop, and top. SplQueue is first-in, first-out with enqueue and dequeue. Both are built on a doubly linked list, so each operation is O(1). SplMinHeap and SplMaxHeap keep the smallest or largest element on top, with insert in O(log n).
SplPriorityQueue returns the element with the highest priority first. Elements with equal priority come out in no guaranteed order. Calling pop, dequeue, or extract on an empty structure throws a RuntimeException, so check isEmpty or count first. Plain arrays with array_push, array_pop, and array_shift also work, but array_shift renumbers the keys and is O(n).
Explore the dry run
<?php$stack = new SplStack();$stack->push("a");$stack->push("b");$stack->push("c");echo $stack->pop(), " ", $stack->top(), " ", count($stack), "\n"; $queue = new SplQueue();$queue->enqueue(1);$queue->enqueue(2);$queue->enqueue(3);echo $queue->dequeue(), " ", $queue->dequeue(), " ", count($queue), "\n"; $heap = new SplMinHeap();foreach ([5, 1, 8, 3] as $value) { $heap->insert($value);}echo $heap->extract(), " ", $heap->top(), "\n"; $tasks = new SplPriorityQueue();$tasks->insert("low", 1);$tasks->insert("high", 10);$tasks->insert("medium", 5);$order = [];while (!$tasks->isEmpty()) { $order[] = $tasks->extract();}echo implode(" > ", $order), "\n";Follow the example
Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.
View the complete dry-run table
| Step / line | What happens | State after step | Output so far |
|---|---|---|---|
| Three pushes: c is on top. | — | — | |
| pop removes c, top shows b, and two items remain. | — | c b 2 | |
| Three items join the back of the queue. | — | c b 2 | |
| The oldest items leave first; one item remains. | — | c b 2 1 2 1 | |
| extract removes the smallest value, 1, and top now shows the next smallest, 3. | — | c b 2 1 2 1 1 3 | |
| Higher priority numbers come out first. | — | c b 2 1 2 1 1 3 high > medium > low |
Cost and common mistakes
push, pop, enqueue, and dequeue are O(1). Heap insert and extract are O(log n).
- SplStack iterates from the top down by default, which is the reverse of insertion order. Remember this when using foreach.
- An SplPriorityQueue has no stable order for equal priorities. Add a sequence number to the priority if the order matters.
- Calling extract on an empty heap throws a RuntimeException.
Try it yourself
Which structure would you use for a to-do list processed in arrival order?
Reveal answer and reasoning
SplQueue: the first task added is the first one processed.