Functional Queues

Queue ADT

A queue is a sequence with First-In-First-Out (FIFO) discipline. The item next to be removed is the one that has been in the queue the longest.

Operation	Description
qempty	The empty queue
qnull q	Test whether q is empty
qhd q	Return the element at the head
deq q	Discard the element at the head
enq q x	Add x to the tail

The two-list representation

Represent the queue x₁x₂…xₘyₙ…y₁ by a pair of lists:

([x₁; x₂; ...; xₘ], [y₁; y₂; ...; yₙ])

• The front list is stored in order: the head of this list is the head of the queue.
• The rear list is stored in reverse order: the head of this list is the tail of the queue.

Operations

type 'a queue = Q of 'a list * 'a list

Enqueue adds to the rear list using :: (O(1)):

let enq (Q (hds, tls)) x = norm (Q (hds, x :: tls))

Dequeue removes from the front list using pattern-matching (O(1) normally):

let deq = function
  | Q (x :: hds, tls) -> norm (Q (hds, tls))
  | _ -> raise Empty

Head reads from the front list:

let qhd = function
  | Q (x :: _, _) -> x
  | _ -> raise Empty

Normalisation

The function norm ensures the front list is never empty unless the queue is empty:

let norm = function
  | Q ([], tls) -> Q (List.rev tls, [])
  | q -> q

When the front list becomes empty, norm reverses the rear list, making it the new front list. This reversal takes O(n) time for a rear list of length n, but as we shall see, the amortised cost per operation is O(1).