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

Онлайн-тренажер Python для начинающих

Изучайте Python легко и без перегрузки теорией. Решайте практические задачи с автоматической проверкой, получайте подсказки на русском языке и пишите код прямо в браузере — без необходимости что-либо устанавливать.

Начать курс

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

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

Почему структуры данных важны в PHP?

PHP — язык с динамической типизацией, и его встроенный массив (array) на самом деле является гибридом: он может работать и как список, и как словарь (хеш-таблица). Это мощно, но без понимания лежащих в основе структур вы рискуете писать неоптимальный код. Например, поиск элемента в неотсортированном массиве из 10 000 записей может занять в 100 раз больше времени, чем поиск в хеш-таблице.

Основные структуры, которые мы рассмотрим:

Массивы — основа основ, но с нюансами.
Стек и очередь — для задач с определённым порядком обработки.
Связные списки — для динамического управления памятью.
Хеш-таблицы — для быстрого доступа по ключу.

1. Массивы и работа с ними: от простого к сложному

В PHP массив — это упорядоченное отображение, которое связывает ключи со значениями. Но даже с этой универсальной структурой можно работать по-разному.

Индексированные и ассоциативные массивы

Индексированный массив использует целочисленные ключи, а ассоциативный — строковые. Пример:

<?php
// Индексированный массив
$fruits = ["apple", "banana", "cherry"];
echo $fruits[1]; // banana

// Ассоциативный массив (хеш-таблица)
$user = [
    "name" => "Alice",
    "age" => 30,
    "city" => "Moscow"
];
echo $user["name"]; // Alice
?>

Операции с массивами

Добавление, удаление и поиск — базовые операции. Важно знать их временную сложность:

array_push() / $arr[] = $val — O(1) в среднем.
array_pop() — O(1).
array_shift() — O(n), так как переиндексирует все элементы.
in_array() — O(n) для неотсортированного массива.
isset($arr[$key]) — O(1) для ассоциативных массивов.

Пример эффективного использования ассоциативного массива для подсчёта частоты слов:

<?php
$text = "apple banana apple cherry banana apple";
$words = explode(" ", $text);
$freq = [];

foreach ($words as $word) {
    if (isset($freq[$word])) {
        $freq[$word]++;
    } else {
        $freq[$word] = 1;
    }
}

print_r($freq);
// Array ( [apple] => 3 [banana] => 2 [cherry] => 1 )
?>

2. Стек и очередь: принципы LIFO и FIFO в PHP

Стек (Last In, First Out) и очередь (First In, First Out) — классические структуры, которые легко реализовать на PHP с помощью массивов.

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

Стек используется, например, для проверки парности скобок или отмены действий (undo).

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

    public function push($item): void {
        $this->items[] = $item; // O(1)
    }

    public function pop() {
        return array_pop($this->items); // O(1)
    }

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

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

// Пример: проверка сбалансированности скобок
function isBalanced(string $expr): bool {
    $stack = new Stack();
    $pairs = [')' => '(', ']' => '[', '}' => '{'];

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

echo isBalanced("({[]})") ? "true" : "false"; // true
echo isBalanced("({[})") ? "true" : "false";  // false
?>

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

Очередь пригодится для обработки задач в порядке поступления (например, очередь сообщений).

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

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

    public function dequeue() {
        return array_shift($this->items); // O(n) — переиндексация
    }

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

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

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

while (!$printQueue->isEmpty()) {
    echo "Printing: " . $printQueue->dequeue() . "\n";
}
// Printing: Document1.pdf
// Printing: Photo.jpg
// Printing: Report.docx
?>

Важно: array_shift() работает за O(n). Для более производительной очереди используйте SplQueue (встроенный класс PHP) или реализуйте очередь на основе связного списка.