push x d adds the element x to the end of the deque d. The average cost is constant. Worst-case running time is O(log N), which happens once in every N operations.

pop q returns None if q is the empty deque, otherwise it returns Some (x, d') where x is the element on the end of the deque, and q' is the remainder of q with the element x removed. The average cost is constant. Worst-case running time is O(log N), which happens once in every N operations.

head q returns the element at the end of the deque q. Raises Not_found if the deque is empty.

tail q is discards the element at the end of the deque q. Raises Not_found if the deque is empty.

Use of_seq s to make a deque by consuming all the elements in the sequence s. The head of the deque is the first element consumed and the tail is the final element consumed.

to_seq q returns a sequence that produces the elements of the deque in order from head to tail by making successive calls to pop q.