Изменения

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

Тип <tex>\mathrm{Pair}</tex> хранит пару элементов <tex>first</tex> и <tex>last</tex> типов <tex>T</tex>.

Pair<<tex>T</tex>> { <tex>T ~first;</tex> <tex>T ~last;</tex> };

Сам дек можно инициализировать напрямую, вызвав конструктор <tex>\mathrm{Deque(left, ~child, ~right)}</tex>, или через шаблоны <tex>\mathrm{Deque<T>}</tex>, тогда произойдёт следующее:

Deque<<tex>T</tex>> { <tex>T</tex> left; <tex>T</tex> right; Deque<Pair<<tex>T</tex>>> child; };

Наша структура данных персистентна, следовательно операция <tex> push\_frontmathrm{pushFront(x, ~D) } </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex>, добавленным в начало <tex> D </tex>.

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

push_front'''pushFront'''(x, D) '''if ''' D == <tex> \emptyset </tex>

'''return ''' Deque(x, <tex> \emptyset ,~ \varnothing </tex>) '''else if ''' D.left == <tex> \varnothing </tex>

'''return ''' Deque(x, D.child, D.right) '''else'''

'''return ''' Deque(<tex> \varnothing </tex>, push_frontpushFront(Pair(x, D.left), D.child), D.right)

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

pop_front'''popFront'''(D) '''if ''' D == <tex> \emptyset </tex>

'''return ''' <tex> \mathcal{h} \varnothing ,~ \emptyset \mathcal{i} </tex> '''else ''' if D.left <tex> \neq ~\varnothing</tex>

'''if ''' D.child = <tex> \emptyset </tex> '''and ''' D.right = <tex> \varnothing </tex> '''return ''' <tex> \mathcal{h} </tex>D.left, <tex> \emptyset \mathcal{i} </tex> '''return ''' <tex> \mathcal{h} </tex>D.left, Deque(<tex> \varnothing </tex>, D.child, D.right)<tex> \mathcal{i} </tex> '''else if ''' D.child == <tex> \varnothing</tex>

'''return ''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex> '''else'''

* если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод pop_front()<tex>\mathrm{popFront}</tex> * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <tex>temp & </tex> и <tex>newDeque</tex>. * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется существующим не пустым * или в деке будет отсутствовать ссылка на следующий дек.

temp, newDeque <tex> \leftarrow </tex> pop_frontpopFront(D.child) '''if ''' temp == <tex> \varnothing </tex>

* значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и <tex>child </tex> ссылается на абсолютно пустой дек, * поэтому возвращаем <tex>right </tex> текущего дека и пустой дек

'''return ''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex> '''else'''

* если всё же <tex>temp </tex> не пуст, то надо вернуть первый элемент пары temp; * в качестве left нового дека надо поставить <tex>temp.last </tex> (на уровне ниже <tex>temp </tex> хранил * в два раза больше элементов, поэтому на текущем уровне <tex>temp.last </tex> будет соответствовать * требуемому количеству элементов); <tex>newDeque </tex> делаем <tex>child</tex>'ом * нового дека, а <tex>right </tex> текущего <tex>right</tex>'ом нового

'''return ''' <tex> \mathcal{h} langle </tex>temp.first, Deque(temp.last, newDeque, D.right)<tex> \mathcal{i} rangle </tex>

=== push_front pushFront ===

Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление <tex>1 </tex> к разряду числа в двоичном представлении: если в разряде <tex>1</tex>, то подряд идущие за ней единицы обнулятся {{---}} элементы объединяются в пары, иначе становятся на место этого разряда.

=== pop_front popFront ===

Посмотрим, как работает ''pop_front'' <tex>\mathrm{popFront}</tex> на примере дека, симметричного нашему предыдущему (в рисунке надо понять, что элементы хранятся слева направо: ''<tex>4 ~3 ~2 ~1''</tex>).

Запустим первый <tex> pop\_front() mathrm{popFront} </tex>. Он будет рекурсивно вызывать сам себя, пока не дойдёт до последней ветки. Тогда в пару <tex> \left \langle temp, ~newDeque \right \rangle </tex> сохранятся две пары элементов и пустой дек высоты <tex>0</tex>. Так как <tex> temp </tex> не пуст, то в предыдущий рекурсивный вызов вернётся пара: в <tex>temp </tex> новый сохранится пара ''<tex>4 ~3''</tex>, на текущем уровне будет пара ''<tex>2 ~1''</tex>, а <tex> child </tex> будет ссылаться на пустой дек. Потом пара ''<tex>4 ~3'' </tex> передастся выше, ''<tex>child'' </tex> сохраняет ссылку на предыдущий дек, и, наконец, ''<tex>4'' </tex> извлечётся. И так далее. Аналогично добавлению, процесс извлечения элемента можно представить, как вычитание <tex>1 </tex> из младшего разряда двоичного числа.