PHP SPL data structures: stack, queue, and heap

Before you start

PHP classes and arrays.

Use the standard SplStack, SplQueue, SplMinHeap, and SplPriorityQueue classes.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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).

Code example

PHP

<?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";

Output

c b 2
1 2 1
1 3
high > medium > low

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

Guided walkthroughReady

1<?php

2$stack = new SplStack();

3$stack->push("a");

4$stack->push("b");

5$stack->push("c");

6echo $stack->pop(), " ", $stack->top(), " ", count($stack), "\n";

8$queue = new SplQueue();

9$queue->enqueue(1);

10$queue->enqueue(2);

11$queue->enqueue(3);

12echo $queue->dequeue(), " ", $queue->dequeue(), " ", count($queue), "\n";

14$heap = new SplMinHeap();

15foreach ([5, 1, 8, 3] as $value) {

16 $heap->insert($value);

17}

18echo $heap->extract(), " ", $heap->top(), "\n";

20$tasks = new SplPriorityQueue();

21$tasks->insert("low", 1);

22$tasks->insert("high", 10);

23$tasks->insert("medium", 5);

24$order = [];

25while (!$tasks->isEmpty()) {

26 $order[] = $tasks->extract();

27}

28echo 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

Prepared trace of the published program. Some rows group repeated iterations.
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

Behind the scenes

How PHP processes this code

The PHP runtime executes the script. echo writes to the response or terminal output.

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.