Как реализовать дек: пошаговое решение

Дано: дек на кольцевом массиве ёмкостью $N = 8$, в начале пустой, $head = 0$, $size = 0$. Семь операций подряд: push_back 10, push_back 20, push_back 30, push_front 40, push_front 50, pop_back, pop_front. Найти: индекс головы, индекс хвоста, размер и порядок элементов после последнего шага.

Метод: хранить только два числа, индекс головы $head$ и количество элементов $size$, а индекс хвоста считать формулой $(head + size - 1) \bmod N$. Ответ: $head = 7$, $tail = 1$, $size = 3$, дек от головы к хвосту равен 40, 10, 20; при этом pop_back вернул 30, а pop_front вернул 50. Калькулятор сверху прогоняет эту же последовательность по шагам и показывает массив после каждого, а ниже те же семь шагов расписаны руками.

Решение по шагам

Дано. Массив $a$ из восьми ячеек с индексами от 0 до 7, счётчики $head = 0$ и $size = 0$. Правила четырёх операций записываем один раз и дальше только подставляем числа:

$$\begin{aligned} \text{push\_back}(x): &\quad a[(head + size) \bmod N] = x,\ size \mathrel{+}= 1;\\ \text{push\_front}(x): &\quad head = (head - 1 + N) \bmod N,\ a[head] = x,\ size \mathrel{+}= 1;\\ \text{pop\_front}(): &\quad x = a[head],\ head = (head + 1) \bmod N,\ size \mathrel{-}= 1;\\ \text{pop\_back}(): &\quad size \mathrel{-}= 1,\ x = a[(head + size) \bmod N]. \end{aligned}$$

Шаги 1-3. Три push_back подряд. Свободное место в хвосте всегда лежит по индексу $(head + size) \bmod N$. Пока голова стоит в нуле, это просто $0$, $1$, $2$: числа 10, 20 и 30 ложатся в три первые ячейки, $size$ доходит до трёх, $head$ не двигается.

Шаг 4. push_front 40 уводит голову через край. Свободной ячейки слева от нуля в массиве нет, поэтому индекс уходит по кругу: $head = (0 - 1 + 8) \bmod 8 = 7$. Значение 40 пишется в последнюю ячейку массива, хотя логически стоит первым. Слагаемое $+N$ здесь обязательно: в большинстве языков остаток от отрицательного числа отрицателен, и без него получился бы индекс $-1$.

Шаг 5. push_front 50. По той же формуле $head = (7 - 1 + 8) \bmod 8 = 6$, значение 50 попадает в ячейку 6, $size = 5$. Теперь дек занимает ячейки 6, 7, 0, 1, 2 и физически разорван на два куска, но логически это единый непрерывный отрезок.

Шаг 6. pop_back снимает элемент с хвоста. Сначала уменьшаем размер: $size = 4$. Затем берём значение по индексу $(head + size) \bmod N = (6 + 4) \bmod 8 = 2$, то есть $a[2] = 30$. Порядок важен: если сначала прочитать, а потом уменьшить, придётся писать $-1$ в формуле и легко ошибиться на единицу.

Шаг 7. pop_front снимает элемент с головы. Читаем $a[6] = 50$, сдвигаем голову вперёд: $head = (6 + 1) \bmod 8 = 7$, размер становится равен трём.

Индекс хвоста в последней строке проверяем формулой: $tail = (head + size - 1) \bmod N = (7 + 3 - 1) \bmod 8 = 9 \bmod 8 = 1$. Обход дека читаем как $a[(head + i) \bmod N]$ при $i$ от 0 до $size - 1$: ячейки 7, 0, 1, то есть 40, 10, 20.

Ответ. $head = 7$, $tail = 1$, $size = 3$, содержимое дека от головы к хвосту: 40, 10, 20. Снятые элементы: 30 с хвоста и 50 с головы.

Формула и откуда она берётся

Дек (deque, double ended queue) отличается от очереди тем, что добавлять и удалять можно с обоих концов. Значит, нужны две точки роста, и обе должны двигаться, не задевая элементы посередине. Сдвигать массив после каждой операции нельзя: это $O(n)$ на шаг. Остаётся один выход: не двигать данные, а двигать индексы, замкнув массив в кольцо.

Замыкание и даёт остаток от деления. Выражение $(i + 1) \bmod N$ после индекса $N - 1$ возвращает 0, а $(i - 1 + N) \bmod N$ после нуля возвращает $N - 1$. Массив превращается в кольцо, где у последней ячейки соседом справа оказывается нулевая. Ровно тот же приём лежит в основе кольцевого буфера, только там движение одностороннее.

Пару полей выбирают одну из двух: либо $head$ и $tail$, либо $head$ и $size$. Второй вариант удобнее. Если хранить два индекса, состояния «пусто» и «полностью занято» выглядят одинаково: $head$ совпадает с $tail$, и отличить их нельзя без дополнительного флага или жертвы одной ячейки. Счётчик $size$ снимает двусмысленность сразу: дек пуст при $size = 0$ и полон при $size = N$, а индекс хвоста всегда восстанавливается формулой.

Две проверки границ пишутся до арифметики. Любой push начинается со сравнения $size = N$: если места нет, массив расширяют или бросают исключение. Любой pop начинается со сравнения $size = 0$: снимать с пустого дека нечего. В нашей задаче ни та, ни другая ветка не сработала, потому что пять элементов в восьми ячейках помещаются свободно.

