module Queue_fun: QUEUE_FUN =
struct
    type 'a t = 'a list
    exception Empty of string

    let empty () = []
    let enqueue (v, lst) = lst@[v]
    let dequeue = function
        [] -> raise (Empty "dequeue")
      | _::xs -> xs;;
    let first = function
        [] -> raise (Empty "first")
      | x::_ -> x;;
    let isEmpty lst = lst = []
end;;

module Queue_fun2: QUEUE_FUN =
struct
    type 'a t = 'a list * 'a list
    exception Empty of string

    let normalize = function
        ([], q) -> (List.rev q, [])
      | q -> q

    let empty () = ([], [])
    let enqueue (v,(x1, lst)) = normalize (x1, v::lst)
    let dequeue = function
        (_::xs, q) -> normalize (xs, q)
      | _ -> raise (Empty "dequeue")
    let first = function
        (x::_, _) -> x
      | _ -> raise (Empty "first")
    let isEmpty lst = lst = ([], [])
end;;


--------------------------