3622
правки
Изменения
Нет описания правки
'''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т. е. их можно удалять и добавлять как в начало, так и в конец дека.
}}
[[Файл:Deque.png|thumb|325px250px|Дек]]
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать можно с обоих. В отличие от обычных стека и очереди, ''deque'' и ''steque'' используются в задачах намного реже.
== Эффективная реализация ==
Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.
[[Файл:Tree_deque.png|thumb|Древовидная структура дека]]
Персистентный дек можно визуально представить как дерево, где каждый узел хранит пару первый элемент и последний, а также ''ребёнка'' - ссылку на следующий дек. Только с каждым уровнем вложенности левый и правый элемент представляют собой массив размера в два раза больше, чем на предыдущем уровне.
<code>
