Изменения

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

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

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

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

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

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

push_front'''Pair<T, Deque<T>>''' popFront(xD: '''Deque<T>'''): '''if first ''' 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(<Ttex> \varnothing </tex>(x, D.child, lastD.right)<tex> \mathcal{i} </tex> '''elseif''' D.child == <tex> \varnothing</tex> <font color=darkgreen>// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует, // то вернём пару из правого ребёнка и абсолютно пустого дека</font> '''return Deque''' <tex> \mathcal{h} </tex>D.right, <tex>\emptyset \mathcal{i} </tex> '''else''' <Tfont color=darkgreen>(/* * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод <tex> \varnothing mathrm{popFront}</tex> * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <tex>temp</tex> и <tex>newDeque</tex>. * Рекурсивные вызовы прекратятся, cкак только левый ребёнок окажется не пустым * или в деке будет отсутствовать ссылка на следующий дек.push_front */</font> (temp, newDeque) = popFront(D.child) <font color=darkgreen>/* * здесь <tex>temp</tex> всегда не пуст; надо вернуть первый элемент пары temp * (в этом блоке temp всегда будет иметь тип <tex>\mathrm{Pair}</tex>); * в качестве left нового дека надо поставить <tex>temp.last</tex> (на уровне ниже <xtex>temp</tex> хранил * в два раза больше элементов, firstпоэтому на текущем уровне <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>

Метод <tex> DОперации добавления в правый конец и извлечение из него делаются симметрично.pop\_front()  === Асимптотика времени работы ===Таким образом, если мы добавляем элементы только в один конец, то на </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle i </tex> из первого элемента и нового -ом уровне дека, полученного из старого изъятием этого элемента.<code> pop_front() if first не более <tex> \neq ~\varnothing2^i </tex> return элементов. Пусть глубина текущего дека <tex> \mathcal{h} d. </tex>first, Deque<T>(Тогда в нём может находится не более <tex> n = 1 + 2 + 4 + \varnothing ldots + 2^d </tex>объектов, child, last)откуда получаем <tex> d = \mathcal{ib} </tex> else if child == <tex> \varnothing</tex> return <tex> log_2 n \mathcal{hc} </tex>last. Чтобы извлечь элемент, Deque<T>(<tex> \varnothing придётся спуститься не больше,~\varnothing ,~\varnothing </tex>)чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> \mathcal{iO} (\log n) </tex> else temp== Пример == Рассмотрим поподробнее операции. В худшем случае элементы будут добавляться только в один конец, newDeque <tex> \leftarrow </tex> childа извлекаться из другого.pop_front() if temp === pushFront ===  Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на место левого ребёнка второго дека. Процесс добавления можно представить, как прибавление <tex> \varnothing 1</tex> return к разряду числа в двоичном представлении: если в разряде <tex> \mathcal{h} 1</tex>last, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcalто подряд идущие за ней единицы обнулятся {{i---}} </tex>элементы объединяются в пары, иначе становятся на место этого разряда. [[Файл:PushDequeExample.png|700px]] === popFront === else return Посмотрим, как работает <tex> \mathcalmathrm{hpopFront} </tex>temp.firstна примере дека, Deque<T>симметричного нашему предыдущему (temp.childв рисунке надо понять, newDeque, last)что элементы хранятся слева направо: <tex> \mathcal{i} 4 ~3 ~2 ~1</tex></code>).

Чтобы извлечь элементЗапустим первый <tex> \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> O(\log ~n) 1</tex>из младшего разряда двоичного числа.

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