Изменения

 '''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т.е. их можно удалять и добавлять как в начало, так и в конец дека. [[Файл:Deque.png|thumb|220px|Дек]]Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди {{- --}} элементы можно добавлять только в один конец, а извлекать {{---}} с обоих.

=== Способ хранения структуры ===[[Файл:Tree_deque.png|thumb|220px|right|Древовидная структура дека]]

Персистентный дек можно визуально представить как дерево[[Список#Односвязный список | односвязный список]], где каждый узел хранит пару {{- --}} левый элемент и правый, а также ''ребёнка'' {{-- -}} ссылку на следующий декузел. Только с каждым уровнем вложенности левый и правый элемент каждого узла хранят в два раза больше объектов, чем на предыдущем уровнепредыдущий. Это удобно сделать с помощью типа ''пара''.

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

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

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

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

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

Наша структура данных персистентна=== 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''' D == <tex> \emptyset </tex> <font color=darkgreen>// если дек пустой, то формируем новый дек </font> '''return''' Deque(x, <tex> \emptyset ,~ \varnothing </tex>) '''else if ''' D.left == <tex> \varnothing </tex> <font color=darkgreen>// если левый ребенок не существует, то сделаем его новым элементом<tex> x </tex> левым ребёнком </font> '''return ''' Deque(x, D.child, D.right) '''else''' <font color=darkgreen>// иначе объединим его левого ребёнка с новым элементов элементом и попытаемся добавить в дек на следующем уровне</font> '''return ''' Deque(<tex> \varnothing </tex>, child.push_frontpushFront(Pair(x, D.left), D.child), D.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 ''' 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>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> <font color=darkgreen>// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует, // то вернём пару из правого ребёнка и абсолютно пустого дека</font> '''return ''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex> '''else''' <font color=darkgreen>/* * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод pop_front()<tex>\mathrm{popFront}</tex> * и возвращённую пару "элемент{{---}} новый дек" сохраняем в переменные <tex>temp & </tex> и <tex>newDeque</tex>. * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется существующим не пустым * или в деке будет отсутствовать ссылка на следующий дек. */ </font> (temp, newDeque <tex> \leftarrow </tex> ) = popFront(D.child.pop_front() if temp =<font color= <texdarkgreen> \varnothing </tex> /* * это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты, * значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и child ссылается на абсолютно пустой дек, * поэтому возвращаем right текущего дека и пустой дек */ return здесь <tex> \mathcal{h} temp</tex>right, всегда не пуст; надо вернуть первый элемент пары temp * (в этом блоке temp всегда будет иметь тип <tex>\emptyset \mathcalmathrm{iPair} </tex> else /* * если всё же temp не пуст, то надо вернуть первый элемент пары 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>'ом нового */</font> '''return ''' <tex> \mathcal{h} langle </tex>temp.first, Deque(temp.last, newDeque, D.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> O(d = \log ~mathcal{b} \log_2 n) \mathcal{c} </tex>.

Таким образом, если мы добавляем элементы только Изначально у нас пустой дек. Элементы будем добавлять в один левый конецдека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, то значит, мы объединяем новый элемент со старым и ставим сформированную пару на <tex> i </tex>-ом уровне место левого ребёнка второго дека не более <tex> 2^i </tex> элементов. Пусть высота текущего дека Процесс добавления можно представить, как прибавление <tex> h. 1</tex> Тогда к разряду числа в двоичном представлении: если в нём может находится не более разряде <tex> n ~=~ 1 ~+~ 2 ~+~ 4 ~+...+~ 2^h </tex> объектов, откуда получаем <tex> h = \mathcalто подряд идущие за ней единицы обнулятся {{b---} \log_2 ~n \mathcal{c} </tex>элементы объединяются в пары, иначе становятся на место этого разряда.

Посмотрим, как работает <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> pop 1</tex> тоже выполняется за <tex> O(\log ~ n)из младшего разряда двоичного числа. </tex> [[Файл:PopDequeExample.png|700px]]

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