Queues

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);
}

References

• ↗ https://www.php.net/manual/en/class.splqueue.php

Tags

Related Terms