Queue

Queue module: functional double-ended queue (deque) using two lists.

Representation: Queue(front, back) The sequence from front to back is: front ++ reverse(back)

This gives amortised O(1) push and pop at both ends: push_front / push_back O(1) worst case pop_front / pop_back O(1) amortised (O(n) worst case on rebalance) peek_front / peek_back O(1) amortised size O(n) to_list O(n)

Rebalancing: when the "consume" end is empty we reverse the other list.

Types

typeQueueQueue(a) = Queue(List(a), List(a))#

Functions

fnemptyempty()#

Returns an empty deque.

fnis_emptyis_empty(q)#

Returns true if the deque contains no elements.

fnpush_backpush_back(q, x)#

Add an element to the back of the deque.

fnpush_frontpush_front(q, x)#

Add an element to the front of the deque.

fnpop_frontpop_front(q)#

Remove and return the front element. Returns Some((element, new_queue)) if non-empty, or None if empty.

fnpop_backpop_back(q)#

Remove and return the back element. Returns Some((element, new_queue)) if non-empty, or None if empty.

fnpeek_frontpeek_front(q)#

Return the front element without removing it, or None if empty.

fnpeek_backpeek_back(q)#

Return the back element without removing it, or None if empty.

fnsizesize(q)#

Return the number of elements in the deque. O(n).

fnto_listto_list(q)#

Convert the deque to a list ordered from front to back.

fnfrom_listfrom_list(xs)#

Build a deque from a list. The first element of the list becomes the front.