Dequeue

Dequeue (дек, от англ. double-ended queue — очередь с двумя концами) — это абстрактный тип данных (АТД), представляющий собой последовательность элементов, в которой добавление и удаление элементов возможно как с начала, так и с конца структуры. В отличие от классической очереди (FIFO — first in, first out) и стека (LIFO — last in, first out), дек сочетает свойства обеих структур, позволяя выполнять операции вставки и извлечения с обеих сторон. Дек является обобщением очереди и стека, и его реализация может быть основана на массиве с кольцевым буфером или на двусвязном списке.

Основные операции

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

• pushFront (или addFirst) — вставка элемента в начало дека.
• pushBack (или addLast) — вставка элемента в конец дека.
• popFront (или removeFirst) — удаление и возврат элемента из начала дека.
• popBack (или removeLast) — удаление и возврат элемента из конца дека.

Дополнительно часто реализуются операции просмотра крайних элементов без удаления (peekFront, peekBack), проверки на пустоту (isEmpty) и получения размера (size).

Виды деков

Деки классифицируются по ограничениям на операции:

• Ограниченный входной дек (input-restricted deque) — допускает вставку только с одного конца, но удаление с обоих.
• Ограниченный выходной дек (output-restricted deque) — допускает удаление только с одного конца, но вставку с обоих.
• Двусторонний дек (double-ended deque) — полный дек, поддерживающий все четыре операции без ограничений.

В контексте программирования также выделяют циклический дек (circular deque), реализованный на кольцевом буфере, который позволяет эффективно использовать память, и стек-дек (stack-deque), где операции pushFront и popFront имитируют стек, а pushBack и popBack — очередь.

История

Понятие дека было введено в 1970-х годах в рамках развития теории абстрактных типов данных. Одним из первых систематических описаний дека стала работа Дональда Кнута в его фундаментальном труде «Искусство программирования» (том 1, 1968 год), где он рассматривал дек как обобщение очереди и стека. В 1979 году в языке программирования Ada была введена встроенная поддержка дека через пакет Ada.Containers.Doubly_Linked_Lists, что способствовало популяризации структуры в промышленной разработке. В 1990-х годах с развитием стандартной библиотеки C++ (STL) дек был включён в контейнер std::deque, который стал одним из ключевых компонентов языка. В 2010-х годах дек появился в стандартных библиотеках языков Python (модуль collections.deque), Java (класс ArrayDeque) и C# (класс LinkedList).

Реализация

На основе массива с кольцевым буфером

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

На основе двусвязного списка

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

Пример на языке Python

В стандартной библиотеке Python дек реализован в модуле collections как класс deque. Он основан на кольцевом буфере и поддерживает все основные операции:

```python from collections import deque

d = deque() d.append(1) # pushBack d.appendleft(2) # pushFront d.pop() # popBack d.popleft() # popFront ```

Пример на языке C++

В стандартной библиотеке C++ (STL) дек реализован как std::deque. Внутренне он использует блоки памяти (chunks), что обеспечивает быстрый доступ по индексу и эффективные операции вставки/удаления с концов:

```cpp

include <deque>

std::deque<int> d; d.push_back(1); d.push_front(2); d.pop_back(); d.pop_front(); ```

Применение

Деки находят широкое применение в различных областях компьютерных наук и программирования:

• Алгоритмы обработки последовательностей — например, в алгоритме скользящего окна (sliding window) для поиска максимума или минимума в подмассивах за O(n). Дек используется для хранения индексов элементов, потенциально являющихся экстремумами.
• Реализация очередей и стеков — дек может служить универсальной основой для построения как очереди (используя только pushBack и popFront), так и стека (используя только pushFront и popFront).
• Планировщики задач — в операционных системах дек используется для управления очередями процессов с приоритетами, где задачи могут добавляться как в начало (высокий приоритет), так и в конец (низкий приоритет).
• Обработка текста — в редакторах текста дек применяется для реализации операций отмены (undo) и повтора (redo), где последние изменения хранятся в начале дека, а более старые — в конце.
• Графические интерфейсы — в системах управления событиями (event-driven programming) дек используется для хранения очереди сообщений, где сообщения с высоким приоритетом обрабатываются раньше.
• Сетевые протоколы — в буферизации пакетов данных, где пакеты могут быть обработаны в порядке, отличном от FIFO, например, в алгоритмах управления перегрузкой (RED, CoDel).

Сравнение с другими структурами данных

Интересные факты

• В языке Python модуль collections.deque оптимизирован для быстрых операций с обоих концов и используется в реализации внутренних механизмов, таких как collections.OrderedDict и asyncio.Queue.
• В C++ std::deque не гарантирует непрерывность памяти, что отличает его от std::vector, но позволяет избежать перераспределения при вставке в середину.
• В некоторых реализациях (например, в Java ArrayDeque) дек может быть использован как стек, заменяя Stack, который считается устаревшим из-за синхронизации.
• Дек является основой для алгоритма «поиска в ширину» (BFS) на графах, если требуется обход с возможностью добавления вершин как в начало, так и в конец очереди (например, в алгоритме 0-1 BFS).

Источники

• Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2006. — 720 с.
• Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013. — 1328 с.
• Седжвик Р. Фундаментальные алгоритмы на C++. Анализ/Структуры данных/Сортировка/Поиск. — М.: ДиаСофт, 2002. — 688 с.
• Документация Python: модуль collections — deque objects. — Python Software Foundation, 2023.
• Стандарт C++ ISO/IEC 14882:2020 — раздел 23.3.3 (deque).