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

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

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

1. Базовые структуры данных: стек и очередь

Стек и очередь — это линейные структуры данных, которые часто используются в реальных приложениях. Стек работает по принципу LIFO (Last In, First Out), а очередь — FIFO (First In, First Out). В PHP их можно реализовать с помощью встроенных функций массива.

Реализация стека

<?php
class Stack {
    private $stack = [];

    public function push($item) {
        array_push($this->stack, $item);
    }

    public function pop() {
        if ($this->isEmpty()) {
            return null;
        }
        return array_pop($this->stack);
    }

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

    public function isEmpty() {
        return empty($this->stack);
    }
}

// Пример использования
$stack = new Stack();
$stack->push("Первый");
$stack->push("Второй");
$stack->push("Третий");
echo $stack->pop(); // Третий
echo $stack->peek(); // Второй
?>

Реализация очереди

<?php
class Queue {
    private $queue = [];

    public function enqueue($item) {
        array_push($this->queue, $item);
    }

    public function dequeue() {
        if ($this->isEmpty()) {
            return null;
        }
        return array_shift($this->queue);
    }

    public function front() {
        return reset($this->queue);
    }

    public function isEmpty() {
        return empty($this->queue);
    }
}

// Пример использования
$queue = new Queue();
$queue->enqueue("Первый");
$queue->enqueue("Второй");
$queue->enqueue("Третий");
echo $queue->dequeue(); // Первый
echo $queue->front();    // Второй
?>

Эти структуры данных незаменимы при реализации буферов, истории действий (undo/redo) и обработке задач в порядке поступления.

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

Сортировка — одна из самых частых операций в программировании. Рассмотрим две классические реализации: пузырьковую сортировку (для обучения) и быструю сортировку (для реальной работы).

Пузырьковая сортировка (Bubble Sort)

<?php
function bubbleSort(&$arr) {
    $n = count($arr);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($arr[$j] > $arr[$j + 1]) {
                // Обмен значениями
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
}

$numbers = [64, 34, 25, 12, 22, 11, 90];
bubbleSort($numbers);
print_r($numbers); // [11, 12, 22, 25, 34, 64, 90]
?>

Сложность: O(n²) — не подходит для больших массивов, но отлично демонстрирует принцип.

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

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

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

    for ($i = 1; $i < count($arr); $i++) {
        if ($arr[$i] < $pivot) {
            $left[] = $arr[$i];
        } else {
            $right[] = $arr[$i];
        }
    }

    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

$numbers = [3, 6, 8, 10, 1, 2, 1];
$sorted = quickSort($numbers);
print_r($sorted); // [1, 1, 2, 3, 6, 8, 10]
?>

Средняя сложность: O(n log n). В PHP для реальных проектов лучше использовать встроенную функцию sort(), но понимание алгоритма важно для собеседований.

3. Бинарный поиск и работа с деревьями

Бинарный поиск работает только на отсортированных данных и даёт сложность O(log n). Деревья — более сложная структура, но они лежат в основе многих современных систем (например, индексы в базах данных).

Бинарный поиск (итеративная версия)

<?php
function binarySearch($arr, $target) {
    $left = 0;
    $right = count($arr) - 1;

    while ($left <= $right) {
        $mid = floor(($left + $right) / 2);

        if ($arr[$mid] === $target) {
            return $mid;
        }

        if ($arr[$mid] < $target) {
            $left = $mid + 1;
        } else {
            $right = $mid - 1;
        }
    }

    return -1; // не найдено
}

$sortedArray = [1, 3, 5, 7, 9, 11, 13];
$index = binarySearch($sortedArray, 7);
echo "Индекс элемента 7: " . $index; // 3
?>

Простое бинарное дерево поиска (BST)

<?php
class TreeNode {
    public $value;
    public $left;
    public $right;

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

class BinarySearchTree {
    public $root;

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

    private function insertRec($node, $value) {
        if ($node === null) {
            return new TreeNode($value);
        }

        if ($value < $node->value) {
            $node->left = $this->insertRec($node->left, $value);
        } else if ($value > $node->