PHP: Массивы
2026-02-26 20:32 Diff
https://ru.hexlet.io/courses/php-arrays/lessons/stack/theory_unit

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

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

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

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

Каноническая организация хранения массива — это непрерывный блок памяти. В таком случае индекс играет роль смещения по ней. Именно поэтому индексация в массивах начинается с нуля — индекс указывает на начало этого блока, а индекс под номером 1 уже считается смещением. Сложность в том, что в PHP нет настоящих массивов. Об этом вы узнаете в следующем курсе.

Кроме массивов существует множество других структур данных: списки, хеш-таблицы, деревья, графы, стек, очередь и другие. Если мы правильно выберем структуру данных под решаемую задачу, мы сможем заметно упростить код и устранить запутанную логику.

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

Стоит разделять три понятия:

  • Структура данных. Выше мы изучили этот термин
  • Конкретный тип данных. Типом данных может быть что угодно в зависимости от предпочтений создателей языка. Само это понятие всегда привязано к конкретному языку. Если бы создатели PHP захотели обозначать числа через тип данных Array, то никто не запретил бы эту абсурдную идею.
  • Абстрактный тип данных (АТД). Это теоретическое понятие, которое существует только на бумаге и в головах. Абстрактный тип данных определяется только операциями, которые можно выполнять над ним. При этом о способе хранения данных нам ничего не известно. АТД есть во всех языках, но везде его реализуют разные конкретные типы.

АТД нередко путают с понятием «структура данных». Более того, часто они имеют одно и то же название.

В этом уроке мы разберем один из самых простых и важных абстрактных типов данных – стек.

Стек

Термином стек называют упорядоченную коллекцию элементов. В стеке добавление и удаление элементов всегда происходит с вершины стека — начала или конца коллекции:

У стека есть аналогии из реальной жизни. Само слово stack переводится с английского как «стопка», поэтому любую стопку можно рассматривать как стек. Например, чтобы изменить стопку книг, нужно добавить одну книгу сверху или убрать одну снизу.

Еще один пример стека — это стопка шипучих таблеток в упаковке:

Здесь есть дно, поэтому мы не можем сразу достать самую нижнюю таблетку. Открыв упаковку, мы заберем самую верхнюю таблетку, которую положили последней. Такие стеки называют LIFO (Last In First Out) — последний элемент выходит из стека первым.

Вспомните, как исполняется любая программа. Первые функции вызывают вторые, вторые вызывают третьи и так далее. Программа доходит до самой глубокой функции и получает ее значение. Чтобы вернуть это значение, программа запускает обратный процесс: переходит от самой глубокой функции к менее глубокой, поднимается на уровень выше, а потом еще выше вплоть до самой внешней функции. Другими словами, вызов функций — добавление элемента в стек, а возврат — снятие со стека.

Именно так все устроено на аппаратном уровне. Если во время выполнения произойдет ошибка, мы увидим трассировку стека (stack trace).

Еще один пример из программирования — кнопка «Назад» в браузере. История посещений — это стек ссылок, в котором кнопка «Назад» извлекает последний элемент.

Стек — абстрактный тип данных со следующим набором операций:

  • Добавить в стек (push)
  • Взять из стека (pop)
  • Вернуть элемент с вершины стека без удаления (peek)
  • Проверить на пустоту (isEmpty)
  • Вернуть размер (size)

В PHP стек можно создать на основе массивов. Для этого используются функции array_push, array_pop, empty и count:

Обратите внимание, что array_pop и array_push меняют исходный массив. При этом array_pop не только меняет массив, но и возвращает элемент, снятый со стека.

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

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

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

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

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

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

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

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

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

Семантика

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

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