module type QUEUE_FUN =
    sig
        type 'a t
        exception Empty of string
        val empty: unit -> 'a t
        val enqueue: 'a * 'a t -> 'a t
        val dequeue: 'a t -> 'a t
        val first: 'a t -> 'a
        val isEmpty: 'a t -> bool
    end;;

module PairQueue : QUEUE_FUN =
  struct
        type 'a t = 'a list * 'a list

    exception Empty of string

    let empty() = ([],[])

        let enqueue (element, queue) =
            match queue with
            | ([], []) -> ([element], [])
            | (l1, l2) -> (l1, element::l2)

        let dequeue queue =
            match queue with
            | (_::[], l2) -> (List.rev l2, [])
            | (_::t, l2) -> (t, l2)
            | ([], []) -> ([], [])

        let first = function
            | (h1::_, _) -> h1
            | ([], []) -> raise (Empty "module PairQueue: first")


        let isEmpty queue =
            queue = ([], [])
    end;;

let x = PairQueue.empty();;
PairQueue.dequeue(PairQueue.enqueue(2, PairQueue.enqueue(4,x))) = PairQueue.enqueue(2,x);;