Алгоритмы и структуры данных на PHP: от основ до реализации

Алгоритмы и структуры данных на PHP: от основ до реализации

В современной веб-разработке знание алгоритмов и структур данных — это не просто академический навык, а практический инструмент для создания быстрых, масштабируемых и надёжных приложений. PHP, несмотря на свою репутацию «языка для простых сайтов», предоставляет все необходимые средства для реализации сложных вычислительных задач. В этой статье мы разберём ключевые структуры данных и алгоритмы, а главное — покажем, как их реализовать на чистом PHP с примерами кода.

1. Фундаментальные структуры данных на PHP

В PHP встроенные типы (массивы, объекты) уже покрывают многие потребности, но для глубокого понимания и оптимизации стоит реализовать классические структуры вручную.

1.1. Стек (Stack)

Стек работает по принципу LIFO (Last In, First Out). Используется для отмены действий (undo), парсинга скобок, обхода графов в глубину.

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

// Пример: проверка сбалансированности скобок
function 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("({[]})") ? "Сбалансировано" : "Не сбалансировано"; // Сбалансировано
?>

1.2. Очередь (Queue)

Очередь работает по принципу FIFO (First In, First Out). Применяется в системах очередей задач, BFS (обход в ширину), буферизации данных.

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

// Пример: симуляция очереди печати
$printQueue = new Queue();
$printQueue->enqueue("document1.pdf");
$printQueue->enqueue("photo.jpg");
$printQueue->enqueue("report.docx");

while (!$printQueue->isEmpty()) {
    echo "Печатается: " . $printQueue->dequeue() . "\n";
}
?>

1.3. Бинарное дерево поиска (BST)

Дерево обеспечивает быстрый поиск, вставку и удаление элементов (O(log n) в среднем).

<?php
class 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) {
            return new TreeNode($value);
        }

        if ($value < $node->value) {
            $node->left = $this->insertNode($node->left, $value);
        } elseif ($value > $node->value) {
            $node->right = $this->insertNode($node->right, $value);
        }
        return $node;
    }

    public function search($value): bool {
        return $this->searchNode($this->root, $value);
    }

    private function searchNode(?TreeNode $node, $value): bool {
        if ($node === null) return false;
        if ($value === $node->value) return true;
        return $value < $node->value
            ? $this->searchNode($node->left, $value)
            : $this->searchNode($node->right, $value);
    }

    // Обход в порядке (in-order traversal)
    public function inOrder(): array {
        $result = [];
        $this->traverseInOrder($this->root, $result);
        return $result;
    }

    private function traverseInOrder(?TreeNode $node, array &$result): void {
        if ($node !== null) {
            $this->traverseInOrder($node->left, $result);
            $result[] = $node->value;
            $this->traverseInOrder($node->right, $result);
        }
    }
}

$bst = new BinarySearchTree();
foreach ([8, 3, 10, 1, 6, 14, 4, 7, 13] as $val) {
    $bst->insert($val);
}
echo "Отсортированные значения: " . implode(", ", $bst->inOrder()); // 1, 3, 4, 6, 7, 8, 10, 13, 14
?>

2. Классические алгоритмы сортировки на PHP

Хотя PHP имеет встроенную функцию sort(), понимание алгоритмов сортировки критически важно для оптимизации и собеседований.

2.1. Быстрая сортировка (Quick Sort)

Один из самых эффективных алгоритмов (O(n log n) в среднем).

<?php
function quickSort(array $arr): array {
    if (count($arr) < 2) {
        return $arr;
    }

    $pivot = $arr[0];
    $left = $right = [];

    for ($i = 1; $i < count($arr); $i