Stacks and queues — SplStack, SplQueue, array implementations

Intermediate5 min read·eng-07-003

compare

Concept

Stack (LIFO — Last In, First Out): The last item pushed is the first item popped. Think: a stack of plates. Push adds to the top. Pop removes from the top.

Queue (FIFO — First In, First Out): The first item enqueued is the first item dequeued. Think: a line at a checkout. Enqueue adds to the back. Dequeue removes from the front.

Stack operations (all O(1)):

push($item): Add to top.
pop(): Remove and return top.
peek() / top(): View top without removing.
isEmpty(): Check if empty.

Queue operations (all O(1) with proper implementation):

enqueue($item): Add to back.
dequeue(): Remove and return front.
peek(): View front without removing.

Stack use cases: Function call stack, undo/redo, expression parsing, DFS, backtracking algorithms, bracket matching.

Queue use cases: BFS traversal, task queues, rate limiting windows, producer-consumer pattern, print spooler.

PHP built-ins:

SplStack: PHP SPL stack. Extends SplDoublyLinkedList with LIFO mode. Has push(), pop(), top().
SplQueue: PHP SPL queue. Extends SplDoublyLinkedList with FIFO mode. Has enqueue(), dequeue(), bottom().
Array as stack: array_push($arr, $item) / array_pop($arr) — O(1).
Array as queue: array_shift($arr) dequeues from front — O(n) (must shift all elements). Use SplQueue for true O(1) queue operations.

Code Example

php

<?php
// SplStack — LIFO
$stack = new \SplStack();
$stack->push('first');
$stack->push('second');
$stack->push('third');

echo $stack->top();   // 'third' (peek, no removal)
echo $stack->pop();   // 'third' (remove)
echo $stack->pop();   // 'second'
echo $stack->count(); // 1

// SplQueue — FIFO
$queue = new \SplQueue();
$queue->enqueue('first');
$queue->enqueue('second');
$queue->enqueue('third');

echo $queue->dequeue(); // 'first' (FIFO — oldest out first)
echo $queue->dequeue(); // 'second'

// Array as stack (O(1) push/pop)
$stack = [];
array_push($stack, 'a');  // or $stack[] = 'a';
array_push($stack, 'b');
echo array_pop($stack);  // 'b'

// Bracket matching — classic stack problem
function isBalanced(string $expression): bool
{
    $stack = new \SplStack();
    $pairs = ['(' => ')', '[' => ']', '{' => '}'];
    $close = array_flip($pairs);

    foreach (str_split($expression) as $char) {
        if (isset($pairs[$char])) {
            $stack->push($char); // opening bracket → push
        } elseif (isset($close[$char])) {
            if ($stack->isEmpty() || $pairs[$stack->top()] !== $char) {
                return false; // unmatched closing bracket
            }
            $stack->pop();
        }
    }

    return $stack->isEmpty(); // all brackets matched
}

echo isBalanced('{[()]}');  // true
echo isBalanced('{[(])}');  // false

// BFS with a queue (tree/graph traversal)
function bfs(array $graph, string $start): array
{
    $visited = [$start => true];
    $queue   = new \SplQueue();
    $result  = [];

    $queue->enqueue($start);
    while (!$queue->isEmpty()) {
        $node     = $queue->dequeue();
        $result[] = $node;
        foreach ($graph[$node] ?? [] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue->enqueue($neighbor);
            }
        }
    }
    return $result;
}

PreviousLinked lists — implementing in PHP, when to useData Structures in PHP NextBinary trees and BSTs — traversal, searchData Structures in PHP