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

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

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

Дек

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

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

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

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

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

Тип [math]Pair[/math] хранит пару элементов [math]first[/math] и [math]last[/math] типов [math]T_1[/math] и [math]T_2[/math] соответственно.

 Pair<[math]T_1, ~T_2[/math]> {
   [math]T_1 ~first;[/math]
   [math]T_2 ~last;[/math]
 };

Сам дек можно инициализировать напрямую, вызвав конструктор [math]Deque(left, ~child, ~right)[/math], или через шаблоны [math]Deque\lt Pair\lt T_1, ~T_2\gt \gt [/math], тогда произойдёт следующее:

 Deque<Pair<[math] T_1, ~T_2 [/math]>> {
   [math]T_1[/math] left;
   [math]T_2[/math] right;
   Deque<Pair<Pair<[math] T_1, ~T_2 [/math]>, Pair<[math] T_1, ~T_2 [/math]>> child;
 };

Таким образом элементы с начала хранятся в левой ветке дерева, а с конца - в правой.

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

 push_front(x)
   if left == [math] \varnothing [/math]
     // если левый ребенок не существует, то сделаем его новым элементом
     return Deque(x, child, right)
   else
     // иначе объединим его с новым элементов и попытаемся добавить в дек на следующем уровне
     return Deque([math] \varnothing [/math], child.push_front(Pair<x, left>), right)

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

 pop_front()
   if left [math] \neq ~\varnothing[/math]
     // если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка
     return [math] \mathcal{h} [/math]left, Deque([math] \varnothing [/math], child, right)[math] \mathcal{i} [/math]
   else if child == [math] \varnothing[/math]
     // если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует,
     // то вернём пару из правого ребёнка и абсолютно пустого дека
     return [math] \mathcal{h} [/math]right, Deque([math] \varnothing ,~\varnothing ,~\varnothing [/math])[math] \mathcal{i} [/math]
   else
     /* 
      * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод pop_front()
      * и возвращённую пару "элемент-новый дек" сохраняем в переменные temp & newDeque
      * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется существующим 
      * или в деке будет отсутствовать ссылка на следующий дек
      */     
     temp, newDeque [math] \leftarrow [/math] child.pop_front()
     if temp == [math] \varnothing [/math]
       /*
        * это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты,
        * значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и child ссылается на абсолютно пустой дек,
        * поэтому возвращаем right текущего дека и пустой дек
        */
       return [math] \mathcal{h} [/math]right, Deque([math] \varnothing ,~\varnothing ,~\varnothing [/math])[math] \mathcal{i} [/math]
     else
       /*
        * если всё же temp не пуст, то надо вернуть первый элементы пары temp; 
        * в качестве left нового дека надо поставить temp.last (на уровне ниже temp хранил
        * в два раза больше элементов, поэтому на текущем уровне temp.last будет соответствовать 
        * требуемому количеству элементов); newDeque делаем child'ом
        * нового дека, а right текущего right'ом нового
        */
       return [math] \mathcal{h} [/math]temp.first, Deque(temp.last, newDeque, right)[math] \mathcal{i} [/math]

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

См. также

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

Ссылки

• Purely Functional Deques with Catenation by Robert E. Tarjan