После массивов и списков лайков на этот раз мы рассмотрим новый тип структуры данных — стеки.

Стеки: концепции

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

# Что такое стеки?

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

Таким образом, все операции со стеком выполняются только с одного конца через наиболее доступную информацию, находящуюся в ВЕРХНЕЙстеке. Наименее доступная информация в стеке находится в НИЗУ. Обычно мы называем добавление нового элемента помещениемего в стек. С другой стороны, мы называем удаление элемента извлечениемиз стека.

# Зачем использовать стеки?

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

  1. Оценка выражений…

Использование стека может быть полезно при вычислении выражений, состоящих из операндов, операторов и/или скобок. Как правило, это можно сделать тремя способами: инфиксным, постфиксным или префиксным выражением.

2. Возврат…

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

Стеки: реализация на JavaScript

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

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

Вот так…

Фрагмент выше говорит сам за себя, но если у вас есть какие-либо вопросы, пожалуйста, используйте раздел комментариев…

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

Стеки: Теперь твоя очередь…

# Задача 1

Используйте предпочитаемый язык программирования для реализации структуры данных стека с использованием массивов вместо связанных списков.

# Задача 2

Можете ли вы предложить решение проблемы отмены/возврата? Тем не менее, используйте предпочитаемый язык программирования…

Подождите секунду, пожалуйста! Прежде чем мы уйдем, если хотите, давайте подключимся…