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

Массив умеет всё: читать по индексу, вставлять в середину, искать. Стек умеет ровно две вещи: положить на верх и снять с верха. Казалось бы, это регресс — мы намеренно отбираем у себя возможности. Но именно в этом сила: ограничение интерфейса — это не потеря функциональности, а приобретение гарантий.

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

Эта статья — про три дисциплины доступа к линейной последовательности и про то, во что они превращаются, когда встречаются с реальностью: с кэш-линиями, с многопоточностью, с сетевыми сокетами и с backpressure.

1. Три дисциплины доступа

Все три структуры — это абстрактные типы данных (ADT): контракт операций, а не способ хранения. Один и тот же стек можно построить на массиве, на связном списке, на дереве и даже на файле — контракт не изменится.

Дек (double-ended queue, произносится «дэк») — это надмножество: он умеет всё, что умеют стек и очередь. Возникает разумный вопрос: зачем тогда стек и очередь отдельно, если есть дек?

Ответ — двойной. Во-первых, специализированная реализация быстрее: стек на голом массиве с одним указателем top бьёт любой дек по константе. Во-вторых, узкий тип — это документация: параметр Stack<Task> в сигнатуре сообщает читателю про порядок обработки больше, чем комментарий на три строки.

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

2. Стек

2.1 Инвариант и реализация на массиве

Стек на динамическом массиве — это массив плюс целое число top, обозначающее количество элементов. Инвариант: элементы занимают ячейки [0, top), вершина — это arr[top - 1].

class ArrayStack:
    """Стек на динамическом массиве. push/pop — амортизированный O(1)."""

    def __init__(self):
        self._data: list = []

    def push(self, item) -> None:
        self._data.append(item)          # амортизированный O(1)

    def pop(self):
        if not self._data:               # явная проверка вместо IndexError
            raise IndexError("pop из пустого стека")
        return self._data.pop()          # строго O(1): удаление с конца

    def peek(self):
        if not self._data:
            raise IndexError("peek на пустом стеке")
        return self._data[-1]

    def __len__(self) -> int:
        return len(self._data)

Ключевое слово — амортизированный. append иногда вызывает реаллокацию и копирование всего массива, то есть Θ(n). Но поскольку ёмкость растёт геометрически (в CPython — примерно в 1.125 раза сверх текущего размера, в Go и C++ — обычно вдвое), суммарная стоимость n вставок остаётся Θ(n), а значит на операцию приходится O(1). Подробный разбор с методом потенциалов — в статье Асимптотика, амортизация и модель памяти.

Есть тонкость, о которой забывают: амортизированный O(1) ≠ предсказуемый O(1). В системе реального времени или в аудиопотоке единичный скачок на Θ(n) с реаллокацией — это пропущенный дедлайн. Там берут стек фиксированной ёмкости, выделенный заранее, и переполнение считают ошибкой, а не поводом расти.

2.2 Стек на связном списке

Альтернатива — односвязный список, где push/pop работают с головой (см. Связные списки):

from dataclasses import dataclass
from typing import Any, Optional

@dataclass(slots=True)
class _Node:
    value: Any
    next: Optional["_Node"]

class LinkedStack:
    """Строго O(1) в худшем случае, но платим указателем и промахом кэша на элемент."""

    def __init__(self):
        self._top: Optional[_Node] = None
        self._size = 0

    def push(self, item) -> None:
        self._top = _Node(item, self._top)   # аллокация узла — O(1) без реаллокаций
        self._size += 1

    def pop(self):
        if self._top is None:
            raise IndexError("pop из пустого стека")
        node = self._top
        self._top = node.next
        self._size -= 1
        return node.value

Сравнение честное:

На практике массив выигрывает почти всегда. Список берут, когда нужен гарантированный худший случай, когда элементы огромные и копировать их при реаллокации дорого, или когда нужна персистентность: неизменяемый стек-список позволяет держать сразу много версий, разделяя хвост (об этом — Персистентные и конкурентные структуры).

2.3 Стек вызовов: почему рекурсия — это стек

Самый важный стек в вашей программе вы никогда не создавали явно. При вызове функции процессор кладёт на стек фрейм: адрес возврата, сохранённые регистры, локальные переменные, аргументы, не влезшие в регистры. Возврат снимает фрейм. Это буквально LIFO, реализованный аппаратно через регистр указателя стека.

Отсюда следуют практические выводы:

