Стек — 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
// => )

Обратите внимание, что 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)

Разберем его построчно:

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