Rybak: Новая страница: « {{Определение |definition = '''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} с...»

2012-03-10T13:10:20Z

Новая страница: « {{Определение |definition = '''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} с...»

Новая страница

{{Определение
|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> соответственно.

<code style = "display: inline-block;">
Pair<<tex>T_1, ~T_2</tex>> {
<tex>T_1 ~first;</tex>
<tex>T_2 ~last;</tex>
};
</code>

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

Наша структура данных персистентна, следовательно операция <tex> D.push\_front(x) </tex> возвращает новый дек <tex> D' </tex>, c элементом <tex> x </tex> в начале.
<code>
push_front(x)
if left == <tex> \varnothing </tex>
// если левый ребенок не существует, то сделаем его новым элементом
return Deque(x, child, right)
else
// иначе объеденим его с новым элементов и попытаемся добавить в дек на следующем уровне
return Deque(<tex> \varnothing </tex>, child.push_front(Pair<x, left>), right)
</code>

Метод <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(<tex> \varnothing </tex>, child, right)<tex> \mathcal{i} </tex>
else if child == <tex> \varnothing</tex>
// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек тоже отсутсвует,
// значит, вернём пару из правого ребёнка и абсолютно пустого дека
return <tex> \mathcal{h} </tex>right, Deque(<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(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>
else
/*
* если всё же temp не пуст, то надо вернуть первый элементы пары temp,
* в качестве left нового дека надо поставить temp.last (на уровне ниже, из которого он пришёл,
* temp хранил в два раза больше элементов, поэтому на текущем уровне temp.last будет соответствовать
* как раз требуемому количеству элементов), newDeque делаем child'ом
* нового дека, а right текущего, right'ом нового
*/
return <tex> \mathcal{h} </tex>temp.first, Deque(temp.last, newDeque, right)<tex> \mathcal{i} </tex>
</code>

Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> O(\log ~n) </tex>

== См. также ==

* [[Очередь]]
* [[Стек]]
* [[Персистентный стек]]

== Ссылки ==

* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451 Purely Functional Deques with Catenation by Robert E. Tarjan]

[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]

Участник:Rybak/Черновик - История изменений

Rybak: Новая страница: « {{Определение |definition = '''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} с...»