• Переполнение стека (RecursionError в Python, StackOverflowError в JVM, SIGSEGV в C) — это не «слишком сложная рекурсия», а исчерпание фиксированного региона памяти. По умолчанию это 8 МБ на главном потоке Linux (ulimit -s), около 512 КБ–1 МБ на поток в JVM, и 8 КБ с динамическим ростом у горутин Go — именно поэтому в Go рекурсия глубиной в миллионы кадров не падает.
• Любую рекурсию можно превратить в цикл с явным стеком. Это стандартный приём, когда глубина непредсказуема — например, обход дерева пользовательского JSON или графа зависимостей.

def dfs_iterative(graph: dict, start):
    """Обход в глубину без рекурсии: явный стек вместо стека вызовов.
    Время O(V + E), память O(V) — своя, из кучи, а не из 8 МБ стека потока."""
    visited = set()
    stack = [start]
    order = []
    while stack:
        node = stack.pop()
        if node in visited:
            continue
        visited.add(node)
        order.append(node)
        # разворот нужен, чтобы порядок обхода совпал с рекурсивным вариантом
        for neighbour in reversed(graph[node]):
            if neighbour not in visited:
                stack.append(neighbour)
    return order

Обратите внимание на строчку с reversed: стек переворачивает порядок, и без разворота итеративный DFS обойдёт соседей в обратном порядке относительно рекурсивного. На корректность это не влияет, на воспроизводимость тестов — очень даже. Подробнее про обходы — в статье Графы: представления и свойства.

2.4 Монотонный стек — приём, который стоит знать наизусть

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

def next_greater(nums: list[int]) -> list[int]:
    """Для каждого i — индекс ближайшего справа элемента, большего nums[i], иначе -1.
    Время O(n): каждый индекс попадает в стек ровно один раз и выходит не более раза.
    Память O(n) на стек в худшем случае (строго убывающий массив)."""
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []            # индексы, значения по ним строго убывают

    for i, value in enumerate(nums):
        # пришёл элемент больше вершины — значит он и есть ответ для вершины
        while stack and nums[stack[-1]] < value:
            result[stack.pop()] = i
        stack.append(i)

    return result                     # оставшиеся в стеке так и не нашли большего


assert next_greater([2, 1, 2, 4, 3]) == [3, 2, 3, -1, -1]

Ключ к анализу сложности: внутренний while выглядит как вложенный цикл, но каждый индекс выталкивается не более одного раза за всё выполнение. Суммарное число итераций while по всей программе ограничено n — это амортизационный аргумент в чистом виде.

Тот же паттерн решает «максимальный прямоугольник в гистограмме» (задача, лежащая в основе maximalRectangle), вычисление температурных ожиданий, парсинг выражений с приоритетами и построение декартова дерева за линейное время.

2.5 Парсинг: стек как проверка вложенности

Проверка сбалансированности скобок — учебный пример, но его промышленный аналог (валидация JSON/XML, сопоставление тегов, восстановление после ошибок в парсере) работает ровно так же.

PAIRS = {")": "(", "]": "[", "}": "{"}

def is_balanced(text: str) -> bool:
    """O(n) по времени, O(n) по памяти в худшем случае '((((('."""
    stack: list[str] = []
    for ch in text:
        if ch in "([{":
            stack.append(ch)
        elif ch in PAIRS:
            if not stack or stack.pop() != PAIRS[ch]:
                return False
    return not stack

Заметьте: стек здесь хранит не «сколько скобок открыто», а какие именно — счётчика недостаточно, потому что типы скобок должны совпадать. Это типичный признак того, что нужен именно стек, а не счётчик: когда закрытие обязано знать, чему оно парное.

3. Очередь

3.1 Ошибка, которую делают все

queue = []
queue.append(x)   # O(1) — норм
queue.pop(0)      # Θ(n) — катастрофа