Дек на двусвязном списке

Второй канонический способ реализации - двусвязный список. Узел хранит значение и два указателя, на предыдущий и на следующий; сама структура держит указатели $head$ и $tail$ на крайние узлы и счётчик длины. Добавление в голову создаёт узел, вешает его перед текущей головой и переставляет $head$; добавление в хвост делает то же самое с другого конца. Удаление сдвигает соответствующий указатель на соседа и обнуляет ссылку назад.

Все четыре операции здесь честно константные, без всяких оговорок: правок указателей ровно три-четыре, независимо от длины. Плюс ёмкость не ограничена заранее, переполнения не бывает в принципе. Минусы платные: на каждый элемент уходит два указателя (16 лишних байт на 64-битной платформе), узлы разбросаны по куче, и обход дека промахивается мимо кэша процессора на каждом шаге.

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

Сложность операций и расширение массива

Все четыре операции дека - push_front, push_back, pop_front, pop_back - стоят $O(1)$: несколько сложений, одно взятие остатка и одна запись в память. Доступ к произвольному элементу по логическому номеру $i$ тоже константный, $a[(head + i) \bmod N]$, но вставка в середину дека не предусмотрена вовсе - это не список.

Исключение одно: push в полный массив. Тогда заводят новый массив вдвое большей ёмкости и переносят элементы от головы к хвосту, выпрямляя кольцо, - голова нового массива снова встаёт в ноль. Одна такая операция стоит $O(n)$, но происходит она всё реже: после $n$ добавлений суммарно скопировано не больше $2n$ элементов, поэтому амортизированная стоимость push остаётся константной. Тот же приём разобран на примере стека в статье про реализацию стека на списке, а как считать такие оценки в общем случае - в разборе сложности алгоритма.

Дек обобщает сразу две структуры. Если пользоваться только парой push_back и pop_back, получается стек с дисциплиной LIFO. Если брать push_back и pop_front - очередь FIFO. Переключи сценарий в калькуляторе сверху: последовательность операций поменяется, а формулы индексов останутся теми же. Отсюда и типовое применение дека: скользящее окно максимума, обход в ширину с приоритетом 0-1, история навигации вперёд и назад.

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

• Забыли $+N$ при сдвиге головы влево. Выражение $(head - 1) \bmod N$ при $head = 0$ даёт $-1$ в C, C++, Java и JavaScript: выход за границу или исключение. Писать нужно $(head - 1 + N) \bmod N$.
• Хранят $head$ и $tail$ без счётчика. Тогда пустой и полный дек неразличимы: в обоих случаях указатели совпадают. Либо добавляйте $size$, либо сознательно жертвуйте одной ячейкой, оставляя её всегда свободной.
• Путают порядок действий в pop_back. Сначала уменьшить $size$, потом читать по $(head + size) \bmod N$. При обратном порядке формула обязана быть $(head + size - 1) \bmod N$, и именно здесь чаще всего теряется единица.
• Считают, что освободившаяся ячейка очистилась. После pop старое значение физически остаётся в массиве. Логически ячейка свободна, но в языках со сборкой мусора ссылку стоит обнулить, иначе объект не освободится.
• Расширяют массив копированием «как лежит». Если дек разорван через край, простое побайтовое копирование в новый массив перепутает порядок. Переносить надо по одному элементу через $(head + i) \bmod N$.
• Берут ёмкость, не равную степени двойки, и оптимизируют остаток битовой маской. Замена $\bmod N$ на $\,\&\,(N-1)$ работает только при $N = 2^k$.

FAQ

Чем дек отличается от очереди и стека? Очередь позволяет добавлять только в хвост и снимать только с головы, стек работает одним концом. Дек снимает это ограничение: доступны все четыре операции, поэтому и стек, и очередь получаются из него частным случаем.

Можно ли реализовать дек на односвязном списке? Частично. Три операции из четырёх выйдут константными, а pop_back потребует найти предпоследний узел, то есть пройти весь список за $O(n)$. Именно поэтому берут двусвязный список или кольцевой массив.

Как обойти дек, не разрушая его? Циклом по $i$ от 0 до $size - 1$ с чтением $a[(head + i) \bmod N]$. Индексы $head$ и $size$ при этом не меняются, так что дек остаётся в прежнем состоянии.

Какую ёмкость брать на старте? Обычно 8 или 16 ячеек: меньше не имеет смысла из-за накладных расходов на сам объект, а больше - просто память впустую, если дек так и останется коротким. Дальше ёмкость удваивается по мере заполнения.

Коротко

1. Дек на массиве хранит два числа: индекс головы $head$ и размер $size$; индекс хвоста считается как $(head + size - 1) \bmod N$.
2. push_back пишет в $(head + size) \bmod N$, push_front сдвигает голову по $(head - 1 + N) \bmod N$ и пишет туда же.
3. pop_front читает $a[head]$ и двигает голову вперёд, pop_back сначала уменьшает $size$, потом читает $(head + size) \bmod N$.
4. В примере после семи операций получилось $head = 7$, $tail = 1$, $size = 3$, дек равен 40, 10, 20; снялись 30 с хвоста и 50 с головы.
5. Все операции $O(1)$; альтернатива - двусвязный список, где константность честная, но на каждый элемент уходит два указателя.