Изменения

{{Определение

|definition =

'''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т. е. их можно удалять и добавлять как в начало, так и в конец дека.

}}

Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать можно с обоих.

== Эффективная реализация ==

Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.

Персистентный дек можно визуально представить как дерево, где каждый узел хранит пару - левый элемент и правый, а также ''ребёнка'' - ссылку на следующий дек. Только с каждым уровнем вложенности левый и правый элемент хранят в два раза больше объектов, чем на предыдущем уровне.

/*

* если всё же temp не пуст, то надо вернуть первый элементы пары temp,

* нового дека, а right текущего, right'ом нового

*/