Дэк (deque, double-ended queue) — универсальная структура данных, которая представляет собой последовательность элементов, у которой есть два конца. Причём добавление и удаление элементов может происходить как в начало, так и в конец структуры.
Структура дэк обладает следующими особенностями:
- Вставка элемента возможна как в начало, так и в конец.
- Удаление элемента так же возможно как в начале, так и в конце.
- Доступ к первому и последнему элементу производится за константное время O(1).
- Доступ к элементам в середине дэка осуществляется за линейное время O(n), так как элементы хранятся последовательно.
В целом, дэк представляет собой смесь стека и очереди.
Структура дэк может реализовываться различными способами, например, с использованием двух стэков или двусвязного списка.
