Реализация стека в Javascript с методами массива

Это руководство знакомит вас со структурой данных стека JavaScript и показывает, как использовать массив в качестве стека с помощью методов push и pop.

Стек — это структура данных, содержащая список элементов. Он работает по принципу LIFO, т. е. «последний пришел, первый ушел», что означает, что последний добавленный элемент удаляется первым.

В стеке есть две основные операции, которые выполняются только в верхней части стека: push и pop. Операция push помещает элемент на вершину, тогда как операция pop удаляет элемент из вершины .

Стек имени происходит от аналогии с набором физических предметов, например, DVD-диска, книг, сложенных друг на друга.

Он имеет множество приложений. Например, самый простой — перевернуть слово. Для этого вы помещаете слово в стек буква за буквой и выталкиваете буквы из стека.

Другими приложениями стека являются механизм «отмены» в текстовых редакторах, анализ синтаксиса, вызов функций и преобразование выражений(инфикс в постфикс, инфикс в префикс, постфикс в инфикс и префикс в инфикс).

Тип JavaScript Array предоставляет методы push() и pop(), которые позволяют использовать массив в качестве стека.

Метод push()

Метод push() позволяет добавить один или несколько элементов в конец массива. Метод push() возвращает значение свойства length, указывающее количество элементов в массиве.

Если вы рассматриваете массив как стек, метод push() добавляет один или несколько элементов на вершину. В следующем примере создается пустой массив с именем stack и добавляются пять чисел по одному в конец массива stack. Это все равно, что запихнуть каждое число в верхнюю часть стека.

let stack = [];

stack.push(1);
console.log(stack); // [1]

stack.push(2);
console.log(stack); // [1,2]

stack.push(3);
console.log(stack); // [1,2,3]

stack.push(4);
console.log(stack); // [1,2,3,4]

stack.push(5);
console.log(stack); // [1,2,3,4,5]

На следующем рисунке показан каждый шаг в приведенном выше сценарии.

Изначально стек пуст. Каждый раз мы вызываем метод push() для добавления числа в стек. После 5 вызовов осталось 5 элементов.

Обратите внимание, что метод push() также позволяет добавлять несколько элементов в конец массива одновременно.

Метод pop()

Метод pop() удаляет элемент в конце массива и возвращает элемент вызывающей стороне. Если массив пуст, метод pop() возвращает неопределенное значение.

В следующем примере показано, как извлекать элементы из вершины стека с помощью метода pop().

console.log(stack.pop()); //  5
console.log(stack); // [1,2,3,4];

console.log(stack.pop()); //  4
console.log(stack); // [1,2,3];

console.log(stack.pop()); //  3
console.log(stack); // [1,2];

console.log(stack.pop()); //  2
console.log(stack); // [1];

console.log(stack.pop()); //  1
console.log(stack); // []; -> empty

console.log(stack.pop()); //  undefined

На рисунке ниже показан каждый шаг сценария.

Изначально в стеке 5 элементов. Метод pop() удаляет элементы в конце массива, т. е. в верхней части стека по одному. После пяти операций стек пуст.

Переворот строки с помощью стека JavaScript

В следующем примере показано, как инвертировать строку.

function reverse(str) {
    let stack = [];
    // push letter into stack
    for(let i = 0; i < str.length; i++) {
        stack.push(str[i]);
    }
    // pop letter from the stack
    let reverseStr = '';
    while(stack.length > 0) {
        reverseStr += stack.pop();
    }
    return reverseStr;
}
console.log(reverse('JavaScript Stack')); //kcatS tpircSavaJ

Как работает скрипт.

Функция reverse() принимает строковый аргумент и возвращает его обратную версию со следующей логикой:

1. Сначала прокрутите str и поместите каждую букву в массив stack.
2. Во-вторых, извлеките каждую букву из стека и создайте перевернутую строку.

В этом руководстве мы показали вам, как использовать массив в качестве структуры данных стека JavaScript, которая имеет две основные операции: push и pop.