Stacks, Queues, And Deques

Stacks remove the newest item first, queues remove the oldest item first, and deques support both ends.

Why This Matters

These structures encode processing order directly and appear in parsing, traversal, work scheduling, undo history, and breadth-first search.

Working Model

LIFO order suits nested work and backtracking. FIFO order suits arrival-order processing and breadth-first traversal. In PHP, SPL structures can communicate intent better than repeated array shifting.

Practical Rules

• Choose order from the business requirement.
• Use SplStack, SplQueue, or SplDoublyLinkedList where intent matters.
• Bound queues that can grow from external input.
• Define empty behavior.
• Separate queue order from retry policy.

Failure Modes

• Using array_shift() repeatedly on large arrays.
• Calling a queue reliable without persistence or acknowledgement.
• Allowing priority to silently replace fairness.
• Mixing stack and queue operations on one collection.

Verification

• Test exact removal order.
• Test empty and capacity behavior.
• Measure large workloads.
• Simulate retries and duplicate jobs separately.

What You Should Be Able To Do

After this lesson, you should be able to explain LIFO, FIFO, and double-ended processing and their practical PHP representations, choose a suitable approach for a real PHP project, and verify the result instead of relying on assumptions.

Order Is The Data Structure

Stacks, queues, and deques are simple because their central rule is simple: they control which item comes out next. A stack removes the newest item first. A queue removes the oldest item first. A deque allows insertion and removal at both ends. The value of these structures is not their names; it is that they encode processing order directly in the code.

A stack is useful for nested work. Function calls, undo histories, depth-first traversal, parser state, and backtracking all have a last-in, first-out shape. The newest unfinished item is the next one to handle. A queue is useful for arrival-order work. Breadth-first traversal, simple job buffers, and request-local pipelines often need first-in, first-out behavior. A deque is useful when both ends have meaning, such as sliding windows or algorithms that need to add urgent work to the front while still keeping normal work at the back.

The first question is therefore not which PHP class to use. It is what order the requirement promises. If customers are processed in signup order, a priority structure may violate fairness. If the newest undo action must be reverted first, a queue is wrong. If retry timing controls when work is eligible, queue order and retry policy must be separate concepts.

Arrays Versus SPL Structures

PHP arrays can model small stacks and queues. Appending with $items[] = $value and removing with array_pop() gives a basic stack. For tiny request-local data, that may be perfectly clear. Queue behavior can also be built with arrays, but repeated array_shift() on large arrays is a performance warning because removing from the front requires reindexing list elements.

SPL structures communicate intent better for larger or more explicit workflows. SplStack represents LIFO behavior. SplQueue represents FIFO behavior. SplDoublyLinkedList can operate at both ends. These classes also avoid some of the accidental shape drift that plain arrays allow.

<?php

declare(strict_types=1);

$stack = new SplStack();
$stack->push('parse expression');
$stack->push('parse term');

echo $stack->pop() . PHP_EOL;
echo $stack->pop() . PHP_EOL;

// Prints:
// parse term
// parse expression

The example is small, but the name SplStack makes the order visible. A reviewer does not have to inspect every array operation to know that newest work comes out first.

Queue Behavior And Empty Cases

A queue promises oldest-first removal. That promise is useful only when empty behavior is defined. Should an empty queue throw, return null, block, or produce a status that the caller checks? In request-local PHP code, throwing or checking isEmpty() may be enough. In a worker, empty behavior may mean sleeping, polling later, or exiting cleanly.

<?php

declare(strict_types=1);

$queue = new SplQueue();
$queue->enqueue('send receipt');
$queue->enqueue('update search index');

while (!$queue->isEmpty()) {
    echo $queue->dequeue() . PHP_EOL;
}

// Prints:
// send receipt
// update search index

Bounded growth is another part of the contract. A queue fed by external input can grow until memory fails if nothing limits it. For in-memory queues, define a maximum size or ensure the input is already bounded. For durable queues, use operational limits, visibility into backlog, and a policy for overload. A queue without capacity thinking is just deferred failure.

Deques And Sliding Windows

