Обзор

Стек - это структура данных с правилом LIFO: последним пришел, первым ушел. Мы добавляем элемент на вершину стека и забираем тоже с вершины.

На интервью стек часто появляется там, где нужно помнить незавершенные состояния: открытые скобки, предыдущие элементы, путь обхода, вызовы рекурсии или кандидаты для будущего сравнения.

Стек

У стека есть три основные операции:

1. push - добавить элемент на вершину.

2. pop - снять элемент с вершины.

3. top или peek - посмотреть на верхний элемент, не удаляя его.

Все эти операции обычно выполняются за O(1).

stack.push("(");
stack.push("[");
stack.pop(); // "["
stack.pop(); // "("

Когда использовать

Стек хорошо подходит, когда в задаче есть такие признаки:

1. Нужно обрабатывать элементы в обратном порядке.

2. Нужно закрывать то, что было открыто раньше.

3. Нужно симулировать рекурсию итеративно.

4. Нужно хранить кандидатов, которые могут пригодиться позже.

5. Нужно найти следующий больший или меньший элемент через монотонный стек.

Самый простой пример - проверка скобочной последовательности. Каждая открывающая скобка кладется в стек. Когда встречается закрывающая, она должна соответствовать верхнему элементу стека.

Обычный стек и монотонный стек

В базовых задачах стек просто хранит историю. Например, открытые скобки или предыдущие директории в пути.

Монотонный стек хранит элементы в определенном порядке: возрастающем или убывающем. Такой стек часто помогает в задачах вида "найти ближайший больший элемент справа" или "сколько дней ждать до более теплой температуры".

Очередь на двух стеках

Стек работает по правилу LIFO, а очередь - по правилу FIFO. Казалось бы, это разные структуры, но очередь можно реализовать с помощью двух стеков.

Идея простая:

1. inStack - сюда кладем новые элементы при добавлении в очередь.
2. outStack - отсюда забираем элементы при извлечении.

При enqueue делаем push в inStack. При dequeue, если outStack пуст, перекладываем все элементы из inStack в outStack. После такого переноса порядок элементов разворачивается, и мы получаем нужный FIFO-порядок.

enqueue(x) -> inStack.push(x)
 
dequeue():
  if outStack пуст:
    пока inStack не пуст:
      outStack.push(inStack.pop())
  return outStack.pop()

Каждый элемент перекладывается между стеками не больше одного раза, поэтому операции работают за амортизированное O(1). Это частый вопрос на интервью: он проверяет, понимаете ли вы, как одна структура данных может имитировать другую.

Min stack и Max stack

Иногда нужен стек, который за O(1) отдает не только верхний элемент, но и текущий минимум или максимум. Для этого используют дополнительный стек.

В Min stack вместе с основным стеком хранят второй стек минимумов. При добавлении нового значения кладем в него либо само значение, либо текущий минимум, если новое число не меньше:

push(x):
  main.push(x)
  if minStack пуст или x <= minStack.top():
    minStack.push(x)
  else:
    minStack.push(minStack.top())

При pop снимаем элемент с обоих стеков. Тогда getMin() - это просто minStack.top().

Max stack устроен так же, только второй стек хранит текущие максимумы. Такой подход полезен, когда минимум или максимум нужен на каждом шаге алгоритма, а не только в конце.

Тот же результат можно получить с одним стеком, если хранить не отдельное число, а пару: значение и минимум на момент добавления этого значения.

push(x):
  currentMin = stack пуст ? x : min(x, stack.top().min)
  stack.push({ val: x, min: currentMin })
 
getMin():
  return stack.top().min

При push мы сразу знаем, какой минимум был в стеке после добавления нового элемента. При pop снимаем одну пару, и предыдущий минимум автоматически восстанавливается из следующей пары ниже. Дополнительный стек не нужен, а все операции по-прежнему выполняются за O(1).

Очередь с минимумом или максимумом

Идеи очереди на двух стеках и Min stack можно объединить. Если в inStack и outStack хранить не просто числа, а пары { val, min }, мы получим очередь, которая за O(1) отвечает на вопрос о минимуме во всей очереди.

При enqueue добавляем элемент в inStack так же, как в Min stack: вместе со значением сохраняем текущий минимум этого стека. При переносе элементов из inStack в outStack делаем то же самое для второго стека. Тогда минимум всей очереди - это минимум из минимумов обоих стеков:

getMin():
  if outStack пуст:
    return inStack.getMin()
  if inStack пуст:
    return outStack.getMin()
  return min(inStack.getMin(), outStack.getMin())

Max queue устроена так же, только в парах хранится текущий максимум.

Это полезно в задачах, где нужно поддерживать скользящее окно фиксированной длины k и на каждом шаге быстро узнавать минимум или максимум внутри окна. Окно можно представить как очередь: новый элемент добавляем в конец, элемент, который вышел за границу окна, удаляем с начала.

Например, в задаче Sliding Window Maximum нужно для каждого окна длины k найти максимальный элемент массива. Тот же паттерн работает и для минимума: на каждом шаге мы двигаем окно и спрашиваем у очереди текущий минимум или максимум.

На интервью такую задачу чаще решают через монотонную деку.

Дека - это очередь с двумя концами. В нее можно добавлять и удалять элементы и с начала, и с конца за O(1). Для скользящего окна это удобнее очереди на двух стеках: нам нужно быстро убирать устаревший элемент слева и добавлять новый справа, без перекладывания между стеками.

Монотонная дека хранит кандидатов на ответ в упорядоченном виде. Для максимума в окне элементы в деке идут по убыванию: самый большой - в начале. Когда приходит новое число, с конца деки удаляем все меньшие значения, потому что они уже не смогут стать максимумом, пока в окне есть это новое число. Когда левый элемент выходит из окна, удаляем его с начала деки, если он там лежит.

После таких операций максимум текущего окна всегда находится в начале деки. Идея похожа на Min stack и Max stack: мы заранее выбрасываем элементы, которые точно не понадобятся. Разница в том, что дека еще умеет удалять элементы с обоих концов, а это как раз нужно для окна фиксированной длины k.

Итоги

Стек полезен, когда текущий элемент должен взаимодействовать с последним незавершенным элементом. Он помогает заменить запутанные вложенные проверки на простую последовательность операций push и pop.

Стек лежит в основе структур для быстрого доступа к минимуму и максимуму. Min stack и Max stack отвечают на этот вопрос для всего стека, а монотонный стек и монотонная дека помогают в задачах на скользящее окно и поиск экстремумов в подмассиве.

Очередь можно реализовать на двух стеках, а если добавить в каждый стек хранение текущего минимума или максимума, получится очередь, которая за O(1) знает экстремум всего содержимого. Это полезно, когда окно данных двигается по массиву и на каждом шаге нужен быстрый ответ.

В обходе графов стек используют для итеративного DFS вместо рекурсии. Мы кладем стартовую вершину на стек, достаем вершины одну за другой и добавляем соседей, которые еще не посещены. Тот же принцип работает при обходе дерева в глубину: стек хранит путь, по которому алгоритм еще не закончил работу.

Монотонный стек часто применяют для поиска ближайшего большего или меньшего элемента слева или справа. Проходя массив, мы держим в стеке кандидатов в убывающем или возрастающем порядке и на каждом шаге сразу понимаем, для каких элементов текущее число и есть искомый ответ.