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