Персистентный дек — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 5: Строка 5:
 
'''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т. е. их можно удалять и добавлять как в начало, так и в конец дека.
 
'''Дек''' (англ. deque {{---}} double ended queue {{---}} очередь с двумя концами) {{---}} структура данных с двусторонним доступом к элементам, т. е. их можно удалять и добавлять как в начало, так и в конец дека.
 
}}
 
}}
[[Файл:Deque.png|thumb|325px|Дек]]
+
[[Файл:Deque.png|thumb|250px|Дек]]
  
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать можно с обоих. В отличие от обычных стека и очереди, ''deque'' и ''steque'' используются в задачах намного реже.
+
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать можно с обоих.
  
 
== Эффективная реализация ==
 
== Эффективная реализация ==
  
 
Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.
 
Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.
 +
[[Файл:Tree_deque.png|thumb|Древовидная структура дека]]
 +
 +
Персистентный дек можно визуально представить как дерево, где каждый узел хранит пару первый элемент и последний, а также ''ребёнка'' - ссылку на следующий дек. Только с каждым уровнем вложенности левый и правый элемент представляют собой массив размера в два раза больше, чем на предыдущем уровне.
  
 
<code>
 
<code>

Версия 18:03, 9 марта 2012

Эта статья находится в разработке!


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

Кроме дека ещё существует структура данных, называемая steque, которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать можно с обоих.

Эффективная реализация

Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы [math] O(\log ~ n). [/math] Добавление и исключение из другого конца делается симметрично.

Древовидная структура дека

Персистентный дек можно визуально представить как дерево, где каждый узел хранит пару первый элемент и последний, а также ребёнка - ссылку на следующий дек. Только с каждым уровнем вложенности левый и правый элемент представляют собой массив размера в два раза больше, чем на предыдущем уровне.

Deque<T>(first, child, last)

 Deque<T> {
   T first, last;
   Deque<T> child;
 };

Так как наша структура данных персистентная, то операция [math] D.push\_front(x) [/math] возвращает новый дек [math] D' [/math], c элементом [math] x [/math] в начале.

 push_front(x)
   if first == [math] \varnothing [/math]
     return Deque<T>(x, child, last)
   else
     return Deque<T>([math] \varnothing [/math], c.push_front(Pair<x, first>), last)

Метод [math] D.pop\_front() [/math] возвращает пару [math] \left \langle e, ~D' \right \rangle [/math] из первого элемента и нового дека, полученного из старого изъятием этого элемента.

 pop_front()
   if first [math] \neq ~\varnothing[/math]
     return [math] \mathcal{h} [/math]first, Deque<T>([math] \varnothing [/math], child, last)[math] \mathcal{i} [/math]
   else if child == [math] \varnothing[/math]
     return [math] \mathcal{h} [/math]last, Deque<T>([math] \varnothing ,~\varnothing ,~\varnothing [/math])[math] \mathcal{i} [/math]
   else
     temp, newDeque [math] \leftarrow [/math] child.pop_front()
     if temp == [math] \varnothing [/math]
       return [math] \mathcal{h} [/math]last, Deque<T>([math] \varnothing ,~\varnothing ,~\varnothing [/math])[math] \mathcal{i} [/math]
     else
       return [math] \mathcal{h} [/math]temp.first, Deque<T>(temp.child, newDeque, last)[math] \mathcal{i} [/math]

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

См. также

Ссылки