Алгоритмы — это хорошо, но структуры данных — еще лучше.
Структура данных — это конкретный способ хранения и организации данных. Иногда удобно организовать данные одним образом, иногда — другим. Здесь все зависит от решаемых задач.
Одну структуру данных мы уже изучили — это массив. По своей структуре массив — это совокупность элементов, к которым есть индексированный доступ (доступ по индексу).
С точки зрения хранения все работает немного сложнее. Массивы бывают разные, и внутри языка они реализуются тоже по-разному.
Каноническая организация хранения массива — это непрерывный блок памяти. В таком случае индекс играет роль смещения по ней. Именно поэтому индексация в массивах начинается с нуля — индекс указывает на начало этого блока, а индекс под номером 1 уже считается смещением. Сложность в том, что в PHP нет настоящих массивов. Об этом вы узнаете в следующем курсе.
Кроме массивов существует множество других структур данных: списки, хеш-таблицы, деревья, графы, стек, очередь и другие. Если мы правильно выберем структуру данных под решаемую задачу, мы сможем заметно упростить код и устранить запутанную логику.
Некоторые из перечисленных структур данных мы рассмотрим в курсах и проектах, другие придется изучить самостоятельно по книгам. В любом случае алгоритмы и структуры данных — это фундамент, на которую строится все остальное в разработке.
Стоит разделять три понятия:
- Структура данных. Выше мы изучили этот термин
- Конкретный тип данных. Типом данных может быть что угодно в зависимости от предпочтений создателей языка. Само это понятие всегда привязано к конкретному языку. Если бы создатели PHP захотели обозначать числа через тип данных Array, то никто не запретил бы эту абсурдную идею.
- Абстрактный тип данных (АТД). Это теоретическое понятие, которое существует только на бумаге и в головах. Абстрактный тип данных определяется только операциями, которые можно выполнять над ним. При этом о способе хранения данных нам ничего не известно. АТД есть во всех языках, но везде его реализуют разные конкретные типы.
АТД нередко путают с понятием «структура данных». Более того, часто они имеют одно и то же название.
В этом уроке мы разберем один из самых простых и важных абстрактных типов данных – стек.
Стек
Термином стек называют упорядоченную коллекцию элементов. В стеке добавление и удаление элементов всегда происходит с вершины стека — начала или конца коллекции:
У стека есть аналогии из реальной жизни. Само слово stack переводится с английского как «стопка», поэтому любую стопку можно рассматривать как стек. Например, чтобы изменить стопку книг, нужно добавить одну книгу сверху или убрать одну снизу.
Еще один пример стека — это стопка шипучих таблеток в упаковке:
Здесь есть дно, поэтому мы не можем сразу достать самую нижнюю таблетку. Открыв упаковку, мы заберем самую верхнюю таблетку, которую положили последней. Такие стеки называют LIFO (Last In First Out) — последний элемент выходит из стека первым.
Вспомните, как исполняется любая программа. Первые функции вызывают вторые, вторые вызывают третьи и так далее. Программа доходит до самой глубокой функции и получает ее значение. Чтобы вернуть это значение, программа запускает обратный процесс: переходит от самой глубокой функции к менее глубокой, поднимается на уровень выше, а потом еще выше вплоть до самой внешней функции. Другими словами, вызов функций — добавление элемента в стек, а возврат — снятие со стека.
Именно так все устроено на аппаратном уровне. Если во время выполнения произойдет ошибка, мы увидим трассировку стека (stack trace).
Еще один пример из программирования — кнопка «Назад» в браузере. История посещений — это стек ссылок, в котором кнопка «Назад» извлекает последний элемент.
Стек — абстрактный тип данных со следующим набором операций:
- Добавить в стек (
push) - Взять из стека (
pop) - Вернуть элемент с вершины стека без удаления (
peek) - Проверить на пустоту (
isEmpty) - Вернуть размер (
size)
В PHP стек можно создать на основе массивов. Для этого используются функции array_push, array_pop, empty и count:
<?php
$stack = [];
array_push($stack, 3);
print_r($stack);
// => Array
// => (
// => [0] => 3
// => )
array_push($stack, 'Winterfall');
print_r($stack);
// => Array
// => (
// => [0] => 3
// => [1] => Winterfall
// => )
array_push($stack, true);
print_r($stack);
// => Array
// => (
// => [0] => 3
// => [1] => Winterfall
// => [2] => 1
// => )
$element1 = array_pop($stack);
print_r("\n{$element1}\n");
// => 1
print_r($stack);
// => Array
// => (
// => [0] => 3
// => [1] => Winterfall
// => )
$element2 = array_pop($stack);
print_r("\n{$element2}\n");
// => Winterfall
print_r($stack);
// => Array
// => (
// => [0] => 3
// => )
https://repl.it/@hexlet/php-arrays-stack
Обратите внимание, что array_pop и array_push меняют исходный массив. При этом array_pop не только меняет массив, но и возвращает элемент, снятый со стека.
Рассмотрим задачку, которую очень просто решить с помощью стека. Кстати, ее нередко задают на собеседованиях, чтобы проверить ваши знания о базовых структурах данных:
Реализуйте функцию, которая проверяет парные скобки
<>,{},()и[]. Каждая открывающая скобка должна иметь закрывающую. Входом в функцию может быть()<>{}.Обратите внимание, что скобки не должны перекрываться. Например, сочетание
[({)}]не пройдет проверку, потому что здесь есть перекрытие фигурных и круглых скобок.
Решение со стеком выглядит так:
- Проверяем первый элемент строки:
- Если это открывающая скобка, заносим ее в стек
- Если это закрывающая скобка, достаем из стека последний добавленный элемент и смотрим, сочетаются ли эти скобки между собой. Неуспешная проверка покажет, что выражение не соответствует требуемому формату
- Таким образом проходим все элементы:
- Если в конце строки мы видим пустой стек, то все хорошо
- Если в конце строки мы видим в стеке какие-то элементы, то проверка не прошла (такое может произойти, если были открывающие скобки в начале строки и не было закрывающих скобок в конце строки)
Перейдем к коду:
<?php
function checkIfBalanced($expression)
{
$stack = [];
$startSymbols = ['{', '(', '<', '['];
$pairs = ['{}', '()', '<>', '[]'];
for ($i = 0, $len = strlen($expression); $i < $len; $i++) {
$curr = $expression[$i];
if (in_array($curr, $startSymbols)) {
array_push($stack, $curr);
} else {
$prev = array_pop($stack);
$pair = "{$prev}{$curr}";
if (!in_array($pair, $pairs)) {
return false;
}
}
}
return count($stack) === 0;
}
var_dump(checkIfBalanced('[')); // => bool(false)
var_dump(checkIfBalanced('}{')); // => bool(false)
var_dump(checkIfBalanced('(([<>]){})')); // => bool(true)
var_dump(checkIfBalanced('([{]})')); // => bool(false)
https://repl.it/@hexlet/php-arrays-stack-balancing
Разберем его построчно:
<?php
function checkIfBalanced(string $expression): bool
{
// Инициализируем стек
$stack = [];
// Инициализируем список открывающих элементов
$startSymbols = ['{', '(', '<', '['];
// Инициализируем список пар
$pairs = ['{}', '()', '<>', '[]'];
// Проходимся по строке от первого до последнего символа
for ($i = 0; $i < strlen($expression); $i++) {
$curr = $expression[$i];
// Если текущий символ находится в списке открывающих скобок, заносим его в стек
if (in_array($curr, $startSymbols)) {
array_push($stack, $curr);
} else { // Если элемент не входит в список открывающих скобок, считаем его закрывающей скобкой
// Извлекаем из стека последний добавленный элемент
$prev = array_pop($stack);
// Составляем из этих символов пару
$pair = "{$prev}{$curr}";
// Проверяем, входит ли эта пара в список $pairs
// Если да, все хорошо — двигаемся дальше
// Если нет, то символы не сбалансированы
if (!in_array($pair, $pairs)) {
return false;
}
}
}
// Если после обхода строки в стеке ничего нет, то все хорошо
return count($stack) === 0;
}
Предположим, что на вход функции попала строка [{]. Функция проверки сработает так:
- Первый символ
[входит в список открывающих скобок, заносим его в стек - Второй символ
{тоже входит в список открывающих скобок, заносим его в стек - Третий символ
]входит в список закрывающих скобок, поэтому достаем из стека последний символ{ - Из символов
{и]составляем пару{], которая не проходит проверку
Семантика
Кажется, что эти функции будет удобно использовать в повседневной практике. Например, с их помощью можно извлекать из массива последний элемент. В целом, array_pop позволяет так сделать, но это не лучшее решение:
- У этой операции есть побочный эффект — изменение исходного массива. Даже если массив нам больше не нужен, такой код вносит потенциальные проблемы, в будущем придется переписывать
- Такой подход нарушает семантику. Инструменты нужно использовать по назначению — иначе рождается код, который декларирует одно, а делает совершенно другое. Увидев программу с
array_popилиarray_push, любой опытный программист сразу подозревает, что в ней массив используется как стек. Чтобы проанализировать такой код, нужно тратить дополнительные усилия
Дополнительные материалы
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
