3622
правки
Изменения
Нет описания правки
'''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т.е. их можно удалять и добавлять как в начало, так и в конец дека.
[[Файл:Deque.png|thumb|220px|Дек]]
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать {{---}} с обоих.
== Эффективная реализация ==
[[Файл:Tree_deque.png|thumb|220px|right|Древовидная структура дека]]
Персистентный дек можно визуально представить как дерево, где каждый узел хранит пару - левый элемент и правый, а также ''ребёнка'' - ссылку на следующий дек. Только с каждым уровнем вложенности левый и правый элемент хранят в два раза больше объектов, чем на предыдущем уровне.
Тип <tex>Pair</tex> хранит пару элементов <tex>first</tex> и <tex>last</tex> типов <tex>T_1T</tex> и <tex>T_2</tex> соответственно.
<code style = "display: inline-block;">
Pair<<tex>T_1, ~T_2T</tex>> { <tex>T_1 T ~first;</tex> <tex>T_2 T ~last;</tex>
};
</code>
Сам дек можно инициализировать напрямую, вызвав конструктор <tex>Deque(left, ~child, ~right)</tex>, или через шаблоны <tex>Deque<Pair<T_1, ~T_2T>></tex>, тогда произойдёт следующее:
<code style = "display: inline-block;">
Deque<Pair<<tex> T_1, ~T_2 T</tex>>> { <tex>T_1T</tex> left; <tex>T_2T</tex> right; Deque<Pair<Pair<<tex> T_1, ~T_2 T</tex>>, Pair<<tex> T_1, ~T_2 </tex>>> child;
};
</code>
else
// иначе объединим его с новым элементов и попытаемся добавить в дек на следующем уровне
return Deque(<tex> \varnothing </tex>, child.push_front(Pair<(x, left>)), right)
</code>
// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует,
// то вернём пару из правого ребёнка и абсолютно пустого дека
return <tex> \mathcal{h} </tex>right, Deque(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> emptyset \mathcal{i} </tex>
else
/*
* поэтому возвращаем right текущего дека и пустой дек
*/
return <tex> \mathcal{h} </tex>right, Deque(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> emptyset \mathcal{i} </tex>
else
/*
* если всё же temp не пуст, то надо вернуть первый элементы элемент пары temp;
* в качестве left нового дека надо поставить temp.last (на уровне ниже temp хранил
* в два раза больше элементов, поэтому на текущем уровне temp.last будет соответствовать
