A queue is represented by a pair of lists, with the intended meaning the the first list is the first half of the queue and the second list is the second half of the queue in reversed order. That is, given a queue (xs, ys), the "content" of the queue is xs ++ reverse ys. This representation allows reasonably efficient access to both the head and the tail of a queue.

The empty queue.

Test whether a queue is empty.

Enqueue an element at the end of the queue.

Dequeue the first element of the queue. The result pair consists of this element together with the remaining queue.