PHP поставляется с библиотекой, называемой SPL (Standard PHP Library). Кроме прочего, она содержит набор классов, реализующих популярные структуры данных, такие как стек или очередь.
<?php
$q = new SplStack();
$q->push(3);
$q->push(10);
$q->pop(); // 10
$q->pop(); // 3
Несмотря на то, что SPL встроен в язык, конкретно к структурам данных есть множество претензий со стороны сообщества, как по производительности, так и по интерфейсам классов. Всё это вылилось в создание расширения php-ds (DS). Подробнее о нем читайте в статье https://medium.com/@rtheunissen/efficient-data-structures-for-php-7-9dda7af674cd. php-ds можно установить как обычный пакет https://github.com/php-ds/polyfill. Вся документация доступна здесь: https://php.net/manual/ru/book.ds.php.
DS включает в себя Vector, Deque, Map, Set, Stack, Queue, PriorityQueue, Pair. Эти структуры в жизни обычного веб-разработчика нужны не каждый день, но всё же такое случается. Если вы с ними не знакомы, то имеет смысл хотя бы прочитать о них в википедии.
Stack
Стек — это коллекция типа "Последний вошёл, первый вышел" (Last In, First Out или LIFO), которая позволяет работать только с самым верхним (последним) значением. Итерация происходит от конца к началу с удалением взятого элемента.
<?php
$stack = new \Ds\Stack();
$stack->push(3);
$stack->push(10);
$stack->pop(); // 10
$stack->pop(); // 3
print_r($stack->toArray());
Методы pop()
и push()
составляют основной интерфейс класса. push()
добавляет элемент (или элементы) на стек, pop()
- снимает со стека.
Перепишем с использованием этого стека функцию, которая разбиралась в курсе "PHP: массивы". Напомню задачу:
Необходимо реализовать функцию, которая проверяет, что парные символы сбалансированы. То есть каждый открывающий символ имеет закрывающий, и они не перекрываются, например, так: [{]}
. К таким символам в нашем случае относятся <>, {}, (), []
. Входом в функцию может быть ()<>{}
. Такой пример проходит проверку, а вот этот уже нет: [({)}]
. Здесь происходит перекрытие фигурных и круглых скобок.
<?php
function checkIfBalanced(string $expression): boolean
{
// инициализируем стек
$stack = new \Ds\Stack();
// инициализируем список открывающих элементов
$startSymbols = ['{', '(', '<', '['];
// инициализируем список пар
$pairs = ['{}', '()', '<>', '[]'];
// Проходим по строке от первого до последнего символа
for ($i = 0; $i < strlen($expression); $i++) {
$curr = $expression[$i];
// Если текущий символ находится в списке открывающих символов, то заносим его в стек
if (in_array($curr, $startSymbols)) {
$stack->push($curr);
} else { // Если элемент не входит в список открывающих, то считаем, что это закрывающий символ
$prev = $stack->pop();
// Составляем из этих символов пару
$pair = "{$prev}{$curr}";
// Проверяем, что она входит в список $pairs. Если входит, то все правильно, двигаемся дальше; если нет,
// то это автоматически означает, что символы не сбалансированы
if (!in_array($pair, $pairs)) {
return false;
}
};
}
// Если стек оказался пустым после обхода строки, то значит все хорошо
return sizeof($stack) === 0;
}
Объектный стиль никак не повлиял на алгоритм решения. Кода не стало меньше, он не стал проще. С другой стороны, такой подход в PHP распространен крайне широко.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
- Статья «Как учиться и справляться с негативными мыслями»
- Статья «Ловушки обучения»
- Статья «Сложные простые задачи по программированию»
- Вебинар «Как самостоятельно учиться»
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.