Введение в применение структур стека данных в информатике

Стеки в реальной жизни

Пример стопки из реальной жизни можно сравнить со стопкой книг в вашем доме, которые вы пообещали себе прочесть, но на самом деле никогда не уделяли времени или энергии для чтения. В этом случае, всякий раз, когда вы захотите добавить в стек, проще всего будет добавить его наверх. Кроме того, если вы хотите получить доступ к книге для чтения, возможно, вы возьмете книгу сверху, чтобы горная стопка книг не упала. Предполагая, что мы хотим полностью гарантировать, что стопка книг не упадет, мы хотели бы получать доступ к нашим книгам только сверху и добавлять дополнительные книги только сверху. Если вы хотите добраться до книги, которая не находится на вершине стопки, вам нужно удалить все книги, которые находятся над указанной книгой.

Операции со стеками

Как и в наших книгах, в структуре данных стека вы можете получить доступ только к элементу на вершине стека. Существуют определенные операции, которые мы можем использовать для вставки, удаления и оценки данных в нашем стеке. Теперь представьте, что наша стопка книг — это набор чисел (данных), которые мы укладываем в массив. Одним из методов вставки данных в массив является push(), который вставляет данные на вершину стека.

Теперь, если бы мы хотели удалить последний вставленный элемент из стека, мы бы использовали метод pop(). Это приложение разработчики называют FILO (первый пришел последним) и LIFO (последний пришел — первым ушел). Взгляните на пример на рис. 1.2, и вы увидите, как работает LIFO.

Эти два метода определяют наши основные операции при оценке стеков в массивах. Однако есть и другие операции, которые позволяют нам лучше понять структуру данных нашего стека.

• Метод top() позволяет вернуть последний вставленный элемент, не удаляя его.
• Метод size() позволяет нам вернуть размер или количество элементов в стеке. Учитывая рисунок 1.1, размер нашего стека будет равен 4.
• Метод isEmpty() возвращает true, если стек пуст, иначе он возвращает false.
• Точно так же метод isFull() возвращает значение true, если стек заполнен, иначе он возвращает значение false.

Хотя стек считается ограниченной структурой данных (где над ним выполняется лишь небольшое количество операций), существуют и другие типы и методы (например, связанные списки). В приведенных выше примерах описываются вводные операции, которые можно реализовать при оценке массива стека.

Реализация стека вызовов

Javascript и другие языки используют то, что разработчики называют стеком вызовов. Стек вызовов можно рассматривать как «список дел» вызовов функций, где (в большинстве случаев) важен порядок выполнения задач. Ранее мы упоминали, как стеки полезны для ведения списка операций. Поддерживающий аспект здесь — это то, что мы бы назвали нашим «списком дел». Например, если каждая операция в нашем стеке вызовов отвечает за другой вызов функции или создание определенной подпрограммы, порядок их размещения определяет порядок, в котором вызывается каждая операция. Следовательно, важно помнить, что будущие операции не могут быть выполнены до тех пор, пока предыдущая операция в этом стеке не будет передана.

Как мы видим на рис. 1.3, в этом случае стек вызовов в Javascript будет использоваться для отслеживания истории вызываемых вещей (в данном случае истории вызовов функций, которые еще предстоит реализовать). В этом случае стек вызовов решает последствия реализации функций, которые полагаются друг на друга при вызове. Как видно выше, вызовы в стеке зависят друг от друга, и порядок важен.

• Первая функция вызывает функцию два, вторая функция вызывает третью функцию, а третья функция вызывает console.trace стека вызовов.
• В этом примере мы можем видеть использование LIFO, поскольку процесс с 1 по 3 заполняет стек вызовов вызываемыми функциями.
• Процесс (3–6) один за другим вызывает функцию последнего вставленного в качестве первого возвращаемого.

Это может быть рудиментарное описание реализации, но оно обеспечивает упрощенное визуальное объяснение сложности стеков вызовов.

Заключение

Стеки имеют множество применений. Например, в некоторых фреймворках, таких как ReactJS, стеки также используются для упрощения рекурсивных подпрограмм, где состояние каждого вызова сохраняется в кадре стека и помещается в стек.

Полезность стековых структур данных и их реализации предоставляет программе или программному обеспечению инструменты для ведения списка операций, которые необходимо вызывать в упорядоченном порядке, чтобы программное обеспечение работало должным образом. Таким образом, сведение к минимуму возможных последствий того, что наша программа «развалится», будет похоже на вытаскивание одной книги из середины огромной стопки.

Справочные источники и дополнительное чтение

Стек — Isaac Computer Science: https://isaaccomputerscience.org/concepts/dsa_datastruct_stack?examBoard=all&stage=all

Введение в стеки — Youtube: https://www.youtube.com/watch?v=I37kGX-nZEI&ab_channel=NesoAcademy

Объяснение стека вызовов JS за 9 минут — Youtube: https://www.youtube.com/watch?v=W8AeMrVtFLY&ab_channel=ColtSteele

Структура данных стека — ГИС: http://wiki.gis.com/wiki/index.php/Stack_(data_structure)

Стек вызовов — Википедия: https://en.wikipedia.org/wiki/Call_stack#Functions_of_the_call_stack