Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Стек PHP: Массивы

Алгоритмы — это хорошо, но структуры данных — еще лучше.

Структура данных — это конкретный способ хранения и организации данных. Иногда удобно организовать данные одним образом, иногда — другим. Здесь все зависит от решаемых задач.

Одну структуру данных мы уже изучили — это массив. По своей структуре массив — это совокупность элементов, к которым есть индексированный доступ (доступ по индексу).

С точки зрения хранения все работает немного сложнее. Массивы бывают разные, и внутри языка они реализуются тоже по-разному.

Каноническая организация хранения массива — это непрерывный блок памяти. В таком случае индекс играет роль смещения по ней. Именно поэтому индексация в массивах начинается с нуля — индекс указывает на начало этого блока, а индекс под номером 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 не только меняет массив, но и возвращает элемент, снятый со стека.

Рассмотрим задачку, которую очень просто решить с помощью стека. Кстати, ее нередко задают на собеседованиях, чтобы проверить ваши знания о базовых структурах данных:

Реализуйте функцию, которая проверяет парные скобки <>, {}, () и []. Каждая открывающая скобка должен иметь закрывающую. Входом в функцию может быть ()<>{}.

Обратите внимание, что скобки не должны перекрываться. Например, сочетание [({)}] не пройдет проверку, потому что здесь есть перекрытие фигурных и круглых скобок.

Решение со стеком выглядит так:

  1. Проверяем первый элемент строки:
    • Если это открывающая скобка, заносим ее в стек
    • Если это закрывающая скобка, достаем из стека последний добавленный элемент и смотрим, сочетаются ли эти скобки между собой. Неуспешная проверка покажет, что выражение не соответствует требуемому формату
  2. Таким образом проходим все элементы:
    • Если в конце строки мы видим пустой стек, то все хорошо
    • Если в конце строки мы видим в стеке какие-то элементы, то проверка не прошла (такое может произойти, если были открывающие скобки в начале строки и не было закрывающих скобок в конце строки)

Перейдем к коду:

<?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;
}

Предположим, что на вход функции попала строка [{]. Функция проверки сработает так:

  1. Первый символ [ входит в список открывающих скобок, заносим его в стек
  2. Второй символ { тоже входит в список открывающих скобок, заносим его в стек
  3. Третий символ ] входит в список закрывающих скобок, поэтому достаем из стека последний символ {
  4. Из символов { и ] составляем пару {], которая не проходит проверку

Семантика

Кажется, что эти функции будет удобно использовать в повседневной практике. Например, с их помощью можно извлекать из массива последний элемент. В целом, array_pop позволяет так сделать, но это не лучшее решение:

  1. У этой операции есть побочный эффект — изменение исходного массива. Даже если массив нам больше не нужен, такой код вносит потенциальные проблемы, в будущем придется переписывать
  2. Такой подход нарушает семантику. Инструменты нужно использовать по назначению — иначе рождается код, который декларирует одно, а делает совершенно другое. Увидев программу с array_pop или array_push, любой опытный программист сразу подозревает, что в ней массив используется как стек. Чтобы проанализировать такой код, нужно тратить дополнительные усилия

Дополнительные материалы

  1. array_push
  2. array_pop

Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff
Рекомендуемые программы
профессия
от 6 300 ₽ в месяц
Разработка веб-приложений на Laravel
10 месяцев
с нуля
Старт 28 марта

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»