Изменения

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

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

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

Pair<'''class''' Deque<texT>T_1, ~T_2</tex>> {: T left <tex>T_1 ~first;</tex>T right Deque<texPair<T>T_2 ~last;</tex> };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} </tex>right. Процесс добавления можно представить, Deque(как прибавление <tex> \varnothing ,~\varnothing ,~\varnothing 1</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>из младшего разряда двоичного числа.

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