Стек и очередь

↑ 8.3 Алгоритмы и структуры данных · ← Предыдущая · → Следующая

Желательно~3 мин чтенияУровень: senior

Зачем это на собесе

Стек лежит в основе call stack, undo, парсинга; очередь — в event loop и обходе в ширину.

Стек (LIFO)

Последним пришёл — первым вышел. Операции push, pop, peek — O(1).

const stack: number[] = []
stack.push(1); stack.push(2); stack.pop()   // 2

Применение: история (undo), call stack, обход в глубину без рекурсии, разбор выражений, проверка скобок, «Next Greater Element» (монотонный стек).

function validBrackets(s: string): boolean {
  const pairs: Record<string, string> = { ')': '(', ']': '[', '}': '{' }
  const st: string[] = []
  for (const c of s) {
    if ('([{'.includes(c)) st.push(c)
    else if (st.pop() !== pairs[c]) return false
  }
  return st.length === 0
}

Очередь (FIFO)

Первым пришёл — первым вышел.

// массив: shift() O(n) на больших данных, лучше реализация на связном списке или двух индексах
class Queue<T> {
  #items = new Map<number, T>(); #head = 0; #tail = 0
  enqueue(x: T) { this.#items.set(this.#tail++, x) }
  dequeue(): T | undefined { const v = this.#items.get(this.#head); this.#items.delete(this.#head++); return v }
  get size() { return this.#tail - this.#head }
}

Применение: BFS, очередь задач, буфер событий, event loop (macro/microtask queues), rate limiting.

Варианты

• Deque: вставка и удаление с обоих концов;
• Приоритетная очередь (heap): извлечение минимума за O(log n), планировщики, Top-K;
• Кольцевой буфер: фиксированный размер, логи.

Задача: очередь на двух стеках

Добавляем в in, при dequeue переливаем в out, если пуст. Амортизированно O(1).

Вопросы с ответами

Как реализовать undo/redo?

Два стека: undo и redo. При действии кладём в undo и очищаем redo; при отмене переносим между стеками.

Почему shift() на большом массиве медленный?

Смещает все элементы на одну позицию, O(n). Для очереди лучше связный список или индексы.