queue.ml

type 'a t = {
  front: 'a list;
  back : 'a list
}
exception Empty

let empty = {front = []; back = []}
let is_empty x = x = empty

let balance =
  function
      {front=[]; back=back} ->
	{front=List.rev back; back=[]}
    | q ->
	q

let add elt queue = balance {queue with back = elt::queue.back}

let take queue =
  match queue.front with
      x::xs ->
	x,balance {queue with front=xs}
    | [] ->
	raise Empty

let peek queue =
  match queue.front with
      x::_ ->
	x
    | [] ->
	raise Empty

let length {front=front; back=back} =
  List.length front + List.length back

let iter f {front=front; back=back} =
  List.iter f front;
  ignore (List.rev_map f back)

let fold f init {front=front; back=back} =
  let accum =
    List.fold_left f init front in
    List.fold_right (fun a b -> f b a) back accum

(* alias *)
let push = add
let pop = take
let top = peek

queue.mli

type 'a t
exception Empty

val empty : 'a t
val is_empty : 'a t -> bool
val add : 'a -> 'a t -> 'a t
val take : 'a t -> 'a * 'a t
val peek : 'a t -> 'a
val length : 'a t -> int
val iter : ('a -> unit) -> 'a t -> unit
val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

(* alias *)
val push : 'a -> 'a t -> 'a t
val pop : 'a t -> 'a * 'a t
val top : 'a t -> 'a