Позвольте мне задать тон: всего 11 недель назад я практически ничего не знал о программировании. 'Привет, мир'? Что это такое? Приквел к Спокойной ночи, луна? Для петель? Что случилось с 1, 2 и 3 петлями? Функции? Да, я работаю.. если во мне достаточно кофе.

Вы поняли идею. С тех пор я участвую в крещении огнем, широко известном как учебный лагерь веб-разработки или кодирования. Перемотаем вперед 3 изнурительных, битком набитых месяца спустя — я Нео. Мое офисное кресло похоже на принадлежность к «Навуходоносору». Мои инструкторы? Морфеус. Они подключают меня и нажимают скачать. Ого. Я знаю JavaScript. Вау! Я знаю Express. Я знаю SQL. Я встретил этого человека Руби на каких-то железнодорожных путях..

И вот, ученик готов стать мастером. Я здесь, чтобы загрузить свои знания о структурах данных стека прямо в вашу кору головного мозга. Вы будете...ждать... Стекировать структуры данных? Я вообще ничего об этом не знал!

Или я?

Мы все знаем, что такое стопка на обычном компьютерном языке без бип-буп — стопка блинов, стопка грязной посуды в раковине, стопка пыльных компакт-дисков на полке, которые Spotify сделал устаревшими. . Набор предметов, наложенных друг на друга в линейном порядке. А структура данных — это просто способ организации, управления и хранения данных в памяти, чтобы ваша система знала, как получить к ним доступ.

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

Если ты первый, ты последний

Таким образом, вновь добавленные элементы всегда оказываются на вершине стека, но как насчет удаления или удаленияданных? В стеке доступен только элемент на вершине стека. Это связано с принципом, известным как Последним пришел, первым ушел (LIFO), который работает именно так, как звучит; в этом примере элемент 3 был добавлен в стек последним, поэтому его необходимо удалить, прежде чем можно будет получить доступ к элементу 2 или удалить его, что, в свою очередь, такженужно должен быть удален до того, как можно будет получить доступ к элементу 1. Короче говоря, каждый раз, когда вам нужно добраться до определенного элемента в стеке, все, что находится поверх него, должно быть удалено в первую очередь.

Bop It, Twist It, Pull It!

Так как же это на самом деле работает? Что ж, есть несколько операций, которые можно выполнять со стеком, в том числе:

  • Push: Добавляет элемент на вершину стека
  • Pop: Удаляет элемент с вершины стека
  • IsEmpty: Проверяет, пуст ли стек (возвращает логическое значение, true/false)
  • IsFull: Проверяет, заполнен ли стек (логическое значение)
  • Peek: Получает значение верхнего элемента, не удаляя его

Давайте вернемся к предыдущей диаграмме, чтобы увидеть ее в действии.

Если вы когда-нибудь работали с массивами в программировании, то понятия Push, Pop и даже самого стека будут сразу понятны, стоит только наклонить голову вправо..

В этом случае первый элемент массива эквивалентен нижнему элементу стека (1), а последний элемент — вершине стека (3). Имея это в виду, .push и .pop работают одинаково; они повлияют только на последний элемент массива (верхнюю часть стека). Конечно, с помощью массивов мы также можем получить доступ к определенным элементам по их индексам без необходимости .popпрокладывать к ним путь.

Мы также можем проверить, пуст ли массив, вызвав для него метод .length, хотя это вернет количество элементов в массиве, а не логическое значение, например IsEmpty/. IsFullда.

Но массивы могут быть заполнены практически любым количеством элементов!

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

Откуда оно знает?

Ну, во-первых, указатель с именем TOP используется для отслеживания верхнего элемента в стеке. При инициализации стека его значение устанавливается равным -1, чтобы мы могли проверить, пуст ли стек, сравнивая TOP == -1. При нажатии элемента значение TOP увеличивается, и новый элемент помещается в позицию, на которую указывает TOP. При извлечении элемента возвращается элемент, на который указывает TOP, и его значение уменьшается.

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

Вот мой номер, так что позвони мне, может быть

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

Когда файл кода запускается на JavaScript (и других языках), функции добавляются (Push) в стек вызовов в том порядке, в котором они вызываются. Здесь вызов функции startWashingMachine() происходит в строке 15, затем startDishwasher() вызывается в строке 16.

Мы видим startWashingMachine() в нижней части стека вызовов, поскольку он был вызван первым, а затем startDishwasher() был добавлен сверху, как обычно в стеке. Однако стек вызовов работает на основе FIFO (First In, First Out), а не LIFO. Поскольку это асинхронные функции, то есть существует задержка между их вызовом и окончанием выполнения части кода (здесь моделируется setTimeOut() функций), они затем будут переданы из стека вызовов в веб-API, чтобы предотвратить любые другие действия. код от блокировки от запуска в то же время.

По мере разрешения тайм-аутов они передаются в очередь обратного вызова, которая сама по себе является еще одним стеком FIFO. На этом этапе цикл обработки событий проверит, пуст ли стек вызовов (isEmpty), и только когда возвращаемое значение равно true , он начнет передавать элементы из очереди обратного вызова обратно в стек вызовов, чтобы завершить выполнение всего оставшегося кода этих функций (в этом примере console.log для «Посудомоечная машина завершена», за которым следует «Стиральная машина завершена»)

Но что еще они могут сделать?

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

То, что на первый взгляд может показаться архаичным (Я могу получить доступ только к верхнему элементу?), на самом деле представляет собой чрезвычайно продвинутую и фундаментальную структуру, на которую опираются все наши системы.

Это было мое понимание структур данных стека, когда я был 11-недельным младенцем в мире программирования. Пусть это послужит капсулой времени, к которой я смогу вернуться в будущем, чтобы увидеть, сколько еще мне еще предстоит узнать.

Если вам нужен более тщательный анализ структур данных стека, посетите следующие ссылки:

Особая благодарность Lighthouse Labs!