по взлому

Стек — это линейная структура данных, означающая, что элементы связаны последовательно (один за другим) так же, как очередь или связанный список. Думайте о стопке, как о стакане, наполненном разноцветным песком. Да, я уверен, что есть способы извлечь песок со дна, но, похоже, это может занять некоторое время. Лучший способ добраться до розового песка на изображении ниже — удалить то, что над ним. Более того, хотя, безусловно, возможно добавить песок на промежуточном уровне, например, между желтым и зеленым песком; Самый простой способ добавить в бутылку другой цветной песок — это добавить его доверху. Хотя абсолютно возможны более сложные вычисления (например, вставка в определенное место в списке, удаление в определенном месте в списке или поиск), эти операции имеют временную сложность 0(n). Наиболее подходящая работа со стеком включает в себя вставку и удаление верхнего узла или элемента. Эту концепцию лучше всего резюмировать так: ПЕРВЫМ ПОСЛЕДНИМ. Менее доступный элемент или узел внизу стопки всегда оказывается первым. В случае с бутылкой с песком это розовый песок. В результате розовый песок будет удаляться последним после удаления каждого слоя выше.

Покопавшись в структурах данных, я обнаружил, что лучший способ полностью окунуться в них — создать метод/фабрику для их создания. В JavaScript нет встроенного типа данных стека, поэтому единственный способ использовать их — создать собственный. Так я именно так и сделал! Для этого блога я собираюсь использовать небольшую программу, которую я создал с использованием HTML, CSS и vanilla JS, чтобы продемонстрировать основные функциональные возможности стека. Я хочу добавить больше логики и надеюсь, что к концу недели она будет размещена!

Вот краткий gif проекта проекта на данный момент…

Я начал с использования синтаксиса класса JavaScript ES6 и создал класс под названием Stack. Стек можно создать с помощью массивов или связанных списков, но для этой демонстрации я использовал массив.

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

Чтобы добавить данные в наш экземпляр стека, мы будем использовать метод push, определенный в нашем классе Stack. В случае построения стека с массивом логика наших методов экземпляра в значительной степени уже является прототипом методов самого объекта Array. На мой взгляд, понимание того, как работает массив, значительно облегчает понимание того, как работают стеки. Метод push (Array.prototype.push()) встроен в любой массив по законам прототипного наследования, и, поскольку stack.data — это массив, мы используем те же самые методы для достижения желаемого эффекта. Stack.push(value) предназначен для получения значения и добавления его к нашему stack.data. Если мы вернемся к бутылке, полной песка, то здесь мы добавляем песок нового цвета в верхнюю часть бутылки. Когда мы нажимаем, мы добавляем что-то на вершину стека. Точно так же в программе, которую я создал, мы, когда нажимаем push и добавляем элемент со значением в стек, оранжевое блюдо добавляется на вершину стека.

Для удаления из стека мы используем метод Stack.pop(). Опять же, pop() присущ массивам, так что это довольно просто. Когда мы вызываем pop() для массива, мы удаляем последний элемент. В стеке мы удаляем все, что находится наверху. Если бы мы вызвали метод pop() для нашей бутылки с песком, мы бы удалили фиолетовый слой, закрытый штопором. Если бы мы назвали это снова, мы бы убрали голубой песок. В моем методе pop() я добавил условие, чтобы убедиться, что длина нашего массива stack.data не пуста перед извлечением. Если он пуст, клиенту будет отправлено предупреждение о том, что из стека удалять нечего, так как длина стека равна 0. Аналогично, в мини-проекте, когда мы нажимаем pop(), он удаляет верхнее блюдо из списка. куча. Вы также можете заметить, что в верхнем левом углу экрана появляется небольшое предупреждение, дающее нам представление о значении недавно удаленного элемента. Я могу отобразить значение удаленного элемента, потому что мы возвращаем извлеченный элемент. Когда мы используем метод pop для массива, он по своей сути возвращает удаленное значение. Убедитесь, что вы вернули его в свой метод pop из стека, так как позже мы сможем использовать эту информацию для многих интересных вещей!

Последний метод в нашем классе Stack называется peek, и peek возвращает последний элемент в нашем массиве stack.data. В стеке единственный элемент, к которому у вас есть доступ, — это то, что находится сверху или самый последний элемент, помещенный в массив (последний элемент). Когда мы нажимаем кнопку просмотра в проекте, на пару секунд отображается значение верхнего элемента.

Хватит бутылочки разноцветного песка! Возможно, наиболее подходящим примером стека является стек вызовов в механизме выполнения JavaScript. Когда программа запускается, функции JavaScript помещаются в стек вызовов и последовательно удаляются из стека по мере их выполнения одна за другой. Когда программа завершает выполнение всего, это означает, что стек вызовов пуст. Например, в приведенном ниже примере мы используем ряд функций, последовательно вызываемых в функции с именем nums, которая перемещает массив до тех пор, пока сумма чисел в массиве не будет напечатана на консоли в функции printProduct.

В приведенном выше примере, когда мы запускаем программу, первым элементом, помещаемым в наш стек вызовов, является глобальный объект, поскольку мы являемся программой, работающей в узле. Затем следующим элементом, который нужно поместить в стек, является функция nums, у которой есть аргумент numsArr. Функция nums возвращает функцию с именем giveMeNums, так что giveMeNums помещается в стек, а затем printProduct помещается в стек. В печатном продукте в стек помещается console.log, а затем функция reduce(). Уменьшение находится на вершине стека! Пока снизу вверх наш стек вызовов выглядит так.

nums.reduce((сумма, число) =› …)

console.log(nums.reduce…)

printProduct(numsArr)

дайMeNums(numsArr)

числа (numsArr)

Глобальный()

Когда nums.reduce завершает выполнение и у нас есть сумма, reduce извлекается из стека. Теперь наш console.log запускается, и он извлекается из стека. printProduct выполнил свою логику, поэтому он выталкивается, затем дает MeNums, затем nums, затем глобальный. Бум! Теперь стек пуст.

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

В мини-проекте, когда количество блюд превышает определенное число, это происходит…