Изменения

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

{{Определение|definition = '''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т. е. их можно удалять и добавлять как в начало, так и в конец дека.}} Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди {{- --}} элементы можно добавлять только в один конец, а извлекать можно {{---}} с обоих. В отличие от обычных стека и очереди, ''deque'' и ''steque'' используются в задачах намного реже.

Написать Персистентный дек на массиве не представляет особого трудаможно визуально представить как [[Список#Односвязный список | односвязный список]], зная ужегде каждый узел хранит пару {{---}} левый элемент и правый, как работают стек и очередьа также ''ребёнка'' {{---}} ссылку на следующий узел. Далее будет приведена реализация операций добавление элемента Только левый и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n)правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. </tex> Добавление и исключение из другого конца делается симметричноЭто удобно сделать с помощью типа ''пара''.

Тип <tex>\mathrm{Pair}</tex> хранит пару элементов <tex>\mathrm{first}</tex> и <tex>\mathrm{last}</tex> типов <tex>T</tex>.<codestyle = "display: inline-block;">Deque '''class''' Pair<T>: T first T last</code>Сам дек можно инициализировать напрямую, вызвав конструктор <tex>\mathrm{Deque(firstleft, ~child, last~right) }</tex>. Описание структуры через шаблон <tex>\mathrm{Deque{<}T{>}}</tex> следующее:<code style = "display: inline-block;"> '''class''' Deque<T> {: T left T first, last;right Deque<Pair<T>> child; };

Так как наша структура данных персистентная=== push ===Пустой дек будем обозначать значком <tex> \emptyset </tex>, то операция а пустую пару {{---}} <tex> D.push\_front(x) varnothing </tex> возвращает новый дек , чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю <tex> D' \mathrm{left}</tex>. Если же работаем с концом, c элементом то обращаемся сперва к полю <tex> x \mathrm{right}</tex> в начале.

push_front'''Deque<T>''' pushFront(x: '''T''', D: '''Deque<T>'''): '''if first ''' D == <tex> \varnothing emptyset </tex> <font color=darkgreen>// если дек пустой, то формируем новый дек </font> '''return ''' Deque(x, <tex> \emptyset ,~ \varnothing </tex>) '''else if''' D.left == <tex> \varnothing </tex> <Tfont color=darkgreen>// если левый ребенок не существует, то сделаем <tex> x </tex> левым ребёнком </font> '''return''' Deque(x, D.child, lastD.right) '''else''' <font color=darkgreen>// иначе объединим левого ребёнка с новым элементом и попытаемся добавить в дек на следующем уровне </font> '''return ''' Deque<T>(<tex> \varnothing </tex>, c.push_frontpushFront(Pair<(x, first>D.left), D.child), lastD.right)

=== pop ===Метод <tex> D.pop\_frontmathrm{popFront(D) } </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.

pop_front'''Pair<T, Deque<T>>''' popFront(D: '''Deque<T>'''): '''if''' D == <tex> \emptyset </tex> <font color=darkgreen>// изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек"</font> '''return''' <tex> \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} </tex> '''else if first ''' D.left <tex> \neq ~\varnothing</tex> <font color=darkgreen>// если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка, // но если остался только левый ребёнок, то возвращаем его и пустой дек</font> '''if''' D.child == <tex> \emptyset </tex> '''and''' D.right == <tex> \varnothing </tex> '''return ''' <tex> \mathcal{h} </tex>firstD.left, Deque<Ttex> \emptyset \mathcal{i} </tex> '''return''' <tex> \mathcal{h} </tex>D.left, Deque(<tex> \varnothing </tex>, D.child, lastD.right)<tex> \mathcal{i} </tex> '''else if ''' D.child == <tex> \varnothing</tex> <font color=darkgreen>// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует, // то вернём пару из правого ребёнка и абсолютно пустого дека</font> '''return ''' <tex> \mathcal{h} </tex>lastD.right, Deque<T>(<tex> \varnothing ,~emptyset \varnothing ,~\varnothing mathcal{i} </tex>) '''else''' <font color=darkgreen>/* * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод <tex> \mathcalmathrm{ipopFront} </tex> else * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <tex>temp, newDeque </tex> и <tex> \leftarrow newDeque</tex> child.pop_front * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется не пустым * или в деке будет отсутствовать ссылка на следующий дек. */</font> (temp, newDeque) = popFront(D.child) if temp =<font color= darkgreen>/* * здесь <tex> \varnothing temp</tex>всегда не пуст; надо вернуть первый элемент пары temp return * (в этом блоке temp всегда будет иметь тип <tex> \mathcalmathrm{hPair} </tex>); * в качестве left нового дека надо поставить <tex>temp.last, Deque<T/tex>(на уровне ниже <tex>temp</tex> \varnothing хранил * в два раза больше элементов,~\varnothing поэтому на текущем уровне <tex>temp.last</tex> будет соответствовать * требуемому количеству элементов); <tex>newDeque</tex> делаем <tex>child</tex>'ом * нового дека,~\varnothing а <tex>right</tex>)текущего <tex> \mathcal{i} right</tex>'ом нового */</font> else '''return ''' <tex> \mathcal{h} langle </tex>temp.first, Deque<T>(temp.childlast, newDeque, lastD.right)<tex> \mathcal{i} rangle </tex>

Операции добавления в правый конец и извлечение из него делаются симметрично. === Асимптотика времени работы ===Таким образом, если мы добавляем элементы только в один конец, то на <tex> i </tex>-ом уровне дека не более <tex> 2^i </tex> элементов. Пусть глубина текущего дека <tex> d. </tex> Тогда в нём может находится не более <tex> n = 1 + 2 + 4 + \ldots + 2^d </tex> объектов, откуда получаем <tex> d = \mathcal{b} \log_2 n \mathcal{c} </tex>. Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> \mathcal{O}(\log ~n) </tex> == Пример == Рассмотрим поподробнее операции. В худшем случае элементы будут добавляться только в один конец, а извлекаться из другого.

== Ссылки Источники информации ==

* [http://wwwciteseerx.eecsist.usmapsu.edu/websviewdoc/people/okasaki/jfp95summary?doi=10.1.1.13.ps 3451 Purely Functional Catable Deques with Catenation by Chris OkasakiRobert E. Tarjan]