Очередь и монотонный стек

Очередь — это FIFO, а монотонный стек решает «следующий больший элемент» за один проход.

Очередь — структура с дисциплиной FIFO (first in, first out); монотонный стек — стек, в котором элементы поддерживаются в возрастающем или убывающем порядке.

Очередь и deque

В очереди добавляем в конец, забираем из начала — как в живой очереди. В Python для этого используют collections.deque: append и popleft работают за O(1) (у обычного списка pop(0) — это O(n)).

from collections import deque

q = deque()
q.append("первый")
q.append("второй")
q.append("третий")
print(q.popleft())
print(q.popleft())
print(list(q))

Вывод:

первый
второй
['третий']

Классическая задача: следующий больший элемент

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

def next_greater(arr):
    result = [-1] * len(arr)
    stack = []  # индексы, ждущие большего элемента
    for i, x in enumerate(arr):
        while stack and arr[stack[-1]] < x:
            idx = stack.pop()
            result[idx] = x
        stack.append(i)
    return result

print(next_greater([2, 1, 2, 4, 3]))
print(next_greater([5, 4, 3, 2, 1]))
print(next_greater([1, 2, 3]))

Вывод:

[4, 2, 4, -1, -1]
[-1, -1, -1, -1, -1]
[2, 3, -1]

Как работает под капотом

В стеке лежат индексы элементов, которые ещё не нашли «большего справа», и они убывают по значению. Когда приходит новый элемент x, он закрывает (является ответом) для всех элементов на верхушке, что меньше него — мы их снимаем. Каждый элемент кладётся и снимается ровно один раз, поэтому суммарно операций O(n), несмотря на вложенный while. Это ключевая идея амортизации внутри монотонного стека.

Частые ошибки

• Хранить в стеке значения вместо индексов — тогда некуда записать ответ.
• Считать алгоритм O(n^2) из-за вложенного while — на деле он O(n) амортизированно.
• Использовать список с pop(0) для очереди — это O(n); берите deque.

Итог

• Очередь — FIFO; в Python используйте deque ради O(1) с обоих концов.
• Монотонный стек решает «следующий больший/меньший» за O(n).
• Каждый элемент входит и выходит из стека один раз — отсюда линейная сложность.