Stacks

Also Known As

TL;DR

Explanation

A stack supports three operations: push (add to top), pop (remove from top), peek (read top without removing). All are O(1). PHP's SplStack implements a doubly-linked-list-backed stack. The call stack is the most familiar stack — each function call pushes a frame, each return pops it. Stacks naturally model any 'reverse the order' or 'undo' problem. Bracket matching, postfix expression evaluation, and iterative DFS all use stacks explicitly.

Diagram

flowchart TD
    subgraph Stack_LIFO
        TOP[TOP] --> E3[Element C - last in]
        E3 --> E2[Element B]
        E2 --> E1[Element A - first in]
        E1 --> BOTTOM[BOTTOM]
    end
    PUSH[push C] -->|O of 1| TOP
    POP[pop] -->|O of 1 returns C| E3
    subgraph Applications
        CALLSTACK[Call stack<br/>function frames]
        UNDO[Undo history]
        DFS2[DFS traversal]
        BRACKETS[Bracket matching]
    end
style TOP fill:#238636,color:#fff
style E3 fill:#1f6feb,color:#fff

Common Misconception

Why It Matters

Common Mistakes

• Implementing a stack with array_push/array_shift — shift is O(n); use array_push/array_pop (both O(1)).
• Not checking isEmpty() before pop — popping an empty stack throws an exception in SplStack.
• Using a queue where a stack is needed — the order of processing is reversed.
• Confusing stack overflow (too many recursive calls) with heap overflow (memory exhaustion).

Code Examples

// Using array_shift as 'pop' — O(n) reindex:
$stack = [];
array_push($stack, 'a');
array_push($stack, 'b');
$top = array_shift($stack); // 'a' — wrong order AND O(n)

// array_pop is O(1) — correct LIFO:
$stack = [];
array_push($stack, 'a');
array_push($stack, 'b');
$top = array_pop($stack); // 'b' — correct LIFO, O(1)

// Or SplStack:
$stack = new SplStack();
$stack->push('a');
$stack->push('b');
$top = $stack->pop(); // 'b'

References

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

Tags

Related Terms