Изменения

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

=== Способ хранения структуры ===[[Файл:Tree_deque.png|thumb|220px|right|Древовидная структура дека]]Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.

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

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

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

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

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