3622
правки
Изменения
Нет описания правки
== Эффективная реализация ==
Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.
<code>
Deque<T>(first, child, last)
Deque<T> {
T first, last;
Deque<T> child;
};
</code>
Так как наша структура данных персистентная, то операция <tex> D.push\_front(x) </tex> возвращает новый дек <tex> D' </tex>, c элементом <tex> x </tex> в начале.
<code>
push_front(x)
if first == <tex> \varnothing </tex>
return Deque<T>(x, child, last)
else
return Deque<T>(<tex> \varnothing </tex>, c.push_front(x, first), last)
</code>
Метод <tex> D.pop\_front() </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
<code>
pop_front()
if first <tex> \neq ~\varnothing</tex>
return <tex> \mathcal{h} </tex>first, Deque<T>(<tex> \varnothing </tex>, child, last)<tex> \mathcal{i} </tex>
else if child == <tex> \varnothing</tex>
return <tex> \mathcal{h} </tex>last, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>
else
temp, newDeque <tex> \leftarrow </tex> child.pop_front()
if temp == <tex> \varnothing </tex>
return <tex> \mathcal{h} </tex>last, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>
else
return <tex> \mathcal{h} </tex>temp.first, Deque<T>(temp.child, newDeque, last)<tex> \mathcal{i} </tex>
</code>
Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> O(\log ~n) </tex>
== См. также ==
