skip to content

In PHP, why use SplQueue rather than array_push() and array_shift() for a FIFO work queue, and how does SplStack differ?

level: middleimportance: should knowfreq 32%

answer

  1. array_shift renumbers every remaining key
  2. doubly linked list underneath
  3. enqueue() and dequeue() are aliases
  4. empty dequeue throws RuntimeException
  5. SplStack iterates LIFO, mode frozen

basics

~20 s

array_shift() renumbers all remaining keys, so each dequeue costs time proportional to the queue length. SplQueue is a doubly linked list with constant-time enqueue() and dequeue(). SplStack is the same list used LIFO, with push(), pop() and top().

solid answer

~40 s

A plain array makes a fine stack, because `array_push()` and `array_pop()` work at the end. As a queue it is weak: `array_shift()` removes the first element and then **re-indexes every remaining numeric key**, so draining n jobs costs roughly n² steps. `SplQueue` extends `SplDoublyLinkedList`, so `enqueue()` and `dequeue()` (aliases of `push()` and `shift()`) are constant time whatever the length. Its failure mode differs too: `dequeue()` on an empty queue throws `RuntimeException`, while `array_shift()` on an empty array returns `null`, so I loop on `isEmpty()`. `SplStack` is the same list with LIFO iteration: `push()`, `pop()`, `top()`, and `foreach` from the newest element. Both lock their iteration direction; `setIteratorMode()` can only switch between keeping and deleting elements as they are visited.

code

php · 17 lines
php
<?php
declare(strict_types=1);

$queue = new SplQueue();
$queue->enqueue('resize-image');
$queue->enqueue('send-invoice');

while (!$queue->isEmpty()) {
    echo $queue->dequeue(), "\n"; // resize-image, then send-invoice
}

$stack = new SplStack();
$stack->push('a');
$stack->push('b');
foreach ($stack as $item) {
    echo $item;                   // prints "ba": LIFO order
}

go deeper

for a junior

Know enqueue()/dequeue() on SplQueue and push()/pop()/top() on SplStack, and that an empty dequeue throws rather than returning null.

for a middle

Explain why array_shift() renumbers keys and costs linear time, while the linked list behind SplQueue makes both ends constant time.

for a senior

Judge when the queue length makes array_shift() a real cost in a worker, and weigh SplQueue's per-node memory and object semantics against an array with a head index.

for a principal

Decide whether an in-process queue is the right tool at all, versus a durable external queue that survives worker restarts.

## Why a plain array is a poor queue A PHP array is an ordered map. Using it as a first-in-first-out queue usually looks like this: ```php $jobs[] = $job; // or array_push($jobs, $job) $next = array_shift($jobs); // take from the front ``` Appending is cheap. Removing from the front is not: `array_shift()` takes the first element and then **renumbers all remaining integer keys** so the list starts again at `0`. That touches every element still in the array, so one dequeue costs time proportional to the queue length, and draining a queue of n items costs on the order of n² steps. For ten items nobody notices; for a hundred thousand queued jobs in a long-running worker it dominates the profile. The end of an array is a different story: `array_pop()` removes the last element without renumbering anything, which is why a plain array remains a perfectly good **stack**. ## SplQueue and SplStack Both classes extend `SplDoublyLinkedList`, a list of nodes linked in both directions, with direct access to the head and the tail. | Operation | `SplQueue` | `SplStack` | Cost | |---|---|---|---| | add | `enqueue($v)` (alias of `push`) | `push($v)` | constant | | remove | `dequeue()` (alias of `shift`) | `pop()` | constant | | look without removing | `bottom()` (next to leave) | `top()` | constant | | `foreach` order | oldest first (FIFO) | newest first (LIFO) | — | | empty check | `isEmpty()`, `count()` | `isEmpty()`, `count()` | constant | On an empty structure, `dequeue()`, `shift()` and `pop()` throw `RuntimeException` ("Can't shift from an empty datastructure", "Can't pop from an empty datastructure"), and the peeking methods throw as well. The array functions behave differently: `array_shift()` and `array_pop()` return `null` on an empty array, which is indistinguishable from a queued `null`. A worker loop therefore checks first: ```php while (!$queue->isEmpty()) { handle($queue->dequeue()); } ``` ## Iteration modes `SplDoublyLinkedList::setIteratorMode()` combines two flags: 1. **Direction**: `IT_MODE_FIFO` or `IT_MODE_LIFO`. For `SplQueue` and `SplStack` the direction is fixed; trying to change it throws `RuntimeException` saying the LIFO/FIFO modes for these classes are frozen. 2. **Behaviour**: `IT_MODE_KEEP` (the default) leaves elements in place as `foreach` visits them; `IT_MODE_DELETE` removes each one as it is visited, so a `foreach` drains the structure. ## What the SPL classes do not buy you - **Speed for stacks.** `SplStack` is not faster than `array_push()` plus `array_pop()`; it mainly states intent and gives `top()` and the exception on underflow. - **Memory.** Each element lives in its own list node, so a large `SplQueue` uses more memory per element than a packed array of the same values. - **Array functions.** An `SplQueue` is an object, not an array; `array_map()`, `sort()` and friends do not accept it. Convert with `iterator_to_array()` or loop. - **Value semantics.** An array passed to a function is copied on write; an `SplQueue` is an object, so the function receives a handle to the same queue and its `dequeue()` calls are visible to the caller. Measure before switching: for a queue that never holds more than a few dozen items, `array_shift()` costs nothing noticeable and the array is simpler to debug and to `var_dump`. The linear cost only shows once the queue regularly holds thousands of entries and is drained in a hot loop, as in a crawler's URL frontier or a batch importer's work list. ## Other ways to avoid the cost - **`SplDoublyLinkedList` directly**: the parent class offers `push()`, `pop()`, `shift()` and `unshift()` at both ends, plus a configurable iteration direction, when you need a double-ended queue rather than a strict FIFO. - **Reverse once, then pop**: when a batch is filled completely before it is consumed, `array_reverse()` once and then `array_pop()` repeatedly gives FIFO order with cheap removals. - **A head index**: keep the array and an integer position, read `$jobs[$head]`, `unset()` it and increment `$head`. The head-index approach keeps array semantics at the price of managing the index yourself; `SplQueue` hides that bookkeeping behind `enqueue()` and `dequeue()` and states the intent in the type.

  • How do you make a foreach over an SplQueue consume the elements it visits?
    Call `$queue->setIteratorMode(SplDoublyLinkedList::IT_MODE_FIFO | SplDoublyLinkedList::IT_MODE_DELETE)`. The default `IT_MODE_KEEP` leaves elements in place. The direction flag must stay FIFO for a queue; asking for LIFO throws `RuntimeException` because the direction of `SplQueue` and `SplStack` is frozen.
  • Is SplStack faster than a plain array used as a stack?
    Not meaningfully. `array_push()` and `array_pop()` work at the end of a packed array without renumbering, so they are already cheap. `SplStack` states intent, adds `top()`, and throws on underflow instead of returning `null`, but it uses more memory per element.

saying these in an interview costs you the question

  • array_shift() is constant time like array_pop()
  • SplStack is much faster than array_push() and array_pop()
  • dequeue() on an empty SplQueue returns null
  • setIteratorMode() can turn an SplQueue into LIFO order
  • An SplQueue passed to a function is copied like an array