Короткий и точный код Js для создания стека.
Стек — это линейная структура данных, которая следует определенному порядку выполнения операций. Порядок может быть LIFO (последним пришел, первым ушел) или FILO (первый пришел последним).
Реализация стека с использованием массивов:
- Использование метода push/pop (последним пришел первым ушел)
2. Использование метода shift/unshift
Примечание. Из этих двух методов shift/unshift крайне неэффективен, поскольку добавление/удаление элементов с начала массива требует больших затрат.
Создание стека с использованием связанного списка:
Все:
- толкать и поп
- подглядывать
Создание узла: он содержит значение и указатель.
Класс стека: он содержит первое значение, последнее значение и длину.
Push:добавление значения в верхнюю часть стека. (технически не меняется в связанном списке)
- Функция должна принимать значение.
- Создайте новый узел, используя это значение.
- Если в стеке нет узлов, задайте свойства first и last стека как вновь созданный узел.
- Если есть хотя бы один узел, создайте переменную, которая хранит текущее первое свойство в стеке.
- Сбросьте первое свойство, чтобы оно было вновь созданным узлом.
- Установите следующим свойством узла значение ранее созданной переменной.
- Увеличьте длину стека на единицу.
Извлечение:удалить из начала/верха стека (технически сдвиг в связанном списке)
- Если в стеке нет узлов, вернуть null.
- Создайте временную переменную для хранения первого свойства в стеке.
- Если есть только один узел, установите для первого и последнего свойства значение null.
- Если имеется более одного узла, установите первое свойство как следующее свойство для текущего первого.
- Уменьшите размер на единицу.
- Возвращает значение удаленного узла.
Peek:возвращает самое верхнее значение в стеке
Временная сложность стека:
- Доступ:O(n)
- Поиск:O(n)
- Вставка:O(1)
- Удаление:O(1)
Обзор:
Структура данных стека основана на принципе LIFO (последним пришел — первым обслужен). Элемент в последнем может быть доступен первым.
