Queues
debt(d7/e3/b3/t5)
Closest to 'only careful code review or runtime testing' (d7) — array_shift() in a loop isn't flagged by standard linters; Blackfire profiling can reveal the O(n²) hot spot but requires deliberate investigation.
Closest to 'simple parameterised fix' (e3) — quick_fix is swapping array_shift() loops for SplQueue, a localized pattern replacement typically in one queue-consuming function.
Closest to 'localised tax' (b3) — the choice of queue implementation typically affects one component (the consumer/processor), not the whole codebase.
Closest to 'notable trap' (t5) — the misconception that PHP arrays are efficient queues is a documented gotcha; array_shift's O(n) reindexing surprises devs coming from languages with proper deque types.
Also Known As
TL;DR
Explanation
A queue supports enqueue (add to rear) and dequeue (remove from front), both O(1) with a doubly linked list. PHP's SplQueue implements this. Circular queues reuse space efficiently in fixed-size buffers. Priority queues extend queues by serving the highest-priority element first (SplMinHeap/SplMaxHeap). The distinction matters practically: array_shift() on a large PHP array is O(n) because it reindexes — use SplQueue for O(1) FIFO operations.
Diagram
flowchart LR
subgraph Queue_FIFO
ENQUEUE[enqueue - add to rear] --> REAR[REAR - newest]
REAR --> E3Q[Element C]
E3Q --> E2Q[Element B]
E2Q --> FRONT[FRONT - oldest]
FRONT --> DEQUEUE[dequeue - remove from front]
end
subgraph Applications
BFS3[BFS traversal]
JOBS[Job queue workers]
PRINT[Print spooler]
BUFFER[IO buffering]
end
subgraph PHP
SPLQ[SplQueue O of 1 both ops]
ARRAY_BAD[array_shift is O of n<br/>avoid for large queues]
end
style FRONT fill:#238636,color:#fff
style SPLQ fill:#238636,color:#fff
style ARRAY_BAD fill:#f85149,color:#fff
Common Misconception
Why It Matters
Common Mistakes
- array_shift() for dequeue in a loop — O(n²) total for n dequeues; use SplQueue.
- Treating a priority queue like a FIFO queue — priority queues are not ordered by insertion time.
- Not handling the empty queue case — dequeue on an empty queue throws RuntimeException.
- Using a stack (LIFO) when FIFO order is required — results processed in reverse order.
Code Examples
// O(n²) — array_shift reindexes entire array each call:
$queue = [];
for ($i = 0; $i < 10000; $i++) $queue[] = $i;
while ($queue) {
$item = array_shift($queue); // O(n) per call — 10000 calls = O(n²)
process($item);
}// SplQueue — O(1) per operation:
$queue = new SplQueue();
for ($i = 0; $i < 10000; $i++) $queue->enqueue($i);
while (!$queue->isEmpty()) {
$item = $queue->dequeue(); // O(1)
process($item);
}