Rivalry2

HTML Diff

0 added 0 removed

Original 2026-01-01

Modified 2026-02-26

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

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

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

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

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

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

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

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

9 <ul><li>Структура данных. Выше мы изучили этот термин</li>

10 <li>Конкретный тип данных. Типом данных может быть что угодно в зависимости от предпочтений создателей языка. Само это понятие всегда привязано к конкретному языку. Если бы создатели PHP захотели обозначать числа через тип данных Array, то никто не запретил бы эту абсурдную идею.</li>

11 <li>Абстрактный тип данных(АТД). Это теоретическое понятие, которое существует только на бумаге и в головах. Абстрактный тип данных определяется только операциями, которые можно выполнять над ним. При этом о способе хранения данных нам ничего не известно. АТД есть во всех языках, но везде его реализуют разные конкретные типы.</li>

12 </ul>АТД нередко путают с понятием "структура данных". Более того, часто они имеют одно и то же название.

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

14 <h2>Стек</h2>

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

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

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

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

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

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

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

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

23 <ul><li>Добавить в стек (push)</li>

24 <li>Взять из стека (pop)</li>

25 <li>Вернуть элемент с вершины стека без удаления (peek)</li>

26 <li>Проверить на пустоту (isEmpty)</li>

27 <li>Вернуть размер (size)</li>

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

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

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

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

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

33 </blockquote>Решение со стеком выглядит так:

34 <ol><li>Проверяем первый элемент строки:<ul><li>Если это открывающая скобка, заносим ее в стек</li>

35 <li>Если это закрывающая скобка, достаем из стека последний добавленный элемент и смотрим, сочетаются ли эти скобки между собой. Неуспешная проверка покажет, что выражение не соответствует требуемому формату</li>

36 </ul></li>

37 <li>Таким образом проходим все элементы:<ul><li>Если в конце строки мы видим пустой стек, то все хорошо</li>

38 <li>Если в конце строки мы видим в стеке какие-то элементы, то проверка не прошла (такое может произойти, если были открывающие скобки в начале строки и не было закрывающих скобок в конце строки)</li>

39 </ul></li>

40 </ol>Перейдем к коду:

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

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

43 <ol><li>Первый символ [ входит в список открывающих скобок, заносим его в стек</li>

44 <li>Второй символ { тоже входит в список открывающих скобок, заносим его в стек</li>

45 <li>Третий символ ] входит в список закрывающих скобок, поэтому достаем из стека последний символ {</li>

46 <li>Из символов { и ] составляем пару {], которая не проходит проверку</li>

47 </ol><h2>Семантика</h2>

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

49 <ol><li>У этой операции есть побочный эффект - изменение исходного массива. Даже если массив нам больше не нужен, такой код вносит потенциальные проблемы, в будущем придется переписывать</li>

50 <li>Такой подход нарушает семантику. Инструменты нужно использовать по назначению - иначе рождается код, который декларирует одно, а делает совершенно другое. Увидев программу с array_pop или array_push, любой опытный программист сразу подозревает, что в ней массив используется как стек. Чтобы проанализировать такой код, нужно тратить дополнительные усилия</li>

51 </ol>