Структуры данных на практике: стеки, очереди и интуиция Big-O
Выберите правильный контейнер для задачи - и код будет быстрым и понятным. Выберите неправильный - и ваш API начнёт задыхаться по мере роста данных.
Map и Set) - когда нужно мгновенно найти что-то по ключу. Понимание стоимости каждой операции - её Big-O - позволяет предсказать поведение кода на 10 элементах и на 10 миллионах.
- реализовать стек (LIFO) и применить его для истории отмен;
- реализовать очередь (FIFO) и применить её для очереди задач, избежав ловушки
shift(); - использовать
Set/Mapдля мгновенного поиска, удаления дубликатов и подсчёта; - читать нотацию Big-O и на интуиции различать
O(1),O(n)иO(n^2); - заменить случайный цикл
O(n^2)проходомO(n)через хеш-таблицу.
1. Стек - последним пришёл, первым вышел
Стек - это стопка. Вы добавляете наверх через push и убираете сверху через pop. Последнее, что вы положили, - это первое, что вы возьмёте: LIFO (Last In, First Out).
Аналогия. Представьте стопку тарелок. Чистую тарелку кладут наверх; следующая тарелка, которую вы возьмёте, - именно та, что вы только что положили. Из середины тарелку не вытаскивают.
Пример из жизни: история отмен. Каждый текстовый редактор хранит стек отмен. Каждая правка кладётся наверх. Когда вы нажимаете Ctrl+Z, редактор снимает (pop) самую последнюю правку и отменяет её. Поскольку новейшее изменение всегда сверху, отмена - это одна дешёвая операция pop.
В JavaScript обычный массив уже является стеком: arr.push(x) добавляет в конец, а arr.pop() убирает с конца, и обе операции - O(1), то есть постоянное время независимо от размера массива. Обёртка в маленький класс просто даёт операциям понятные имена:
class Stack {
constructor() { this.items = []; }
push(x) { this.items.push(x); }
pop() { return this.items.pop(); } // убрать + вернуть верхний
peek() { return this.items[this.items.length - 1]; } // посмотреть, не убирая
get size() { return this.items.length; }
}Ключевая дисциплина: стек позволяет трогать только верхушку. Это ограничение - преимущество: оно держит структуру быстрой, а ваше намерение - очевидным.