re:re:actable
Урок 033 минуты чтения

Что такое 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.

Документация

Wikipedia: Stack (abstract data type).

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам