Дек или двусторонняя очередь — структура данных, в которой элементы
можно добавлять и удалять с обоих концов.
Название происходит от:
Deque = Double Ended Queue
У дека есть два конца:
front -> начало
back -> конец
Пример:
deque = [7, 3, 9, 1]
front back
7 3 9 1
В дек можно добавить элемент слева:
pushFront(5)
deque = [5, 7, 3, 9, 1]
И справа:
pushBack(4)
deque = [5, 7, 3, 9, 1, 4]
Удаление тоже возможно с двух сторон:
popFront() -> 5
popBack() -> 4
Термины
deque -> двусторонняя очередь
front -> первый элемент
back -> последний элемент
size -> количество элементов
pushFront(x) -> добавить x в начало
pushBack(x) -> добавить x в конец
popFront() -> удалить и вернуть первый элемент
popBack() -> удалить и вернуть последний элемент
peekFront() -> посмотреть первый элемент без удаления
peekBack() -> посмотреть последний элемент без удаления
isEmpty() -> проверить, пуст ли дек
Дек задаётся тремя вещами:
1. набор элементов
2. порядок элементов
3. два доступных конца: front и back
Структура дека
Структура отвечает на вопрос:
Что внутри и как расположено?
У дека есть:
элементы
начало
конец
порядок
размер
Дек можно представить как горизонтальную последовательность с доступом с двух
сторон:
front back
↓ ↓
[7] <-> [3] <-> [9] <-> [1]
Основное отличие от стека:
stack -> доступ только к верхушке
deque -> доступ к началу и концу
Основное отличие от обычной очереди:
queue -> добавление с одного конца, удаление с другого
deque -> добавление и удаление с обоих концов
Свойства
Короткая карта свойств дека как структуры:
два конца -> front и back
упорядоченность -> порядок элементов имеет значение
двусторонний доступ -> операции доступны с начала и с конца
размер -> количество элементов в деке
пустота -> дек может не содержать элементов
ограниченный доступ -> произвольный доступ по индексу не является базовой операцией
Конкретный дек содержит конечное число элементов:
size = n
пустой дек = size == 0
непустой дек = size > 0
Для непустого дека существуют оба конца:
front(deque)
back(deque)
Если в деке один элемент, начало и конец указывают на один и тот же элемент:
deque = [7]
front = 7
back = 7
Важно отделять свойства дека от характеристик конкретного дека:
свойство: у дека есть начало
характеристика: первый элемент этого дека = 7
свойство: у дека есть размер
характеристика: размер этого дека = 4
Два конца
Дек предоставляет доступ к двум крайним позициям:
front(deque)
back(deque)
Для дека:
[7, 3, 9, 1]
получаем:
front = 7
back = 1
Порядок
Порядок элементов является частью дека.
[7, 3, 9, 1] != [1, 9, 3, 7]
Операции с разных концов по-разному меняют порядок:
pushFront(5) -> [5, 7, 3, 9, 1]
pushBack(5) -> [7, 3, 9, 1, 5]
Пустота
Дек может быть пустым:
deque = []
size = 0
Для пустого дека нельзя корректно выполнить:
popFront()
popBack()
peekFront()
peekBack()
если реализация явно не задаёт специальное поведение для этих случаев.
Базовые операции
Создание
deque = []
Обычно:
O(1)
Push Front
Добавить элемент в начало:
pushFront(deque, x)
Пример:
deque = [7, 3, 9]
pushFront(1)
deque = [1, 7, 3, 9]
Обычно:
O(1)
Push Back
Добавить элемент в конец:
pushBack(deque, x)
Пример:
deque = [7, 3, 9]
pushBack(1)
deque = [7, 3, 9, 1]
Обычно:
O(1)
Pop Front
Удалить и вернуть первый элемент:
popFront(deque)
Пример:
deque = [7, 3, 9, 1]
popFront() -> 7
deque = [3, 9, 1]
Условие:
size(deque) > 0
Обычно:
O(1)
Pop Back
Удалить и вернуть последний элемент:
popBack(deque)
Пример:
deque = [7, 3, 9, 1]
popBack() -> 1
deque = [7, 3, 9]
Условие:
size(deque) > 0
Обычно:
O(1)
Peek Front / Peek Back
Посмотреть крайний элемент без удаления:
peekFront(deque)
peekBack(deque)
Пример:
deque = [7, 3, 9, 1]
peekFront() -> 7
peekBack() -> 1
deque = [7, 3, 9, 1]
Сложность:
O(1)
Is Empty
Проверить, пуст ли дек:
isEmpty(deque)
Пример:
[] -> true
[7, 3, 9] -> false
Сложность:
O(1)
Size
Получить количество элементов:
size(deque)
Обычно:
O(1)
если размер хранится отдельно.
Проход по деку
Если нужно обработать все элементы через операции дека, его можно постепенно
разбирать с одной стороны:
while not isEmpty(deque):
x = popFront(deque)
use x
или с другой:
while not isEmpty(deque):
x = popBack(deque)
use x
Сложность:
O(n)
Важно: такой проход изменяет дек, потому что popFront() и popBack() удаляют
элементы.
Таблица сложностей
| Операция | Сложность |
|---|---|
| создание | O(1) |
pushFront(x) |
O(1) |
pushBack(x) |
O(1) |
popFront() |
O(1) |
popBack() |
O(1) |
peekFront() |
O(1) |
peekBack() |
O(1) |
isEmpty() |
O(1) |
size() |
O(1) |
| проход с удалением всех элементов | O(n) |
| поиск произвольного значения | O(n) |
Реализация
Дек — это абстрактная структура данных. Его можно реализовать разными способами.
Через двусвязный список
Каждый узел хранит ссылки на следующий и предыдущий узел:
front back
↓ ↓
[7] <-> [3] <-> [9] <-> [1]
Тогда:
pushFront(x) -> добавить новый узел перед front
pushBack(x) -> добавить новый узел после back
popFront() -> удалить узел front
popBack() -> удалить узел back
Все основные операции с концами работают за O(1), если есть ссылки на front
и back.
Через кольцевой буфер
Дек можно хранить в массиве фиксированной ёмкости с двумя указателями:
capacity = 8
front = 2
back = 5
index: 0 1 2 3 4 5 6 7
value: _ _ 7 3 9 1 _ _
При достижении конца массива индекс переходит в начало:
next(i) = (i + 1) mod capacity
prev(i) = (i - 1 + capacity) mod capacity
Такой вариант часто используется в стандартных библиотеках.
Если буфер заполнен, реализация может создать новый буфер большей ёмкости и
перенести элементы. Тогда отдельное расширение стоит O(n), но операции
добавления остаются амортизированно быстрыми.
Дек, стек и очередь
Дек может работать как стек:
pushBack(x)
popBack()
или:
pushFront(x)
popFront()
Дек может работать как очередь:
pushBack(x)
popFront()
или в обратном направлении:
pushFront(x)
popBack()
Поэтому дек часто используют как универсальную структуру для задач, где нужны
быстрые операции с обоих концов.
Python
В Python дек представлен типом:
collections.deque
Основные операции:
append(x) -> добавить справа
appendleft(x) -> добавить слева
pop() -> удалить справа
popleft() -> удалить слева
Пример:
from collections import deque
d = deque()
d.append(7)
d.append(3)
d.appendleft(1)
print(d) # deque([1, 7, 3])
print(d.pop()) # 3
print(d.popleft()) # 1
Типичные применения
очередь задач
скользящее окно
монотонная очередь
BFS
хранение последних n событий
палиндромы
симуляции с обработкой с двух концов
Формальная схема
Deque = {
elements: e1, e2, ..., en,
front: e1,
back: en,
size: n
}
Операции дека изменяют или используют одну из четырёх сущностей:
начало
конец
размер
порядок
Примеры:
pushFront(x) -> меняет начало и увеличивает размер
pushBack(x) -> меняет конец и увеличивает размер
popFront() -> возвращает начало и уменьшает размер
popBack() -> возвращает конец и уменьшает размер
peekFront() -> читает начало без изменения дека
peekBack() -> читает конец без изменения дека
Минимальная формулировка:
дек = структура с быстрым доступом к обоим концам
