Algorithmes et structures de données en PHP : des bases à l'implémentation

Algorithmes et structures de données en PHP : des bases à l'implémentation

Dans le développement web moderne, la connaissance des algorithmes et des structures de données n'est pas simplement une compétence académique, mais un outil pratique pour créer des applications rapides, évolutives et fiables. PHP, malgré sa réputation de « langage pour sites simples », fournit tous les moyens nécessaires pour implémenter des tâches computationnelles complexes. Dans cet article, nous allons détailler les structures de données et algorithmes clés, et surtout, montrer comment les implémenter en PHP pur avec des exemples de code.

1. Structures de données fondamentales en PHP

En PHP, les types intégrés (tableaux, objets) couvrent déjà de nombreux besoins, mais pour une compréhension approfondie et une optimisation, il vaut la peine d'implémenter manuellement les structures classiques.

1.1. Pile (Stack)

La pile fonctionne selon le principe LIFO (Last In, First Out). Elle est utilisée pour l'annulation d'actions (undo), l'analyse des parenthèses, le parcours en profondeur des graphes.

<?phpclass Stack {    private array $items = [];

    public function push($item): void {        array_push($this->items, $item);    }

    public function pop() {        if ($this->isEmpty()) {            throw new UnderflowException('Stack is empty');        }        return array_pop($this->items);    }

    public function peek() {        return end($this->items);    }

    public function isEmpty(): bool {        return empty($this->items);    }

    public function size(): int {        return count($this->items);    }}

// Exemple : vérification de l'équilibre des parenthèsesfunction isBalanced(string $expression): bool {    $stack = new Stack();    $pairs = ['(' => ')', '{' => '}', '[' => ']'];

    for ($i = 0; $i < strlen($expression); $i++) {        $char = $expression[$i];        if (isset($pairs[$char])) {            $stack->push($char);        } elseif (in_array($char, $pairs)) {            if ($stack->isEmpty() || $pairs[$stack->pop()] !== $char) {                return false;            }        }    }    return $stack->isEmpty();}

echo isBalanced("({[]})") ? "Équilibré" : "Non équilibré"; // Équilibré?>

1.2. File d'attente (Queue)

La file d'attente fonctionne selon le principe FIFO (First In, First Out). Elle est utilisée dans les systèmes de files de tâches, le BFS (parcours en largeur), la mise en mémoire tampon des données.

<?phpclass Queue {    private array $items = [];

    public function enqueue($item): void {        $this->items[] = $item;    }

    public function dequeue() {        if ($this->isEmpty()) {            throw new UnderflowException('Queue is empty');        }        return array_shift($this->items);    }

    public function peek() {        return $this->items[0] ?? null;    }

    public function isEmpty(): bool {        return empty($this->items);    }

    public function size(): int {        return count($this->items);    }}

// Exemple : simulation d'une file d'impression$printQueue = new Queue();$printQueue->enqueue("document1.pdf");$printQueue->enqueue("photo.jpg");$printQueue->enqueue("report.docx");

while (!$printQueue->isEmpty()) {    echo "Impression en cours : " . $printQueue->dequeue() . "";}?>

1.3. Arbre binaire de recherche (BST)

L'arbre assure une recherche, une insertion et une suppression rapides des éléments (O(log n) en moyenne).

<?phpclass TreeNode {    public $value;    public ?TreeNode $left = null;    public ?TreeNode $right = null;

    public function __construct($value) {        $this->value = $value;    }}

class BinarySearchTree {    public ?TreeNode $root = null;

    public function insert($value): void {        $this->root = $this->insertNode($this->root, $value);    }

    private function insertNode(?TreeNode $node, $value): TreeNode {        if ($node === null)