list.pop(0) в Python (как и Remove(0) у List<T> в C#, как и erase(begin()) у std::vector) сдвигает все оставшиеся элементы влево. Обработка очереди из n элементов превращается в Θ(n²). На тесте из 100 элементов вы этого не заметите; на проде с 200 000 задач сервис ляжет.

Правильный ответ в Python — collections.deque, у которого popleft() строго O(1).

3.2 Кольцевой буфер

Основная реализация очереди фиксированной ёмкости — кольцевой буфер (ring buffer, circular buffer): непрерывный массив, в котором логическое начало и конец «ездят» по кругу.

class RingBuffer:
    """Очередь фиксированной ёмкости. Все операции — строго O(1) в худшем случае.
    Ёмкость обязана быть степенью двойки: тогда деление по модулю
    заменяется на битовую маску (индекс & mask), что заметно дешевле idiv."""

    def __init__(self, capacity: int):
        if capacity <= 0 or capacity & (capacity - 1) != 0:
            raise ValueError("ёмкость должна быть степенью двойки")
        self._buf: list = [None] * capacity
        self._mask = capacity - 1
        self._head = 0      # индекс первого элемента
        self._size = 0      # количество элементов; хранить size проще, чем tail

    def push(self, item) -> None:
        if self._size == len(self._buf):
            raise OverflowError("буфер переполнен")
        tail = (self._head + self._size) & self._mask
        self._buf[tail] = item
        self._size += 1

    def pop(self):
        if self._size == 0:
            raise IndexError("pop из пустой очереди")
        item = self._buf[self._head]
        self._buf[self._head] = None       # снимаем ссылку, чтобы GC собрал объект
        self._head = (self._head + 1) & self._mask
        self._size -= 1
        return item

    def __len__(self) -> int:
        return self._size

Три инженерных решения в этом коде стоит разобрать отдельно.

Почему size, а не tail. Классическая реализация хранит два индекса, head и tail, и тогда состояния «пусто» и «полно» неотличимы: в обоих head == tail. Обходят это либо жертвуя одной ячейкой (буфер считается полным при (tail + 1) % cap == head), либо храня отдельный счётчик, либо используя монотонно растущие 64-битные счётчики без взятия модуля (так делает LMAX Disruptor — переполнение uint64 при миллиарде сообщений в секунду наступит через сотни лет). Хранение size — самый читаемый вариант для однопоточного кода, но для многопоточного он плох: два потока начинают конкурировать за одну и ту же переменную.

Почему степень двойки. x % n для произвольного n — это аппаратное деление, 20–40 тактов. x & (n - 1) — один такт. При миллионах сообщений в секунду разница видна на графиках.

Почему self._buf[self._head] = None. В языках с трассирующим GC оставленная в массиве ссылка не даёт собрать объект — это классическая утечка через контейнер. ArrayDeque в Java делает elements[h] = null ровно по этой причине, и в комментарии к коду это названо «to let gc do its work».

Состояния буфера удобно смотреть как автомат:

Именно эти две заметки на диаграмме — то, ради чего кольцевой буфер существует в проде. Структура сама по себе тривиальна; вся сложность — в политиках на границах.

3.3 Очередь из двух стеков

Академически изящная конструкция, которая регулярно всплывает на собеседованиях и — что важнее — объясняет амортизационный анализ лучше любого учебника.

class TwoStackQueue:
    """FIFO поверх двух LIFO. Амортизированный O(1), худший случай одной операции Θ(n)."""

    def __init__(self):
        self._in: list = []      # сюда пишем
        self._out: list = []     # отсюда читаем, порядок уже перевёрнут

    def enqueue(self, item) -> None:
        self._in.append(item)                    # всегда O(1)

    def dequeue(self):
        if not self._out:                        # перелив только когда out пуст
            if not self._in:
                raise IndexError("dequeue из пустой очереди")
            while self._in:
                self._out.append(self._in.pop()) # Θ(k), но амортизированно O(1)
        return self._out.pop()

Доказательство амортизированной оценки методом бухгалтерского учёта: назначим каждому enqueue стоимость 3 единицы вместо 1. Одна тратится на сам append, две откладываются «на счёт» элемента. Когда случается перелив, элемент оплачивает своими двумя единицами pop из in и push в out. Итоговый pop из out оплачивается стоимостью самого dequeue. Счёт никогда не уходит в минус, значит суммарная стоимость n операций — O(n).

Практический смысл у конструкции есть, и не только олимпиадный: она даёт персистентную очередь в функциональных языках, где двусвязные списки неудобны. Именно так устроена очередь в Erlang/Elixir (:queue из OTP — пара списков) и в стандартной библиотеке Clojure. Если вы работаете с Elixir, загляните в обзор трека Elixir — иммутабельность там заставляет пересобирать интуицию о структурах данных с нуля.

Учтите главный минус: латентность рваная. Один dequeue из тысячи занимает в тысячу раз больше остальных. Для батчевой обработки это не важно, для p99-латентности API — фатально. Существуют «реально-временные» варианты (real-time queue Окасаки) с инкрементальным переливом по одному элементу за операцию — они дают строгий O(1) в худшем случае ценой констант.

4. Дек

4.1 Как его реализуют на самом деле

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

• collections.deque (CPython) — двусвязный список блоков по 64 указателя. Указатели тратятся раз на 64 элемента, а внутри блока обход идёт последовательно по памяти. Отсюда быстрые append, appendleft, pop, popleft — все O(1) — и при этом медленный доступ по индексу в середину: O(n), потому что нужно прошагать по блокам.
• std::deque (C++) — массив указателей на блоки фиксированного размера. Даёт O(1) индексацию (два разыменования) и O(1) вставку в оба конца, но итераторы инвалидируются коварно, а константа выше, чем у vector.
• ArrayDeque (Java) — кольцевой буфер поверх массива с удвоением ёмкости. Официальная документация прямо рекомендует его вместо Stack и вместо LinkedList в роли очереди (docs.oracle.com).
• Go не имеет дека в стандартной библиотеке: идиома — срез плюс ручной кольцевой буфер, либо канал с буфером, если нужна конкурентность. Про идиомы см. обзор трека Go.

Правило выбора: ArrayDeque/collections.deque — почти всегда верный ответ, если вам нужен стек или очередь и вы не пишете lock-free код. LinkedList в роли очереди — антипаттерн: та же асимптотика при худшей константе и большем потреблении памяти.

4.2 Скользящий максимум — канонический алгоритм на деке

Задача: дан массив и окно ширины k, найти максимум в каждом положении окна. Наивно — O(n·k). С кучей — O(n log k) (см. Кучи и приоритетные очереди). С деком — O(n).

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

from collections import deque

def sliding_window_max(nums: list[int], k: int) -> list[int]:
    """Максимум в каждом окне ширины k.
    Время O(n): каждый индекс входит и выходит из дека ровно по одному разу.
    Память O(k): в деке одновременно не больше k индексов."""
    if k <= 0 or k > len(nums):
        raise ValueError("некорректная ширина окна")

    dq: deque[int] = deque()   # индексы; значения по ним строго убывают
    result: list[int] = []

    for i, value in enumerate(nums):
        # 1. выбрасываем слева индексы, вышедшие за окно
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. выбрасываем справа всех, кто уже не может быть максимумом
        while dq and nums[dq[-1]] <= value:
            dq.pop()
        dq.append(i)
        # 3. окно набралось — голова дека и есть максимум
        if i >= k - 1:
            result.append(nums[dq[0]])

    return result


assert sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], 3) == [3, 3, 5, 5, 6, 7]

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

