Изменения

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

Deque Pair<T<tex>(firstT_1, child, last) Deque~T_2<T/tex>> { T <tex>T_1 ~first, last;</tex> Deque<Ttex> childT_2 ~last;</tex>

Так как наша Сам дек можно инициализировать напрямую, вызвав конструктор <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> в начале.

if first left == <tex> \varnothing </tex> // если левый ребенок не существует, то сделаем его новым элементом return Deque<T>(x, child, lastright)

// иначе объеденим его с новым элементов и попытаемся добавить в дек на следующем уровне return Deque<T>(<tex> \varnothing </tex>, cchild.push_front(Pair<x, firstleft>), lastright)

if first left <tex> \neq ~\varnothing</tex> // если левый ребёнок не пуст, то возвращаем пару из него и нового дека без левого ребёнка return <tex> \mathcal{h} </tex>firstleft, Deque<T>(<tex> \varnothing </tex>, child, lastright)<tex> \mathcal{i} </tex>

// если левый ребёнок оказался пуст, и при этом ссылка на следующий дек тоже отсутсвует, // значит, вернём пару из правого ребёнка и абсолютно пустого дека return <tex> \mathcal{h} </tex>lastright, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>

/* * это возможно только в случае, когда в деке на максимальной глубине все элементы оказались пусты * значит мы сейчас на предпоследнем уровне, и левый ребёнок пустой, а child ссылается на абсолютно пустой дек, * поэтому мы возвращаем right текущего дека, и пустой дек */ return <tex> \mathcal{h} </tex>lastright, Deque<T>(<tex> \varnothing ,~\varnothing ,~\varnothing </tex>)<tex> \mathcal{i} </tex>

/* * если всё же temp не пуст, то надо вернуть первый элементы пары temp, * в качестве left нового дека надо поставить temp.last (на уровне ниже, из которого он пришёл, temp хранил в два раза больше элементов * поэтому на текущем уровне temp.last будет соответствовать как раз требуемому количеству элементов), newDeque делаем child'ом * нового дека, а right текущего, right'ом нового */ return <tex> \mathcal{h} </tex>temp.first, Deque<T>(temp.childlast, newDeque, lastright)<tex> \mathcal{i} </tex>