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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 9: Строка 9:
  
 
== Эффективная реализация ==
 
== Эффективная реализация ==
 +
 +
Написать дек на массиве не представляет особого труда, зная уже, как работают стек и очередь. Далее будет приведена реализация операций добавление элемента и извлечение из одного конца дека за истинное время работы <tex> O(\log ~ n). </tex> Добавление и исключение из другого конца делается симметрично.
 +
 +
<code>
 +
Deque<T>(first, child, last)
 +
  Deque<T> {
 +
    T first, last;
 +
    Deque<T> child;
 +
  };
 +
</code>
 +
 +
Так как наша структура данных персистентная, то операция <tex> D.push\_front(x) </tex> возвращает новый дек <tex> D' </tex>, c элементом <tex> x </tex> в начале.
 +
<code>
 +
  push_front(x)
 +
    if first == <tex> \varnothing </tex>
 +
      return Deque<T>(x, child, last)
 +
    else
 +
      return Deque<T>(<tex> \varnothing </tex>, c.push_front(x, first), last)
 +
</code>
 +
 +
Метод <tex> D.pop\_front() </tex> возвращает пару <tex> \left \langle e, ~D' \right \rangle </tex> из первого элемента и нового дека, полученного из старого изъятием этого элемента.
 +
<code>
 +
  pop_front()
 +
    if first <tex> \neq ~\varnothing</tex>
 +
      return <tex> \mathcal{h} </tex>first, Deque<T>(<tex> \varnothing </tex>, child, last)<tex> \mathcal{i} </tex>
 +
    else if child == <tex> \varnothing</tex>
 +
      return <tex> \mathcal{h} </tex>last, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>
 +
    else
 +
      temp, newDeque <tex> \leftarrow </tex> child.pop_front()
 +
      if temp == <tex> \varnothing </tex>
 +
        return <tex> \mathcal{h} </tex>last, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>
 +
      else
 +
        return <tex> \mathcal{h} </tex>temp.first, Deque<T>(temp.child, newDeque, last)<tex> \mathcal{i} </tex>
 +
</code>
 +
 +
Чтобы извлечь элемент, придётся спуститься не больше, чем на глубину дерева. Аналогично для добавления. Поэтому обе операции выполняются за <tex> O(\log ~n) </tex>
  
 
== См. также ==
 
== См. также ==

Версия 21:56, 7 марта 2012

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


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


Кроме дека ещё существует структура данных, называемая steque, которая представляет собой объединение стека и очереди - элементы можно добавлять только в один конец, а извлекать можно с обоих. В отличие от обычных стека и очереди, deque и 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(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]

См. также

Ссылки