Дек. Сравнительное описание. Примеры задач: очередь с двумя открытыми концами
Определение и операции
Дек - динамическая структура данных, в которой элементы можно добавлять и удалять как с левого конца (начала), так и с правого (конца). Базовый набор операций:
- PushLeft / PushRight - включение элемента слева или справа;
- PopLeft / PopRight - исключение слева или справа;
- TopLeft / TopRight - чтение крайних элементов без удаления;
- определение размера и очистка.
Дек как обобщение стека и очереди
Дек - функциональное объединение стека (LIFO) и очереди (FIFO):
- запретите добавление и удаление на одном из концов - получится стек;
- разрешите добавление только с одной стороны, а удаление только с другой - получится очередь.
Физическое представление
Оба знакомых способа переносятся на дек:
- Статически - кольцевой буфер, как у очереди, только теперь по кольцу умеют двигаться оба конца.
- Динамически - двусвязный список:
каждый узел хранит указатели и на следующий (
next), и на предыдущий (prev) узел, а сам дек - указателиleftиrightна крайние узлы. Второй указатель в узле необходим: чтобы удалить крайний правый элемент за O(1), нужно мгновенно узнать его соседа слева.
/* Узел двусвязного списка */
typedef struct DequeNode {
int data;
struct DequeNode* next; /* сосед справа */
struct DequeNode* prev; /* сосед слева */
} DequeNode;
/* Дек: указатели на оба конца */
typedef struct Deque {
DequeNode* left;
DequeNode* right;
int size;
} Deque;Дек. Сравнительное описание. Примеры задач: где дек незаменим
Задачи "чистого дека" встречаются реже, чем задачи на стек или очередь. Классический пример - задача о птицах на проводе (Russian Code Cup 2012): птицы бегут по проводу навстречу друг другу, при столкновении разворачиваются, а добежав до края - улетают.
Ключевое наблюдение: птицы не обгоняют друг друга, поэтому их порядок на проводе не меняется, а покинуть провод может только крайняя левая или крайняя правая птица. Значит, координаты птиц достаточно хранить в деке: вылет птицы - это PopLeft или PopRight, O(1) на событие.
Общий признак задач на дек: система, где выбывают только крайние элементы, а внутренний порядок сохраняется. Пара таких задач ждет вас на странице задач темы - палиндром и реверс дека.
collections.deque: append / appendleft,
pop / popleft, все за O(1). Это тот самый инструмент,
который рекомендован вместо списка везде, где нужна работа с началом
последовательности.
Коротко: главное
- Дек - двусторонняя очередь: вставка, удаление и чтение с обоих концов за O(1).
- Обобщает стек и очередь: ограничение операций на концах дает любую из них.
- Статическое представление - кольцевой буфер с двумя индексами.
- Динамическое - двусвязный список (next + prev, указатели left и right).
- Область применения: выбывают только крайние элементы, порядок внутри сохраняется.
Проверьте себя
Как из дека получить стек?