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

Стек — структура LIFO (Last In, First Out): последний добавленный извлекается первым, как стопка тарелок. Очередь — FIFO (First In, First Out): первый пришедший обслуживается первым, как очередь в магазине. Deque — обе операции с обоих концов. Monotonic stack/queue — продвинутая оптимизация для задач «ближайший больший/меньший» и «sliding window max/min» за O(n) вместо O(n²). На собесах появляются в ~25% задач: парсинг скобок, RPN, BFS/DFS, sliding window.

Когда применять / Мотивация

Стек нужен, когда есть вложенность или откат:

• проверка скобок, парсинг выражений (shunting-yard);
• DFS без рекурсии (явный стек обходит проблему лимита call stack ~10k в JS);
• undo/redo в редакторах, история браузера;
• балансировка скобок в компиляторах;
• evaluate Reverse Polish Notation.

Очередь — для обработки по порядку поступления:

• BFS в графах (shortest path в unweighted);
• планировщик задач ОС (round-robin);
• event loop в Node.js / браузерах;
• message brokers (RabbitMQ FIFO);
• rate limiting через token bucket.

Monotonic stack/queue — мощная оптимизация:

• next greater element / previous smaller element за O(n);
• sliding window maximum/minimum за O(n);
• largest rectangle in histogram за O(n);
• moving min/max в финансовой аналитике, обработке сигналов.

Идея / Как работает

Стек в JS: обычный массив с push() и pop() — обе O(1).

Очередь в JS: наивно push() + shift(), но shift() это O(n) (сдвиг всех элементов). Для честной O(1) FIFO используют:

1. Circular buffer — массив фиксированного размера с двумя указателями.
2. Две-стековая очередь — inbox для enqueue, outbox для dequeue. Amortized O(1).
3. Связный список — head/tail указатели.

Monotonic stack: храним элементы в монотонном порядке (возрастающем или убывающем). При добавлении нового элемента выталкиваем нарушителей с вершины. Каждый элемент пушится и попается максимум 1 раз → амортизированно O(1) на элемент, итого O(n) для всего массива.

Почему monotonic deque работает

Если новый элемент arr[i] > arr[j] (j на конце deque), то arr[j] никогда уже не будет максимумом в окне, пока arr[i] живо — можно безопасно удалить. Это даёт амортизированно O(1) на элемент.

Реализация

Valid Parentheses (классика стека)

Задача: проверить корректность последовательности скобок ()[]{}. Для s = "({[]})" ответ true.

Идея: открывающие — push, закрывающие — pop и проверка соответствия. В конце стек должен быть пуст.

function isValid(s: string): boolean {
  const stack: string[] = [];
  const pairs: Record<string, string> = { '(': ')', '{': '}', '[': ']' };

  for (const char of s) {
    if (char in pairs) {
      stack.push(char); // открывающая
    } else {
      if (stack.length === 0) return false; // закрывающая без пары
      const top = stack.pop()!;
      if (pairs[top] !== char) return false; // не та закрывающая
    }
  }
  return stack.length === 0;
}

Очередь на двух стеках (amortized O(1))

class Queue<T> {
  private inbox: T[] = [];
  private outbox: T[] = [];

  enqueue(x: T): void {
    this.inbox.push(x); // O(1)
  }

  dequeue(): T | undefined {
    if (this.outbox.length === 0) {
      // Перекладываем из inbox в outbox — порядок инвертируется
      while (this.inbox.length) {
        this.outbox.push(this.inbox.pop()!);
      }
    }
    return this.outbox.pop(); // O(1) amortized
  }
}

Каждый элемент перемещается ровно дважды (inbox → outbox → out), отсюда amortized O(1).

Monotonic Stack — Next Greater Element

Для каждого элемента найти ближайший больший справа. Если нет — -1.

function nextGreaterElement(arr: number[]): number[] {
  const result = new Array(arr.length).fill(-1);
  const stack: number[] = []; // индексы; значения монотонно убывают сверху вниз

  for (let i = 0; i < arr.length; i++) {
    // Выталкиваем все индексы j, для которых arr[i] — следующий больший
    while (stack.length && arr[stack[stack.length - 1]] < arr[i]) {
      result[stack.pop()!] = arr[i];
    }
    stack.push(i);
  }
  return result;
}

Min Stack (getMin за O(1))