Тот же приём лежит в основе вычисления скользящих агрегатов в потоковых системах и в оптимизации динамического программирования «deque optimization» (например, задача о прыжках с ограниченной длиной).

5. Конкурентные варианты

Здесь заканчивается алгоритмика и начинается системное программирование. Как только к очереди обращаются несколько потоков, наивная реализация ломается: два потока могут прочитать один и тот же tail и записать в одну ячейку.

5.1 SPSC-очередь: один писатель, один читатель

Самый частый и самый быстрый случай — Single Producer, Single Consumer. Его можно сделать полностью без блокировок, только на атомарных операциях с правильными барьерами памяти.

// SPSC-кольцевой буфер: lock-free при ровно одном писателе и одном читателе.
// Ключевая идея: писатель владеет head, читатель владеет tail.
// Они читают чужой индекс атомарно, но никогда его не пишут — гонки нет по построению.
type SPSCQueue struct {
    buf  []interface{}
    mask uint64
    // padding разводит head и tail по разным кэш-линиям (64 байта),
    // иначе они делят одну линию и мы получаем false sharing:
    // запись писателя инвалидирует кэш читателя и наоборот.
    _    [56]byte
    head atomic.Uint64 // пишет только producer
    _    [56]byte
    tail atomic.Uint64 // пишет только consumer
    _    [56]byte
}

func (q *SPSCQueue) Push(v interface{}) bool {
    h := q.head.Load()
    t := q.tail.Load() // Acquire: гарантирует, что мы видим освобождённые слоты
    if h-t >= uint64(len(q.buf)) {
        return false // буфер полон — решение о backpressure принимает вызывающий
    }
    q.buf[h&q.mask] = v
    q.head.Store(h + 1) // Release: запись в слот обязана стать видимой раньше индекса
    return true
}

