module type QUEUE_FUN =
sig
 type 'a q
 exception Empty of string
 val empty: unit -> 'a q
 val enqueue: 'a * 'a q -> 'a q
 val dequeue: 'a q -> 'a q
 val top: 'a q -> 'a
 val get:  int * 'a q  -> 'a
 val tolist: 'a q -> 'a list
end


module QUEUE : QUEUE_FUN =
struct
     type 'a q = EmptyQueue | Enqueue of 'a * 'a q
    exception Empty of string
     let  empty() = EmptyQueue

     let rec enqueue(elem, queue) =
        match queue with
        (*Enqueue(elem, Enqueue(next, nextque)) -> Enqueue(elem, enqueue(next, nextque))*)
        (*Enqueue(e, Enqueue(e2, q2)) -> Enqueue(e, enqueue(e2, q2))*)
     (* EmptyQueue -> Enqueue(elem, EmptyQueue)*)

        |Enqueue(e, q) -> Enqueue(elem, enqueue(e, q))
        |EmptyQueue -> Enqueue(elem, EmptyQueue)



    let  dequeue(queue) =
        match queue with
        Enqueue(elem, q) -> q
        | EmptyQueue -> EmptyQueue

    let top queue =
    match queue with
    EmptyQueue -> raise (Empty "top : Pusta kolejka")
    |Enqueue(elem, _) -> elem

    let rec get (n, queue) =
    match (n, queue) with
    (0, Enqueue(elem, queue)) -> elem
    |(_, EmptyQueue) -> raise (Empty "get: poza zakresem")
    |(n, Enqueue(e, q)) -> get(n-1, q)

    let rec tolist queue =
    match queue with
    Enqueue(elem, queue) -> elem::tolist(queue)
    |EmptyQueue -> []
end
module Qq = QUEUE;;
(*let q = QUEUE.empty();;QUEUE.enqueue(1, QUEUE.enqueue(2, QUEUE.enqueue(3, QUEUE.empty())));;*)
(*let q = QUEUE.Enqueue(1, QUEUE.Enqueue(2, QUEUE.Enqueue(3, QUEUE.EmptyQueue)));;*)
let q = Qq.empty();;
let q = Qq.enqueue(3, q);;
let q = Qq.enqueue(2, q);;
 let q = Qq.enqueue(1, q);;


 Qq.get(1, q);;

let q = Qq.dequeue( q);;
 Qq.get(1, q);;
 Qq.tolist(q)