module Queue =
    (*
    //EXAMPLES

    let q =
      List.fold (fun queue item -> queue|> Queue.enqueue item) Queue.empty [1..10]

    Queue.size q // 10

    let first, q2 = Queue.dequeue q

    Queue.size q2 // 9
    *)

    type Queue<'a> = Queue of 'a list * 'a list

    let empty = Queue([], [])

    let enqueue item = function
      | Queue(front, back) ->
        Queue(front, item :: back)

    let rec dequeue = function
      | Queue([], []) -> failwith "Empty queue"
      | Queue([], back) -> Queue(back |> List.rev, []) |> dequeue
      | Queue(front, back) -> front|> List.head, Queue(front|> List.tail, back)

    let size = function
      | Queue(front, back) -> front.Length + back.Length