Когда использовать список, стек, очередь и дек?

Линейные структуры различаются не содержимым, а набором дешёвых операций. Массив быстро обращается по индексу, связный список меняет связи рядом с известным узлом, стек выдаёт…

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

Связный список

Узел хранит значение и ссылку на следующий узел, а двусвязный вариант — ещё и на предыдущий. Вставка после известного узла занимает O(1), но поиск k-й позиции требует прохода O(k). Утверждение «вставка в список всегда постоянна» неверно, если позицию сначала нужно найти.

Стек

Операции push и pop работают с одной вершиной по принципу LIFO. Стек моделирует вложенность: открывающие скобки, возвраты рекурсии, отмену действий. При чтении закрывающей скобки проверяют не только тип верхнего символа, но и то, что стек не пуст.

Очередь

FIFO-порядок нужен для обработки заявок и обхода графа по слоям. Элементы добавляют в хвост, удаляют из головы. Реализация сдвигом всего массива после удаления делает операцию дорогой; кольцевой буфер перемещает только индексы начала и конца.

Дек

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

Таблица выбора

Для сценария выпишите операции и требуемые оценки: случайный индекс, вставка рядом с узлом, последний вошёл — первый вышел или первый вошёл — первый вышел. Затем выберите структуру и отдельно проверьте пустое состояние. Так ответ обосновывается контрактом операций, а не знакомым названием контейнера.

Монотонный дек хранит только возможных победителей

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

from collections import deque

def sliding_maximum(values: list[int], width: int) -> list[int]:
    if not 1 <= width <= len(values):
        raise ValueError("invalid window width")
    candidates: deque[int] = deque()
    answer: list[int] = []
    for index, value in enumerate(values):
        while candidates and candidates[0] <= index - width:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(index)
        if index + 1 >= width:
            answer.append(values[candidates[0]])
    return answer

Каждый индекс добавляется и удаляется не более одного раза, поэтому весь алгоритм работает за O(n), несмотря на вложенные while.

Практика: выбор структуры по контракту

Реализуйте проверку скобок стеком, очередь задач кольцевым буфером и скользящий максимум деком. Для каждого решения перечислите разрешённые операции и их стоимость. Протрассируйте максимум на [4, 1, 3, 5, 2, 5] с окном 3, показывая содержимое дека после шага. Затем замените индексы значениями и найдите пример, где невозможно правильно удалить элемент, покинувший окно.