class MinStack {
  private stack: number[] = [];
  private mins: number[] = []; // минимум на каждом уровне

  push(x: number): void {
    this.stack.push(x);
    const currentMin = this.mins.length === 0 ? x : Math.min(x, this.mins[this.mins.length - 1]);
    this.mins.push(currentMin);
  }

  pop(): void {
    this.stack.pop();
    this.mins.pop();
  }

  top(): number { return this.stack[this.stack.length - 1]; }
  getMin(): number { return this.mins[this.mins.length - 1]; }
}

Трассировка Valid Parentheses

s = "({[]})", stack = []
─────────────────────────────────────
'(' открыв. → push          stack = ['(']
'{' открыв. → push          stack = ['(', '{']
'[' открыв. → push          stack = ['(', '{', '[']
']' закрыв. → top='[', pairs['[']==']' ✓
                            stack = ['(', '{']
'}' закрыв. → top='{', pairs['{']=='}' ✓
                            stack = ['(']
')' закрыв. → top='(', pairs['(']==')' ✓
                            stack = []
─────────────────────────────────────
Конец: stack пуст → true ✓

Сложность

Операция	Стек / Очередь	Monotonic stack
push / enqueue	O(1)	O(1) amortized
pop / dequeue	O(1) (amortized для 2-стековой)	O(1) amortized
peek / top	O(1)	O(1)
Size	O(1)	O(1)
Память	O(n)	O(n)

Monotonic stack обрабатывает массив длины n за O(n), хотя внутри есть while — каждый элемент пушится/попается максимум один раз.

Типичные ошибки и подводные камни

• arr.shift() для очереди в JS — это O(n)! Используйте две-стековую очередь, circular buffer или библиотеку deque.
• Не проверять пустоту: stack.pop() на пустом массиве возвращает undefined, не throws. Всегда if (stack.length) перед pop.
• Неправильная проверка скобок счётчиками: счётчик работает только для одного типа скобок. Для ()[]{} нужен стек, иначе ([)] пройдёт проверку, хотя некорректна.
• Глубокая рекурсия вместо явного стека: JS лимит ~10k. Для DFS на больших графах используйте итеративный DFS с явным стеком.
• Monotonic: путаница с порядком. Для next greater — стек убывающий (выталкиваем меньшие при встрече большего). Для next smaller — возрастающий.
• Indices vs values в monotonic stack: храните индексы, чтобы знать позицию выходящих за окно элементов (sliding window).
• Min Stack: дубликаты минимума. Если просто хранить «текущий min», при удалении узнать новый минимум невозможно. Хранение mins[] параллельно — простое решение.

Follow-up вопросы интервьюера

• Без стека для скобок? Только если один тип. Для нескольких типов нужен стек — счётчики не отслеживают порядок вложенности.
• Минимальное число вставок для корректности. После прохода: stack.length (незакрытые () + счётчик неспаренных ).
• Longest Valid Parentheses. Стек хранит индексы. Push -1 в начало. Для ( push индекс, для ) pop и считаем i - stack.top(). O(n).
• Evaluate RPN (["2","1","+","3","*"] → 9). Стек чисел: число — push, оператор — pop два, применить, push. O(n).
• Sliding Window Maximum. Monotonic deque индексов в убывающем порядке значений. Удаляем с конца меньшие при добавлении, удаляем с головы вышедшие за окно. O(n).
• Largest Rectangle in Histogram. Monotonic stack с возрастающими высотами. При выталкивании высоты — считаем максимальный прямоугольник с этой высотой. O(n).
• Daily Temperatures. Next greater element задача — monotonic stack индексов. Для каждого i ответ — расстояние до следующего большего.
• DFS без рекурсии. Явный стек: push корня, в цикле pop, обрабатываем, push детей. Полезно для глубоких деревьев.
• Implement Stack using Queues (и наоборот). Классические упражнения на понимание amortized analysis.

Чеклист на собес

• Не использую Array.shift() для очереди в JS.
• Знаю две-стековую реализацию очереди.
• Понимаю monotonic stack/deque и могу применить.
• Помню паттерны: скобки, next greater, sliding max.
• Проверяю пустоту стека перед pop.
• Знаю, что DFS можно сделать итеративно через явный стек.
• Понимаю amortized O(1) для 2-стековой очереди и monotonic stack.