func (q *SPSCQueue) Pop() (interface{}, bool) {
    t := q.tail.Load()
    h := q.head.Load()
    if t == h {
        return nil, false // пусто
    }
    v := q.buf[t&q.mask]
    q.buf[t&q.mask] = nil // помогаем GC
    q.tail.Store(t + 1)
    return v, true
}

Две детали, которые отличают работающий код от почти работающего:

False sharing. Если head и tail лежат в одной 64-байтной кэш-линии, каждая запись писателя выбивает линию из кэша читателя. Пропускная способность падает в разы. Padding между полями — не суеверие, а измеримая оптимизация; в Java для этого есть @Contended, в C++ — std::hardware_destructive_interference_size.

Порядок памяти. Запись данных в слот должна стать видимой другому потоку раньше, чем инкремент индекса. Иначе читатель увидит новый индекс и прочитает мусор. За это отвечают release/acquire-семантика (в Go атомики из sync/atomic дают sequential consistency, в C++ порядок задают явно). Это тема статьи Персистентные и конкурентные структуры.

5.2 Work-stealing дек: почему дек, а не очередь

В планировщиках задач (Go runtime, Java ForkJoinPool, Rust rayon, .NET TPL) у каждого воркера собственный дек задач. Владелец работает с одним концом, а «воры» забирают с другого. Это гениально просто: пока дек не почти пуст, владелец и вор физически не конфликтуют.

Дек здесь обязателен именно потому, что нужны разные дисциплины с разных концов: LIFO для владельца даёт локальность кэша и ограничивает потребление памяти (глубина рекурсии вместо ширины), FIFO для вора даёт крупные куски работы и минимизирует число краж. Каноническая реализация — алгоритм Chase–Lev («Dynamic Circular Work-Stealing Deque», PDF), именно он и лежит в основе crossbeam-deque в Rust.

5.3 Многопоточные очереди в продакшене

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

6. Сводка сложности

* — амортизированно, отдельная операция может быть Θ(n) при реаллокации. ** — амортизированно; худший случай одной операции Θ(n).

Ни одна из структур не поддерживает эффективный поиск — это не их работа. Если вам нужно проверять «есть ли элемент в очереди», держите рядом хеш-множество (Хеш-таблицы) и синхронизируйте его с очередью. Если нужен «минимальный элемент», а не «первый» — вам нужна куча, а не очередь.

7. Типичные ошибки

1. list.pop(0) в цикле. Θ(n²) вместо Θ(n). Диагностируется мгновенно профилировщиком, но доживает до прода, потому что на маленьких данных незаметна.
2. Неограниченная очередь как «решение» проблемы нагрузки. Unbounded queue не устраняет перегрузку, она превращает её из отказа в OOM и в рост латентности до бесконечности. Очередь должна быть ограниченной, а переполнение — явным архитектурным решением.
3. Забытое обнуление слота. В языках с GC оставленная ссылка держит объект живым. Утечка выглядит как «память растёт, хотя очередь пустая».
4. head == tail как признак пустоты без учёта полноты. Классический баг кольцевого буфера: при заполнении до конца буфер «внезапно становится пустым» и данные молча теряются.
5. Модуль вместо маски в горячем цикле. Работает, но медленнее; и % от отрицательного числа в C/C++/Java даёт отрицательный результат — источник редких, но злых багов при декременте индекса.
6. LinkedList в роли очереди в Java. Та же асимптотика, но в разы медленнее ArrayDeque из-за аллокаций и промахов кэша.
7. Рекурсия по данным пользователя. Глубоко вложенный JSON от клиента — это удалённое переполнение стека, то есть DoS. Парсеры обязаны либо считать глубину, либо работать на явном стеке.
8. Стек вместо очереди в BFS. Обход остаётся корректным, но перестаёт быть поиском в ширину: найденный путь больше не кратчайший. Ошибка тихая — код «работает», просто даёт неверный ответ.
9. Общий size в многопоточной очереди. Единственная разделяемая переменная-счётчик убивает всю выгоду от разделения head и tail по кэш-линиям.

8. Как это выглядит в проде

Разберём последний узел подробнее, потому что именно там живёт архитектура.

