Изменения

'''Дек''' (англ. ''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>.

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

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

Сам дек можно инициализировать напрямую, вызвав конструктор === pop ===Метод <tex>Deque\mathrm{popFront(left, ~child, ~rightD)} </tex>, или через шаблоны возвращает пару <tex>Deque<Pair<T_1\left \langle e, ~T_2>>D' \right \rangle </tex>из первого элемента и нового дека, тогда произойдёт следующееполученного из старого изъятием этого элемента.

'''Pair<T, Deque<T>>''' popFront(D: '''Deque<PairT>'''): '''if''' D == <tex> \emptyset </tex> <font color=darkgreen>// изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек"</font> '''return''' <tex> T_1\mathcal{h} \varnothing , ~T_2 \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>T_1\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>T_2\mathcal{h} </tex> D.right;, <tex>\emptyset \mathcal{i} </tex> Deque'''else''' <font color=darkgreen>/* * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод <tex>\mathrm{popFront}</tex> * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <Pairtex>temp<Pair/tex> и <tex>newDeque</tex> T_1. * Рекурсивные вызовы прекратятся, ~T_2 как только левый ребёнок окажется не пустым * или в деке будет отсутствовать ссылка на следующий дек. */</font> (temp, newDeque) = popFront(D.child) <font color=darkgreen>/* * здесь <tex>temp</tex>всегда не пуст; надо вернуть первый элемент пары temp * (в этом блоке temp всегда будет иметь тип <tex>, \mathrm{Pair}</tex>); * в качестве left нового дека надо поставить <tex> T_1temp.last</tex> (на уровне ниже <tex>temp</tex> хранил * в два раза больше элементов, ~T_2 поэтому на текущем уровне <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.push\_front(x) i </tex> возвращает новый дек -ом уровне дека не более <tex> D' 2^i </tex>, c элементом элементов. Пусть глубина текущего дека <tex> x d. </tex> Тогда в начале.нём может находится не более <codetex> push_front(x) if left =n = 1 + 2 + 4 + \ldots + 2^d </tex> объектов, откуда получаем <tex> d = \varnothing mathcal{b} \log_2 n \mathcal{c} </tex>. // если левый ребенок Чтобы извлечь элемент, придётся спуститься не существуетбольше, то сделаем его новым элементом return Dequeчем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <Ttex>\mathcal{O}(x\log n) </tex> == Пример == Рассмотрим поподробнее операции. В худшем случае элементы будут добавляться только в один конец, child, right)а извлекаться из другого. === pushFront === else // иначе объеденим его с новым элементов Изначально у нас пустой дек. Элементы будем добавлять в левый конец дека и нумеровать согласно порядку добавления. Сначала добавим первый элемент. Он встанет на позицию левого ребёнка первого уровня дека. Теперь попытаемся добавить в дек второй элемент. Позиция левого ребёнка занята, значит, мы объединяем новый элемент со старым и ставим сформированную пару на следующем уровне return Dequeместо левого ребёнка второго дека. Процесс добавления можно представить, как прибавление <tex>1<T/tex>(к разряду числа в двоичном представлении: если в разряде <tex> \varnothing 1</tex>, childто подряд идущие за ней единицы обнулятся {{---}} элементы объединяются в пары, иначе становятся на место этого разряда.push_front(Pair<x, left>), right)</code>[[Файл:PushDequeExample.png|700px]] === popFront ===

Метод <tex> D.pop\_front() </tex> возвращает пару <tex> \left \langle eПосмотрим, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.<code> pop_front() if left <tex> \neq ~\varnothing</tex> // если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка return <tex> \mathcal{h} </tex>left, Deque<T>(<tex> \varnothing </tex>, child, right)как работает <tex> \mathcalmathrm{ipopFront} </tex> else if child == <tex> \varnothing</tex> // если левый ребёнок оказался пуст, и при этом ссылка на следующий дек тоже отсутсвует, // значит, вернём пару из правого ребёнка и абсолютно пустого примере дека return <tex> \mathcal{h} </tex>right, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex> else /* * если два предыдущих условия оказались невыполнены, то мы рекурсивно вызываем метод pop_frontсимметричного нашему предыдущему () * и возвращённую пару "элемент-новый дек" сохраняем в переменные temp & newDeque * Рекурсивные вызовы прекратятся, как только левый ребёнок окажется существующим * или в деке будет отсутствовать ссылка на следущий дек */ tempрисунке надо понять, newDeque <tex> \leftarrow </tex> child.pop_front() if temp == <tex> \varnothing </tex> /* * это возможно только в случае, когда в деке на максимальной глубине все что элементы оказались пусты * значит мы сейчас на предпоследнем уровне, и левый ребёнок пустой, а child ссылается на абсолютно пустой дек, * поэтому мы возвращаем right текущего дека, и пустой дек */ return хранятся слева направо: <tex> \mathcal{h} </tex>right, Deque<T>(<tex> \varnothing ,4 ~3 ~\varnothing ,2 ~\varnothing </tex>)<tex> \mathcal{i} 1</tex> else /* * если всё же temp не пуст, то надо вернуть первый элементы пары temp, * в качестве left нового дека надо поставить temp.last (на уровне ниже, из которого он пришёл, temp хранил в два раза больше элементов * поэтому на текущем уровне temp.last будет соответствовать как раз требуемому количеству элементов), newDeque делаем child'ом * нового дека, а right текущего, right'ом нового */ return <tex> \mathcal{h} </tex>temp.first, Deque<T>(temp.last, newDeque, right)<tex> \mathcal{i} </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>из младшего разряда двоичного числа.

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