Editing Double-ended queue (section)

===Purely functional implementation===
Double-ended queues can also be implemented as a [[purely functional data structure]].<ref name="functional">{{cite thesis |url=https://www.cs.cmu.edu/~rwh/students/okasaki.pdf |first=Chris |last=Okasaki |title=Purely Functional Data Structures |type=Ph.D. thesis |date=September 1996 |publisher=Carnegie Mellon University |id=CMU-CS-96-177}}</ref>{{rp|115}} Two versions of the implementation exist. The first one, called '''real-time deque'', is presented below. It allows the queue to be [[persistent data structure|persistent]] with operations in {{math|''O''(1)}} worst-case time, but requires [[lazy evaluation|lazy]] lists with [[memoization]]. The second one, with no lazy lists nor memoization is presented at the end of the sections. Its [[amortized analysis|amortized]] time is {{math|''O''(1)}} if the persistency is not used; but the worst-time complexity of an operation is {{math|''O''(''n'')}} where {{mvar|n}} is the number of elements in the double-ended queue.

Let us recall that, for a list <code>l</code>, <code>|l|</code> denotes its length, that <code>NIL</code> represents an empty list and <code>CONS(h, t)</code> represents the list whose head is <code>h</code> and whose tail is <code>t</code>. The functions <code>drop(i, l)</code> and <code>take(i, l)</code> return the list <code>l</code> without its first <code>i</code> elements, and the first <code>i</code> elements of <code>l</code>, respectively. Or, if <code>|l| < i</code>, they return the empty list and <code>l</code> respectively.

==== Real-time deques via lazy rebuilding and scheduling ====
A double-ended queue is represented as a sextuple <code>(len_front, front, tail_front, len_rear, rear, tail_rear)</code> where <code>front</code> is a [[linked list]] which contains the front of the queue of length <code>len_front</code>. Similarly, <code>rear</code> is a linked list which represents the reverse of the rear of the queue, of length <code>len_rear</code>. Furthermore, it is assured that <code>|front| ≤ 2|rear|+1</code> and <code>|rear| ≤ 2|front|+1</code> - intuitively, it means that both the front and the rear contains between a third minus one and two thirds plus one of the elements. Finally, <code>tail_front</code> and <code>tail_rear</code> are tails of <code>front</code> and of <code>rear</code>, they allow scheduling the moment where some lazy operations are forced. Note that, when a double-ended queue contains <code>n</code> elements in the front list and <code>n</code> elements in the rear list, then the inequality invariant remains satisfied after <code>i</code> insertions and <code>d</code> deletions when <code>(i+d) &leq; n/2</code>. That is, at most <code>n/2</code> operations can happen between each rebalancing.

Let us first give an implementation of the various operations that affect the front of the deque - cons, head and tail. Those implementations do not necessarily respect the invariant. In a second time we'll explain how to modify a deque which does not satisfy the invariant into one which satisfies it. However, they use the invariant, in that if the front is empty then the rear has at most one element. The operations affecting the rear of the list are defined similarly by symmetry. 

<syntaxhighlight lang="sml">
empty = (0, NIL, NIL, 0, NIL, NIL)
fun insert'(x, (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  (len_front+1, CONS(x, front), drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun head((_, CONS(h, _), _, _, _, _)) = h
fun head((_, NIL, _, _, CONS(h, NIL), _)) = h
fun tail'((len_front, CONS(head_front, front), tail_front, len_rear, rear, tail_rear)) =
  (len_front - 1, front, drop(2, tail_front), len_rear, rear, drop(2, tail_rear))
fun tail'((_, NIL, _, _, CONS(h, NIL), _)) = empty  
</syntaxhighlight>

It remains to explain how to define a method <code>balance</code> that rebalance the deque if <code>insert'</code> or <code>tail</code> broke the invariant. The method <code>insert</code> and <code>tail</code> can be defined by first applying <code>insert'</code> and <code>tail'</code> and then applying <code>balance</code>.

<syntaxhighlight lang="sml">
fun balance(q as (len_front, front, tail_front, len_rear, rear, tail_rear)) =
  let floor_half_len = (len_front + len_rear) / 2 in
  let ceil_half_len = len_front + len_rear - floor_half_len in
  if len_front > 2*len_rear+1 then
    let val front' = take(ceil_half_len, front)
        val rear' = rotateDrop(rear, floor_half_len, front)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else if len_front > 2*len_rear+1 then
    let val rear' = take(floor_half_len, rear)
        val front' = rotateDrop(front, ceil_half_len, rear)
    in (ceil_half_len, front', front', floor_half_len, rear', rear')
  else q
</syntaxhighlight>
where <code>rotateDrop(front, i, rear))</code> return the concatenation of <code>front</code> and of <code>drop(i, rear)</code>. That is<code>front' = rotateDrop(front, ceil_half_len, rear)</code> put into <code>front'</code> the content of <code>front</code> and the  content of <code>rear</code> that is not already in <code>rear'</code>. Since dropping <code>n</code> elements takes <math>O(n)</math> time, we use laziness to ensure that elements are dropped two by two, with two drops being done during each <code>tail'</code> and each <code>insert'</code> operation. 

<syntaxhighlight lang="sml">
fun rotateDrop(front, i, rear) =
  if i < 2 then rotateRev(front, drop(i, rear), NIL)
  else let CONS(x, front') = front in
    CONS(x, rotateDrop(front', j-2, drop(2, rear)))
</syntaxhighlight>
where <code>rotateRev(front, middle, rear)</code> is a function that returns the front, followed by the middle reversed, followed by the rear. This function is also defined using laziness to ensure that it can be computed step by step, with one step executed during each <code>insert'</code> and <code>tail'</code> and taking a constant time. This function uses the invariant that <code>|rear|-2|front|</code> is 2 or 3. 

<syntaxhighlight lang="sml">
fun rotateRev(NIL, rear, a) =
  reverse(rear)++a
fun rotateRev(CONS(x, front), rear, a) =
  CONS(x, rotateRev(front, drop(2, rear), reverse(take(2, rear))++a))
</syntaxhighlight>
where <code>++</code> is the function concatenating two lists.

==== Implementation without laziness ====
Note that, without the lazy part of the implementation, this would be a non-persistent implementation of queue in {{math|''O''(1)}} [[amortized analysis|amortized time]]. In this case, the lists <code>tail_front</code> and <code>tail_rear</code> could be removed from the representation of the double-ended queue.