Backpressure (блокировка писателя). Когда очередь полна, писатель ждёт. Это правильный выбор, когда терять данные нельзя и когда замедление источника допустимо. Обратное давление распространяется по цепочке до самого края системы — так устроен Reactive Streams и GenStage в Elixir.

Drop-oldest (перезапись). Кольцевой буфер, который просто затирает старые данные. Так работают буферы видеокадров, метрики, кольцевые логи (dmesg, journald), «чёрные ящики» для дампа последних N событий при падении. Свежие данные ценнее старых.

Drop-newest. Отбрасываем то, что не влезло. Типично для телеметрии и трассировок: лучше потерять часть спанов, чем замедлить обслуживание запроса.

Fail-fast. Немедленная ошибка вызывающему — правильно для синхронных RPC, где долгое ожидание всё равно закончится таймаутом клиента. Лучше ответить 503 за 1 мс, чем 504 через 30 секунд.

Ещё одно наблюдение из практики: длина очереди — лучшая метрика здоровья системы. По закону Литтла L = λ·W средняя длина очереди равна произведению интенсивности потока на среднее время пребывания. Растущая очередь означает, что потребитель не успевает, и это видно раньше, чем вырастет латентность на клиенте. Мониторьте не только «сколько обработали», но и «сколько ждёт».

9. Как выбирать

Короткий алгоритм принятия решения:

1. Нужен порядок «последний пришёл — первый ушёл»? → стек, реализация на динамическом массиве.
2. Нужен справедливый порядок FIFO, однопоточно? → collections.deque / ArrayDeque.
3. Нужны оба конца? → дек, и убедитесь, что действительно нужны оба, а не просто «на всякий случай».
4. Нужна фиксированная ёмкость, предсказуемая латентность и ноль аллокаций? → преаллоцированный ring buffer.
5. Нужен доступ по индексу в середину? → это не очередь, вам нужен массив.
6. Нужен «самый приоритетный», а не «самый первый»? → это куча, а не очередь.
7. Несколько потоков? → сначала докажите модель (SPSC/MPSC/MPMC), потом выбирайте реализацию. Не пишите свою lock-free очередь, если можете взять готовую.

Общая карта структур и критерии выбора собраны в обзоре трека.

10. Мини-итог

• Стек, очередь и дек — это дисциплины доступа, а не способы хранения. Один контракт, много реализаций.
• Ограничение интерфейса покупает вам O(1), локальность кэша и возможность рассуждать о корректности.
• Массив бьёт связный список почти всегда: та же асимптотика, лучше константа, лучше кэш.
• Кольцевой буфер — рабочая лошадка систем: степень двойки, маска вместо модуля, обнуление слотов, явная политика на переполнении.
• Монотонный стек и скользящий максимум на деке — два приёма, превращающие O(n²) в O(n) за счёт амортизационного аргумента «каждый элемент входит и выходит один раз».
• В многопоточном мире выигрывает тот, кто сузил модель: SPSC на порядок быстрее MPMC.
• Дек в work-stealing — это не «удобство», а необходимость: два конца дают две разные дисциплины и разводят владельца с вором.
• Главное продакшн-решение вокруг очереди — не её реализация, а политика переполнения.

Источники

• Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 4-е изд., гл. 10 «Elementary Data Structures» и гл. 16 «Amortized Analysis» — mitpress.mit.edu
• Sedgewick, Wayne. Algorithms, 4-е изд., раздел 1.3 «Bags, Queues, and Stacks» — algs4.cs.princeton.edu/13stacks
• Okasaki. Purely Functional Data Structures — real-time queues и амортизация в иммутабельном мире: cambridge.org
• Chase, Lev. Dynamic Circular Work-Stealing Deque, SPAA 2005 — PDF
• Michael, Scott. Simple, Fast, and Practical Non-Blocking and Blocking Concurrent Queue Algorithms — cs.rochester.edu
• LMAX Disruptor — технический доклад о ring buffer без аллокаций: lmax-exchange.github.io/disruptor и разбор Мартина Фаулера martinfowler.com/articles/lmax.html
• Документация collections.deque (CPython) — docs.python.org
• Документация java.util.ArrayDeque — docs.oracle.com
• Vyukov. Заметки об очередях для многопоточности — 1024cores.net

Что дальше

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

Читайте: Хеш-таблицы: хеш-функции, коллизии, открытая адресация