A deque supports both ends. That makes it useful when the algorithm needs more than plain FIFO or LIFO. A sliding window may add new observations at the back and remove expired observations from the front. A work scheduler may push urgent local work to the front while appending normal work to the back. A parser may need to put a token back after looking ahead.

The risk is that a deque can hide an unclear policy. If some code inserts at the front and other code inserts at the back, the difference must be intentional. Otherwise the structure becomes a place where fairness and priority are mixed without a name. Use wrapper methods when the raw operations are too general for the business rule: enqueueNormal(), enqueueRetryReadyNow(), or removeExpiredFromFront() explains more than exposing every deque operation everywhere.

Reliability Is Not Just FIFO

An in-memory PHP queue is not a reliable job queue. It disappears when the process exits. It does not acknowledge work durably. It does not protect against duplicate processing after a crash. It does not coordinate multiple workers. Calling an array or SplQueue a queue does not give it the properties of a message broker or a database-backed job table.

This distinction matters in lessons about background work. FIFO order answers only which item comes out next from this structure? Reliable processing answers additional questions: where is the job stored, when is it considered claimed, what happens if the worker dies, how are retries counted, and how are duplicates prevented or tolerated? Keep those concerns separate in design and tests.

Priority can also undermine fairness. If priority work is always inserted before normal work, normal work may starve. If retries return immediately to the front, a failing job can block everything behind it. Queue order, priority, eligibility time, retry delay, and dead-letter policy deserve separate names.

Practical PHP Choices

Use a plain array stack when the data is tiny and local. Use SplStack when LIFO intent should be explicit or when the structure grows. Use SplQueue for FIFO request-local processing. Use SplDoublyLinkedList or a small wrapper when both ends are meaningful. Use a durable external mechanism when work must survive process failure, coordinate between workers, or be observable operationally.

Avoid mixing operations. A collection that sometimes uses array_pop() and sometimes uses array_shift() is not a clear stack or queue. A helper that exposes both push() and enqueue() on the same internal list should explain the policy or be split into two structures.

Verification

The main test is exact removal order. Insert three named values and assert the order in which they come out. Test empty behavior explicitly. Test capacity behavior when growth is bounded. For queues connected to retries, test duplicate jobs and failed jobs separately from FIFO order. A FIFO unit test does not prove retry reliability.

Measure large workloads if the structure can grow. Repeated array_shift() may be invisible in a ten-item fixture and expensive in a ten-thousand-item workload. Use a realistic size before replacing a clear array stack with a more complex abstraction, but do not ignore growth when the input comes from users, files, or remote systems.

Capacity, Backpressure, And Boundaries

Capacity is part of queue design, even for local structures. A parser stack may be bounded by input depth. A breadth-first traversal queue may grow with the width of a graph. A request-local work queue may grow with user-submitted rows. If the input is untrusted or business-growth driven, decide what happens when the structure becomes too large. The answer might be validation, chunking, streaming, a background job, or a hard rejection with a useful error.

Backpressure is the operational version of the same idea. A durable queue can absorb bursts, but it cannot make work disappear. If producers enqueue faster than workers process, the backlog grows. The system needs visibility into queue length, job age, failure rate, and retry count. Those metrics do not belong in a pure data-structure exercise, but they matter when the same words are used in application architecture.

Retries should not be tested as ordinary FIFO behavior. A retry has a cause, an attempt count, an eligibility time, and usually a maximum. If a failed job is simply appended to the back of the same queue, it may retry too quickly or too often. If it is pushed to the front, it may starve new work. Model retry state separately so the queue only answers the ordering question for work that is ready to run.

For graph traversal, stacks and queues produce different results even when both eventually visit every reachable node. Depth-first traversal uses a stack shape and follows one path deeply before backing up. Breadth-first traversal uses a queue shape and explores neighbors by distance from the start. Tests should assert the expected traversal order when that order affects output, not merely that all nodes were seen.

After this lesson, you should be able to choose LIFO, FIFO, or double-ended behavior from the requirement, represent that order clearly in PHP, avoid confusing in-memory queues with reliable job systems, and test the exact order and empty behavior that callers depend on.