Структура данных стека — одна из самых популярных линейных структур данных. Это фундаментальная часть программирования и одна из самых простых для изучения. Из-за своей простоты он может показаться довольно скучным и бесполезным, но в некоторых приложениях он может быть очень полезен.
Прежде чем мы углубимся в них, давайте кратко рассмотрим, что такое структура данных стека.
Что такое структура данных стека?
Стек представляет собой линейную структуру данных, которая следует принципу последний пришел – первый ушел (LIFO). Последний вставленный элемент является первым удаленным элементом.
Наиболее распространенная аналогия стопки - это стопка тарелок, расположенных одна поверх другой. Вы берете сверху, и как только вы закончите, вы моете его и кладете обратно наверх.
Это хорошая аналогия, но я не думаю, что она вполне подходит. Что делать, если ваша верхняя тарелка не была очищена должным образом или вы хотите взять нижнюю, чтобы использовать все свои тарелки? Что, если есть разные виды тарелок, а вашей любимой нет наверху?
Более точная аналогия — банка теннисных мячей. Он больше соответствует определению стека и его операций и следует принципу ЛИФО.
Теперь, когда мы нарисовали картину, давайте посмотрим на структуру данных.
В стеке есть 3 основные операции:
- Push — добавление элемента в верхнюю часть стека.
- Pop – удаление элемента из вершины стека.
- Peek — получение значения верхнего элемента
Кроме того, есть две общие операции, которые вы можете включить в зависимости от их необходимости. У вас может быть операция для проверки того, пуст ли стек, или, если у вас есть предел емкости, у вас может быть операция для проверки полной структуры данных.
Если вы хотите более глубоко погрузиться в стеки, вот отличный туториал.
Приложения структуры данных стека
Стеки довольно часто используются для решения многих задач, связанных с информатикой. Есть много проблем, которые можно было бы очень легко решить с помощью структуры данных стека. Вот список задач, которые решаются с помощью стековой структуры данных.
- Вычисление или преобразование арифметического выражения (например, префикс в постфикс)
- Проверка скобок
- Разворот строки
- Возвращение
- Поиск в глубину
В дополнение к этим проблемам стеки используются для управления памятью и для функций современных приложений, с которыми мы регулярно сталкиваемся. Функции отмены/возврата и кнопки «вперед/назад» в наших браузерах — две такие функции, которые реализуют стеки, которые мы используем ежедневно!
Другая область, о которой вы, возможно, слышали, где используется структура данных стека, — это стек вызовов/выполнений. Чтобы лучше изучить структуру данных, давайте углубимся в то, что такое стек вызовов. Это также поможет нам понять, как программа выполняет код javascript.
Стек вызовов
Поначалу стек вызовов может быть немного сложным для понимания, но это важный шаг, который должен сделать каждый разработчик, потому что он помогает нам понять логический поток или наши операции и действительно помогает нам понять такие сложные темы, как рекурсивное программирование.
Многие языки используют стек вызовов, но давайте пока сосредоточимся на Javascript. Вот что MDN говорит о стеке вызовов.
Стек вызовов — это механизм, позволяющий интерпретатору (например, интерпретатору JavaScript в веб-браузере) отслеживать свое место в сценарии, вызывающем несколько функций, — какая функция выполняется в данный момент, а какие функции вызывается из этой функции и т. д.
Таким образом, стек вызовов в основном используется для отслеживания вызовов функций. Поскольку Javascript будет выполнять код в том порядке, в котором он написан, сверху вниз. Javascript является однопоточным и синхронным, поэтому он выполняет только одну операцию за раз.
Есть две ключевые части информации для понимания стека вызовов.
- Каждый раз, когда вызывается функция, вы добавляете (push) в стек вызовов.
- Каждый раз, когда функция возвращает или завершает выполнение, вы удаляете (pop) из стека вызовов.
Давайте посмотрим на пример. Попробуйте представить, как работает код, прежде чем читать дальше:
Давайте разберем код шаг за шагом и посмотрим, как он будет работать.
function one() {
two();
console.log("Finish with one");
}
function two() {
three();
console.log("Finish with two");
}
function three() {
console.log("hi");
console.log("Finish with three");
}
Эта часть кода изначально не запускается, потому что это всего лишь определения функций, а вызовы функций не выполняются.
const name = "Ursula"; console.log(name);
Здесь первый вызов функции выполняется, когда вы console.log(name). Поскольку это вызов функции, он добавляется в стек. Как только функция завершает выполнение (она записывает имя в консоль), она извлекает вызов функции из стека вызовов. Помните, что javascript возвращает undefined по умолчанию, когда завершает выполнение функции. «Возврат» отмечает завершение функции и операцию извлечения из стека вызовов.
one();
В этом последнем фрагменте кода выполняются вызовы нескольких функций, и вы действительно понимаете, как работает стек вызовов.
- Добавляет функцию one() в стек вызовов. Затем начинается выполнение кода внутри функции one.
- В теле one() у нас есть еще один вызов функции, поэтому нам нужно поместить его в стек вызовов. Здесь важно понимать, что функция one() еще не завершила выполнение, а console.log("Finish with one") еще не запущен. Мы добавляем two() в стек вызовов, а все остальное откладывается на потом, пока мы не закончим то, что в two. Вот как сейчас выглядит стек вызовов:
- То же самое происходит, когда мы вызываем функцию three(). Код console.log("Finish with two") еще не запущен, а вызов функции three() добавлен в стек.
- В вызове функции three() javascript выполняет два оператора console.log, а затем завершает выполнение функции и извлекает три из стека вызовов. В этот момент следующим элементом в стеке вызовов является функция two(), поэтому javascript возвращается к точке, где был сделан вызов внутри функции two().
- Еще раз, как только остальная часть функции two() завершена, следующим элементом является функция one(), и аналогичные шаги повторяются, поэтому после завершения выполнения two() мы знаем, что есть только первый вызов функции, который был сделан. в нашем стеке вызовов.
- После завершения кода в функциональном блоке one() в стеке вызовов выполняется последняя операция извлечения, и мы возвращаемся к строке 18, где продолжаем выполнение остальной части кода.
Краткое содержание
Стек — это линейная структура данных, которая следует принципу LIFO и может быть лучше всего представлена в виде банки с теннисными мячиками. Несмотря на то, что это может показаться довольно простым, это может быть практическим решением многих проблем, где это уместно.
Он также реализован в стеке вызовов, где он используется для отслеживания вызовов функций, которые выполняются в ходе выполнения программы. Более глубокий взгляд на стек вызовов помог нам лучше понять структуру данных стека и логический поток программы javascript.
Здесь — это ссылка, которая проходит по коду, продемонстрированному в этой статье. Если вы хотите узнать больше о стеках, воспользуйтесь приведенным ниже списком ресурсов, в которых содержится дополнительная информация о структуре данных стека.
Спасибо за прочтение. Надеюсь, вы лучше понимаете структуру данных стека и ее применение.
