Что такое stack?
На этой странице
Stack - структура данных по принципу LIFO: last in, first out. Последний добавленный элемент извлекается первым. В JavaScript стек удобно реализовать через Array.push и Array.pop.
Вопрос
Что такое stack и в каких задачах он применяется?
Пример
const stack: number[] = []
stack.push(1)
stack.push(2)
stack.push(3)
console.log(stack.pop()) // 3
console.log(stack.pop()) // 2Основные операции
| Операция | Смысл | Сложность |
|---|---|---|
push | добавить наверх | O(1) |
pop | снять сверху | O(1) |
peek | посмотреть верх | O(1) |
isEmpty | проверить пустоту | O(1) |
Generic Stack
class Stack<T> {
private items: T[] = []
push(value: T): void {
this.items.push(value)
}
pop(): T | undefined {
return this.items.pop()
}
peek(): T | undefined {
return this.items[this.items.length - 1]
}
get size(): number {
return this.items.length
}
}Где используется stack?
- проверка скобок;
- undo/redo;
- DFS;
- monotonic stack;
- call stack;
- парсинг выражений;
- backtracking.
Проверка скобок
function isValid(s: string): boolean {
const stack: string[] = []
const pairs = new Map([
[')', '('],
[']', '['],
['}', '{'],
])
for (const char of s) {
if (!pairs.has(char)) {
stack.push(char)
} else if (stack.pop() !== pairs.get(char)) {
return false
}
}
return stack.length === 0
}Стек хранит открытые скобки, которые еще ждут свою пару. Закрывающая скобка всегда должна совпадать с последней открытой - это и есть LIFO. Пример для "([]{})":
| char | Действие | stack после |
|---|---|---|
( | открывающая, кладем | ( |
[ | открывающая, кладем | ( [ |
] | снимаем [ - пара совпала | ( |
{ | открывающая, кладем | ( { |
} | снимаем { - пара совпала | ( |
) | снимаем ( - пара совпала | пусто |
Стек пуст - строка корректна. Для "(]" на шаге ] мы снимем (, пара не совпадет, ответ false. Для "((" в конце в стеке останутся скобки, ответ тоже false.
Что отвечать на собеседовании?
Stack - LIFO-структура: последний добавленный элемент выходит первым. В JS ее обычно реализуют через массив и операции push/pop, которые подходят лучше, чем unshift/shift. Stack нужен для задач со вложенностью, откатом, DFS, скобками и монотонными структурами.
Что важно помнить: частые ошибки
- Использовать
shift/unshiftвместоpush/pop. - Не проверять пустой stack.
- Путать stack и queue.
- Не учитывать память
O(n). - Терять порядок при проверке скобок.
Мини-шпаргалка
- Stack = LIFO.
pushдобавить.popснять.peekпосмотреть.- JS Array подходит.
- Частые задачи: brackets, DFS, undo, monotonic stack.