1632
правки
Изменения
м
rollbackEdits.php mass rollback
'''Дек''' (англ. ''deque'' {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т.е. их можно удалять и добавлять как в начало, так и в конец дека.
== Эффективная реализация ==
=== Способ хранения структуры ===
[[Файл:Tree_deque.png|220px|right]]
Персистентный дек можно визуально представить как [[Список#Односвязный список | односвязный список]], где каждый узел хранит пару {{---}} левый элемент и правый, а также ''ребёнка'' {{---}} ссылку на следующий узел. Только левый и правый элемент каждого узла хранят в два раза больше объектов, чем предыдущий. Это удобно сделать с помощью типа ''пара''.
Тип <tex>\mathrm{Pair}</tex> хранит пару элементов <tex>\mathrm{first}</tex> и <tex>\mathrm{last}</tex> типов <tex>T</tex>.
<code style = "display: inline-block;">
'''class''' Pair<T>:
Наша структура данных персистентна, следовательно операция <tex> \mathrm{pushFront(x, ~D)} </tex> возвращает новый дек <tex> D' </tex> c элементом <tex> x </tex>, добавленным в начало <tex> D </tex>.
=== push ===Пустой дек будем обозначать значком <tex> \emptyset </tex>, а пустую пару {{---}} <tex> \varnothing </tex>, чтобы было яснее, когда мы обращаемся к деку, а когда к элементу. Когда мы хотим добавить элемент в начало дека или удалить из начала, то прежде всего обращаемся к полю <tex>\mathrm{left}</tex>. Если же работаем с концом, то обращаемся сперва к полю <tex>\mathrm{right}</tex>.
<code>
'''Deque<T>''' pushFront(x: '''T''', D: '''Deque<T>'''):
</code>
=== pop ===
Метод <tex> \mathrm{popFront(D)} </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
<code>
'''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>
* или в деке будет отсутствовать ссылка на следующий дек.
*/</font>
(temp, newDeque <tex> \leftarrow </tex> ) = popFront(D.child) '''if''' temp == <tex> \varnothing </tex> <font color=darkgreen>/* * это возможно только тогда, когда в деке на максимальной глубине все элементы оказались пусты, * значит, мы сейчас на предпоследнем уровне, левый ребёнок пустой и здесь <tex>childtemp</tex> ссылается на абсолютно пустой дек,всегда не пуст; надо вернуть первый элемент пары temp * поэтому возвращаем <tex>right</tex> текущего дека и пустой дек */</font> '''return''' (в этом блоке temp всегда будет иметь тип <tex> \mathcalmathrm{hPair} </tex>D.right, <tex>\emptyset \mathcal{i} </tex> '''else''' <font color=darkgreen>/* * если всё же <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>'ом нового */</font> '''return''' <tex> \langle </tex>temp.first, Deque(temp.last, newDeque, D.right)<tex> \rangle </tex>
</code>
Операции добавления в правый конец и извлечение из него делаются симметрично.
=== Асимптотика времени работы ===Таким образом, если мы добавляем элементы только в один конец, то на <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>
== Пример ==
Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление <tex>1</tex> к разряду числа в двоичном представлении: если в разряде <tex>1</tex>, то подряд идущие за ней единицы обнулятся {{---}} элементы объединяются в пары, иначе становятся на место этого разряда.
[[Файл:PushDequeExample.png|700px]]
* [[Персистентный стек]]
== Ссылки Источники информации ==
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451 Purely Functional Deques with Catenation by Robert E. Tarjan]
