Стеки - цели, реализации и приложения

Путь к тому, чтобы стать отличным разработчиком, временами может быть чрезвычайно ухабистым. Stack Overflow, вероятно, является одним из самых популярных веб-сайтов и инструментов в наши дни, на который почти каждый разработчик ссылается хотя бы раз в день, если не чаще. Название происходит от одной из наиболее важных и распространенных структур данных, используемых в информатике, - стек. Мы рассмотрим, что такое переполнение стека, но для начала…

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

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

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

Общие операции

Вот некоторые из наиболее распространенных операций, выполняемых со стеком:

• Push: добавляет элемент в стек. Если стек заполнен, это приведет к переполнению стека (а не веб-сайта).
• Поп: удаляет элемент из стека. Если стек пуст, это приведет к недополнению стека.
• Peek or Top: возвращает верхний элемент стопки.
• isEmpty: Возвращает true, если стек пуст; если нет, возвращает false.

Реализация на JavaScript

Вот пример реализации стека в JavaScript с использованием массива - при условии, что стек может расти динамически.

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

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

Стек вызовов - это механизм, с помощью которого интерпретатор отслеживает свое место в сценарии, вызывающем несколько функций - какая функция в настоящее время выполняется и какие функции вызываются из этой функции. [1]

Разработчикам часто приходится писать асинхронный код при работе с JavaScript, особенно при выполнении запросов API. Например, если вы пишете приложение, которое использует внешний API, и вы делаете запрос на синхронную загрузку изображения, если Интернет работает медленно или API не работает, программа зависнет и не продолжит работу. Это происходит, когда вы запрашиваете данные синхронно, потому что JavaScript будет ждать и ничего не делать, пока запрос не будет завершен и ответ не будет отправлен обратно из API, прежде чем перейти к следующему оператору в вашем приложении.

В JavaScript ES6 есть много новых и старых способов написания асинхронного кода. Один простой, но отличный пример асинхронного JavaScript - setTimeout(). Этот метод использует веб-API браузеров, чтобы гарантировать, что код, вызываемый в качестве параметра метода, будет выполняться через заданный промежуток времени.

//setTimeout([callback], milliseconds)
function hello() {
    console.log('Hello world');
}
setTimeout(hello, 5000);
console.log("This will output before: 'Hello World'");

В приведенном выше блоке метод setTimeout() вызывает функцию hello() через 5000 миллисекунд. Хотя console.log() вызывается после вызова метода setTimeout(), веб-API принимает обратный вызов, который передается как первый параметр в методе setTimeout(), и помещает его в очередь обратного вызова до истечения заданного времени, в данном случае 5000 миллисекунд.

Цикл событий JavaScript

Вот краткое изложение каждого элемента цикла событий:

Стек (стек вызовов): это стек, в который весь ваш код JavaScript синхронно передается на протяжении всей программы. Интерпретатор считывает код, и по завершении выполнения каждый элемент удаляется из стека в хронологическом порядке. Если оператор в стеке вызовов является асинхронным, например setTimeout(), обещание или ajax() запрос, функция обратного вызова будет помещена в очередь обратного вызова, которая является другим стеком, где она будет ожидать выполнения. .

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

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

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

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

Полезные приложения

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

Некоторые (но не все) другие полезные приложения включают:

• Функции Redo-Undo (практически в любой программе)
• История браузера
• Прямые и обратные функции в веб-браузерах
• Проблемы с возвратом
• Переворот строки
• Топологическая сортировка и Сильно связанные компоненты

Итак ... что делает стеки такими особенными?

Сам шаблон стека! Вспомните LIFO (Последний вошел, первый ушел), единственный способ вставить или удалить элемент из стека, позволяющий настраивать буквально все, что угодно, только сверху. В информатике мы храним объекты в стеке, будь то числа, строки, адреса памяти или даже другие структуры данных; список можно продолжить!

Ссылки

[1] https://developer.mozilla.org/en-US/docs/Glossary/Call_stack