3622
правки
Изменения
→Эффективная реализация
Кроме дека ещё существует структура данных, называемая ''steque'', которая представляет собой объединение стека и очереди {{- --}} элементы можно добавлять только в один конец, а извлекать можно {{---}} с обоих.
== Эффективная реализация ==
=== Способ хранения структуры ===
[[Файл:Tree_deque.png|220px|right]]
<code>
</code>
<code>
'''Pair<T, Deque<T>>''' popFront(D: '''Deque<PairT>'''): '''if''' D == <tex> \emptyset </tex> <font color=darkgreen>// изъятие элемента из пустого дека возвращает пару "нулевой элемент {{---}} пустой дек"</font> '''return''' <tex> T_1\mathcal{h} \varnothing , ~T_2 \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>T_1\mathcal{h} </tex> D.left;, Deque(<tex> \varnothing </tex>, D.child, D.right)<tex> \mathcal{i} </tex> '''else if''' D.child == <tex> \varnothing</tex> <font color=darkgreen>// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек отсутствует, // то вернём пару из правого ребёнка и абсолютно пустого дека</font> '''return''' <tex>T_2\mathcal{h} </tex> D.right;, <tex>\emptyset \mathcal{i} </tex> Deque'''else''' <font color=darkgreen>/* * если два предыдущих условия оказались не выполнены, то мы рекурсивно вызываем метод <tex>\mathrm{popFront}</tex> * и возвращённую пару "элемент {{---}} новый дек" сохраняем в переменные <Pairtex>temp<Pair/tex> и <tex>newDeque</tex> T_1. * Рекурсивные вызовы прекратятся, ~T_2 как только левый ребёнок окажется не пустым * или в деке будет отсутствовать ссылка на следующий дек. */</font> (temp, newDeque) = popFront(D.child) <font color=darkgreen>/* * здесь <tex>temp</tex>всегда не пуст; надо вернуть первый элемент пары temp * (в этом блоке temp всегда будет иметь тип <tex>, \mathrm{Pair}</tex>); * в качестве left нового дека надо поставить <tex> T_1temp.last</tex> (на уровне ниже <tex>temp</tex> хранил * в два раза больше элементов, ~T_2 поэтому на текущем уровне <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>
</code>
[[Файл:PopDequeExample.png|700px]]
== См. также ==
* [[Список]]
* [[Стек]]
* [[Очередь]]
* [[Персистентный стек]]
== Ссылки Источники информации ==
* [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.13.3451 Purely Functional Deques with Catenation by Robert E. Tarjan]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Амортизационный анализ]]
[[Категория: Структуры данных]]