2. Стек (Stack)

Абстрактный тип данных, представляющий собой список элементов, организованных по принципу LIFO (last in — first out).

2.1 Структура стека

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

    ArrayBasedStack

             lastElementIndex
              |
              v
    ┌───┬───┬───┬───┬───┐
    | 1 | 2 | 3 |   |   |
    └───┴───┴───┴───┴───┘

2.2 Операции над стеком

2.2.1 Добавление элемента в стек (push)

/**
 * Добавление элемента в стек O(1)
 * @param {*} key
 */
push(key) {
    // Если стек полон -- ошибка O(1)
    if (this._length === this._lastElementIndex + 1) {
        throw new Error('Stack is full');
    }

    // Добавление элемента в конец массива O(1)
    this._array[this._lastElementIndex + 1] = key;

    // Увеличение индекса последнего элемента O(1)
    this._lastElementIndex++;
}

2.2.2 Возрат элемента из стека (top)

/**
 * Возврат элемента из стека O(1)
 * @returns {*}
 */
top() {
    // Возврат последнего элемента из массива O(1)
    return this._array[this._lastElementIndex];
}

2.2.3 Удаление элемента из стека (pop)

/**
 * Удаление элемента из стека O(1)
 */
pop() {
    // Уменьшение индекса последнего элемента O(1)
    this._lastElementIndex--;
}

2.2.3 Проверка на пустоту (empty)

/**
 * Проверка стека на пустоту O(1)
 * @returns {boolean}
 */
empty() {
    // Проверка на равенство индекса последнего элемента -1 O(1)
    return this._lastElementIndex === -1;
}

2.3 Примеры использования

2.3.1 Проверка на последовательности скобок на сбалансированность

Сбалансированная последовательность: (([])())

Несбаланированная последовательность: ([), )(

/**
 * Проверка последовательности скобок на сбалансированность O(n)
 * @param {string} sequence
 */
function isBalanced(sequence) {
    const stack = new ArrayBasedStack(100);

    // Итерирование по последовательности O(n)
    for (let i = 0; i < sequence.length; i++) {
        const parenthesis = sequence[i];

        // Если текущая скобка открывающая -- добавление в стек O(1)
        if (parenthesis === '(' || parenthesis === '[') {
            stack.push(parenthesis);
        } else if (parenthesis === ')' || parenthesis === ']') {

            // Если текущая скобка закрывающая, и стек пуст -- возврат false O(1)
            if (stack.empty()) {
                return false;

            // Если текущая скобок закрывающая, и на вершине стека
            // находится соответствующая ей открывающая скобка -- удаление
            // открывающей скобки из стека O(1)
            } else if (parenthesis ===  ')' && stack.top() === '(') {
                stack.pop();
            } else if (parenthesis ===  ']' && stack.top() === '[') {
                stack.pop();

            // Во всех остальных случаях -- возврат false O(1)
            } else {
                return false;
            }
        }
    }

    // Если после итерирования по последовательности в стеке остались
    // скобки -- последовательность несбалансированна. Иначе -- сбалансированна. O(1)
    return stack.empty();
};