Структуры данных стека: краткий обзор

Почему стековые структуры данных являются важной частью современных языков программирования?

Когда я проходил буткемп этой зимой, один термин, который постоянно возникал и казался вездесущим, независимо от языка программирования, — это структуры данных.

Проще говоря, структуры данных используются для хранения данных организованным образом, что делает его эффективным и удобным для доступа и изменения указанных данных по мере необходимости. Сейчас существует ряд структур данных, таких как списки, связанные списки, деревья и т. д. Мы собираемся поговорить о структуре данных стека.

Структуры данных стека

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

Теперь, когда я слышу слово «стопка», первое изображение, которое приходит мне на ум, — это стопка блинов, а структура данных стека очень похожа на стопку блинов… Ну, отчасти!

Точно так же, как стопка блинов, где блин сверху съедается первым, стек следует подходу «последним пришел — первым вышел» (LIFO), когда элемент, добавленный в стек последним, выполняется или обрабатывается первым.

Приложения структуры данных стека

Вот некоторые из приложений структуры данных стека:

• Вычисление арифметических выражений

Стек используется для оценки арифметических операций путем преобразования инфиксных выражений в постфиксные выражения, которые затем оцениваются на основе приоритета арифметических выражений.

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

• Обратные данные

Стек также можно использовать для обращения строки. Из-за свойства стека «First In Last Out» строка может быть обращена путем добавления (PUSH) символов строк по порядку в стек, который затем может быть удален (POP) из стека в обратном порядке.

• Функции отмены/возврата/возврата

Функции отмены или возврата, присутствующие почти во всех приложениях, используют стек для возврата к предыдущему состоянию. Каждый раз, когда вы отменяете действие, оно выталкивается из стека.

• Рекурсивные функции

Когда рекурсивная функция выполняется, функция вызывает себя с увеличенным/измененным параметром несколько раз, пока не будет выполнено определенное условие. Стек используется для организации порядка, в котором функции вызываются и выполняются в данном экземпляре, поскольку их может быть несколько.

• Обработка вызовов функций

Другое применение стека — обработка вызовов функций. Функции или блоки добавляются в стек в том порядке, в котором они вызывались, а затем выполнялись в порядке поступления первыми последними. Это можно уточнить, объяснив стек вызовов в javascript.

Стек вызовов в Javascript

Стек вызовов – это механизм, с помощью которого интерпретатор (например, интерпретатор JavaScript в веб-браузере) может отслеживать свое место в сценарии, вызывающем несколько "функций" – какая функция выполняется в данный момент и какая функции вызываются из этой функции и т. д.

Чтобы уточнить приведенное выше объяснение MDN, стек вызовов добавляет функции в стек по мере того, как эта конкретная функция вызывается, а затем она выполняется. Если эта функция вызывает другую функцию, то эта функция добавляется на «верх» стека. Когда вторая функция возвращает значение, оно удаляется из стека и продолжает выполнение предыдущей функции. Стек также имеет ограниченный объем памяти, поэтому, если функции превышают объем памяти стека, это приводит к «переполнению стека».

• Когда приведенный выше код выполняется изначально, в стек добавляется глобальная функция контекста выполнения, которая обозначается как main() или global().
• Затем вызывается функция приветствия, которая добавляется в стек.
• Выполняется функция приветствия, которая, в свою очередь, вызывает функцию приветствия.
• Как только функция hello завершает свое выполнение, она извлекается из стека.
• Затем функция приветствия завершает свое выполнение и удаляется из стека.
• И, наконец, основная функция удаляется из стека, и программа завершается.
• Это также пример синхронного javascript.

Заключение

• Структура данных стека использует принцип First In Last Out для выполнения функций/процессов.
• Методы push и pop используются для добавления и удаления функций в стек.
• Некоторые приложения стека — это выполнение рекурсивных функций, арифметических выражений и обращение данных.
• Интерпретатор Javascript в браузере использует механизм стека вызовов для отслеживания функций, вызываемых в программе.

Рекомендации