Персистентный дек

Эта статья находится в разработке!

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

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

Дек

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

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

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

Древовидная структура дека

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

Deque<T>(first, child, last)

 Deque<T> {
   T first, last;
   Deque<T> child;
 };

Так как наша структура данных персистентная, то операция [math] D.push\_front(x) [/math] возвращает новый дек [math] D' [/math], c элементом [math] x [/math] в начале.

 push_front(x)
   if first == [math] \varnothing [/math]
     return Deque<T>(x, child, last)
   else
     return Deque<T>([math] \varnothing [/math], c.push_front(Pair<x, first>), last)

Метод [math] D.pop\_front() [/math] возвращает пару [math] \left \langle e, ~D' \right \rangle [/math] из первого элемента и нового дека, полученного из старого изъятием этого элемента.

 pop_front()
   if first [math] \neq ~\varnothing[/math]
     return [math] \mathcal{h} [/math]first, Deque<T>([math] \varnothing [/math], child, last)[math] \mathcal{i} [/math]
   else if child == [math] \varnothing[/math]
     return [math] \mathcal{h} [/math]last, Deque<T>([math] \varnothing ,~\varnothing ,~\varnothing [/math])[math] \mathcal{i} [/math]
   else
     temp, newDeque [math] \leftarrow [/math] child.pop_front()
     if temp == [math] \varnothing [/math]
       return [math] \mathcal{h} [/math]last, Deque<T>([math] \varnothing ,~\varnothing ,~\varnothing [/math])[math] \mathcal{i} [/math]
     else
       return [math] \mathcal{h} [/math]temp.first, Deque<T>(temp.child, newDeque, last)[math] \mathcal{i} [/math]

Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за [math] O(\log ~n) [/math]

См. также

• Очередь
• Стек
• Персистентный стек

Ссылки

• Purely Functional Deques with Catenation by Robert E. Tarjan