Algorithmen und Datenstrukturen in PHP: Von den Grundlagen zur Implementierung

Algorithmen und Datenstrukturen in PHP: Von den Grundlagen bis zur Implementierung

In der modernen Webentwicklung ist die Kenntnis von Algorithmen und Datenstrukturen nicht nur eine akademische Fähigkeit, sondern ein praktisches Werkzeug zur Erstellung schneller, skalierbarer und zuverlässiger Anwendungen. PHP bietet trotz seines Rufs als „Sprache für einfache Websites“ alle notwendigen Mittel zur Umsetzung komplexer Rechenaufgaben. In diesem Artikel behandeln wir die wichtigsten Datenstrukturen und Algorithmen und zeigen vor allem, wie man sie in reinem PHP mit Codebeispielen implementiert.

1. Fundamentale Datenstrukturen in PHP

In PHP decken die eingebauten Typen (Arrays, Objekte) bereits viele Anforderungen ab, aber für ein tiefes Verständnis und Optimierung lohnt es sich, die klassischen Strukturen manuell zu implementieren.

1.1. Stack (Stapel)

Ein Stack arbeitet nach dem LIFO-Prinzip (Last In, First Out). Er wird für Rückgängig-Funktionen (undo), Klammerpaar-Analyse und Tiefensuche in Graphen verwendet.

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

// Beispiel: Prüfung auf korrekte Klammerpaarefunction 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("({[]})") ? "Ausgeglichen" : "Nicht ausgeglichen"; // Ausgeglichen?>

1.2. Queue (Warteschlange)

Eine Queue arbeitet nach dem FIFO-Prinzip (First In, First Out). Sie wird in Aufgabenwarteschlangen, BFS (Breitensuche) und Datenpufferung eingesetzt.

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

// Beispiel: Simulation einer Druckwarteschlange$printQueue = new Queue();$printQueue->enqueue("document1.pdf");$printQueue->enqueue("photo.jpg");$printQueue->enqueue("report.docx");

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

1.3. Binärer Suchbaum (BST)

Ein Baum ermöglicht schnelles Suchen, Einfügen und Löschen von Elementen (im Durchschnitt O(log n)).

<?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)