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

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

Дек (англ. 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]

Описание асипмтотики

Рассмотрим поподробнее асимптотику операций. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.

push_front

Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Этот элемент встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Добавим третий элемент. После предыдущего действия появилась свободная вакансия на место левого ребёнка дека первого уровня, поэтому новый элемент занимает это место. И, наконец, добавим 4-ый элемент. Он объединяется в пару с левым ребёнком дека первого уровня, затем новая пара объединяется со старой парой на втором уровне и добавляется в дек на высоте 2. И так далее.

Таким образом, если мы добавляем элементы только в один конец, то на [math] i [/math]-ом уровне дека не более [math] 2^i [/math] элементов. Пусть высота текущего дека [math] h. [/math] Тогда в нём может находится не более [math] n ~=~ 1 ~+~ 2 ~+~ 4 ~+...+~ 2^h [/math] объектов, откуда получаем [math] h = \mathcal{b} \log_2 ~n \mathcal{c} [/math].

pop_front

Посмотрим, как работает pop_front на примере дека, симметричного нашему предыдущему (в рисунке надо понять, что элементы хранятся слева направо: 4 3 2 1).

Запустим первый [math] pop\_front() [/math]. Он будет рекурсивно вызывать сам себя, пока не дойдёт до последней ветки. Тогда в пару [math] \left \langle temp, ~newDeque \right \rangle [/math] сохранятся две пары элементов и пустой дек высоты 0. Так как [math] temp [/math] не пуст, то в предыдущий рекурсивный вызов вернётся пара: в temp новый сохранится пара 4 3, на текущем уровне будет пара 2 1, а [math] child [/math] будет ссылаться на пустой дек. Потом пара 4 3 передастся выше, child сохраняет ссылку на предыдущий дек, и, наконец, 4 извлечётся. И так далее. Как видно, [math] pop [/math] тоже выполняется за [math] O(\log ~ n). [/math]

См. также

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

Ссылки

• Purely Functional Deques with Catenation by Robert E. Tarjan