Двусторонняя очередь

Двусторонняя очередь (англ. deque, от double-ended queue) — это абстрактный тип данных (АТД) в информатике, представляющий собой последовательность элементов, в которой добавление и удаление элементов может выполняться как с начала, так и с конца очереди. В отличие от обычной очереди (FIFO — «первым пришёл — первым вышел») и стека (LIFO — «последним пришёл — первым вышел»), дек объединяет их возможности, обеспечивая операции вставки и извлечения с обеих сторон. Дек является обобщением этих структур и часто реализуется с помощью динамического массива, двусвязного списка или кольцевого буфера. В стандартной библиотеке шаблонов (STL) языка C++ дек представлен классом std::deque, а в Python — типом collections.deque.

История

Понятие двусторонней очереди было формализовано в 1970-х годах в рамках развития теории структур данных. Термин «deque» ввёл американский математик и программист Дональд Кнут в своей монографии «Искусство программирования» (том 1, 1968 год), где он описал её как «очередь с двумя концами». Однако практическое применение дек получил позже, с развитием языков программирования высокого уровня и потребностью в эффективных структурах для задач, требующих быстрого доступа к обоим концам последовательности.

В 1980-х годах дек стал стандартной частью библиотек языков C++ (STL) и Java (класс ArrayDeque). В 1990-х годах его включили в стандартную библиотеку Python (модуль collections). В России и странах бывшего СССР дек активно изучался в курсах алгоритмов и структур данных, начиная с 1980-х годов, как часть фундаментальной подготовки программистов.

Классификация

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

По ограничению операций

• Полный дек — поддерживает все четыре основные операции: вставка и удаление с обоих концов.
• Ограниченный дек — допускает только часть операций. Например, «входной дек» (input-restricted deque) позволяет вставку только с одного конца, а удаление — с обоих; «выходной дек» (output-restricted deque) — наоборот.

По способу реализации

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

По типу данных

• Гомогенный дек — все элементы одного типа (например, числа или строки).
• Гетерогенный дек — элементы могут быть разных типов (поддерживается в языках с динамической типизацией, таких как Python).

Устройство и характеристики

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

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

Внутреннее устройство

В реализации на основе кольцевого буфера дек хранит элементы в массиве, логически замкнутом в кольцо. Указатели на начало и конец массива позволяют выполнять вставку и удаление с обоих концов без сдвига всех элементов. При переполнении буфера (например, если все ячейки заняты) массив увеличивается в два раза, а элементы копируются в новую область памяти.

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

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

Применение

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

Алгоритмы и структуры данных

• Реализация стеков и очередей — дек может эмулировать обе структуры, ограничив операции только одним концом.
• Алгоритм поиска в ширину (BFS) — в некоторых модификациях (например, 0-1 BFS) дек используется для поддержки очереди с приоритетами, где веса рёбер равны 0 или 1.
• Алгоритм скользящего окна — для нахождения минимума или максимума в подмассивах фиксированного размера (например, задача «Максимум в скользящем окне»).
• Обработка палиндромов — проверка симметричности строки путём сравнения элементов с обоих концов.

Системное программирование

• Буферизация ввода-вывода — дек используется для хранения данных, поступающих с разных скоростей (например, в сетевых протоколах).
• Планировщики задач — в операционных системах дек может применяться для управления очередями процессов с разными приоритетами.

Веб-разработка и базы данных

• Кэширование — дек реализует политику LRU (Least Recently Used), где недавно использованные данные перемещаются в начало, а старые удаляются с конца.
• Обработка запросов — в веб-серверах дек используется для хранения входящих запросов, которые могут быть обработаны в порядке поступления или с приоритетом.

Математика и вычислительная геометрия

• Построение выпуклой оболочки — алгоритм Грэхема использует дек для хранения точек, которые могут быть добавлены или удалены с обоих концов.
• Численные методы — дек применяется в методах конечных разностей для хранения граничных условий.

Примеры реализации

На языке Python (модуль collections)

```python from collections import deque

Создание дека

d = deque([1, 2, 3])

Добавление элементов

d.append(4) # [1, 2, 3, 4] d.appendleft(0) # [0, 1, 2, 3, 4]

Удаление элементов

d.pop() # [0, 1, 2, 3] d.popleft() # [1, 2, 3]

Доступ к элементам

print(d[0]) # 1 print(d[-1]) # 3 ```

На языке C++ (STL)

```cpp

include <deque>

include <iostream>

int main() { std::deque<int> d = {1, 2, 3};

d.push_front(0); // [0, 1, 2, 3] d.push_back(4); // [0, 1, 2, 3, 4]

d.pop_front(); // [1, 2, 3, 4] d.pop_back(); // [1, 2, 3]

std::cout << d.front() << " " << d.back(); // 1 3 return 0; } ```

На языке Java (класс ArrayDeque)

```java import java.util.ArrayDeque; import java.util.Deque;

public class Main { public static void main(String[] args) { Deque<Integer> d = new ArrayDeque<>(); d.addFirst(1); // [1] d.addLast(2); // [1, 2] d.addFirst(0); // [0, 1, 2]

d.removeFirst(); // [1, 2] d.removeLast(); // [1] } } ```

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

• В стандартной библиотеке C++ std::deque реализован как последовательность блоков фиксированного размера (обычно по 512 байт), что обеспечивает эффективный доступ по индексу и вставку с обоих концов.
• В Python collections.deque оптимизирован для быстрой вставки и удаления с обоих концов, но доступ к произвольному элементу по индексу занимает O(n) в худшем случае.
• В языке Rust дек реализован как VecDeque в стандартной библиотеке, используя кольцевой буфер.
• В некоторых функциональных языках (например, Haskell) дек реализуется с помощью двух списков (стеков), что позволяет сохранять неизменяемость данных.

Критика

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

Источники

1. Кнут Д. Э. Искусство программирования. Том 1. Основные алгоритмы. — 3-е изд. — М.: Вильямс, 2006.
2. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ. — 3-е изд. — М.: Вильямс, 2013.
3. Седжвик Р. Фундаментальные алгоритмы на C++. — М.: ДиаСофт, 2002.
4. Документация Python 3.12: модуль collections.deque. — Python Software Foundation, 2023.
5. Стандарт ISO/IEC 14882:2020 (C++20). — Международная организация по стандартизации, 2020.
6. Java Platform, Standard Edition 17: API Specification — класс java.util.ArrayDeque. — Oracle Corporation, 2021.