structure MyQueue =
struct
   datatype 'a queue = Q of 'a list * 'a list
   val emptyQueue = Q ([],[])
   fun isEmptyQueue (Q ([],[])) = true
     | isEmptyQueue (Q (xs,ys)) = false
   fun head (Q (x::xs,ys)) = x
   fun normalise (Q ([],ys)) = Q (rev ys,[])
     | normalise q = q
   fun enqueue v (Q (xs,ys)) = normalise (Q (xs,v::ys))
   fun dequeue (Q (x::xs,ys)) = normalise (Q (xs,ys))
   fun showQueue (Q (xs,ys)) = xs @ (rev ys)
end ;

signature sigQueue =
sig
   type 'a queue
   val emptyQueue   : ''a queue
   val isEmptyQueue : ''a queue -> bool
   val head         : ''a queue -> ''a
   val enqueue      : ''a -> ''a queue -> ''a queue
   val dequeue      : ''a queue -> ''a queue
   val showQueue    : ''a queue -> ''a list
end ;

structure Queue1 : sigQueue =
struct
   datatype 'a queue = Q of 'a list * 'a list
   val emptyQueue = Q ([],[])
   fun isEmptyQueue (Q ([],[])) = true
     | isEmptyQueue (Q (xs,ys)) = false
   fun head (Q (x::xs,ys)) = x
   fun normalise (Q ([],ys)) = Q (rev ys,[])
     | normalise q = q
   fun enqueue v (Q (xs,ys)) = normalise (Q (xs,v::ys))
   fun dequeue (Q (x::xs,ys)) = normalise (Q (xs,ys))
   fun showQueue (Q (xs,ys)) = xs @ (rev ys)
end ;

structure Queue2 :> sigQueue =
struct
   datatype 'a queue = Q of 'a list * 'a list
   val emptyQueue = Q ([],[])
   fun isEmptyQueue (Q ([],[])) = true
     | isEmptyQueue (Q (xs,ys)) = false
   fun head (Q (x::xs,ys)) = x
   fun normalise (Q ([],ys)) = Q (rev ys,[])
     | normalise q = q
   fun enqueue v (Q (xs,ys)) = normalise (Q (xs,v::ys))
   fun dequeue (Q (x::xs,ys)) = normalise (Q (xs,ys))
   fun showQueue (Q (xs,ys)) = xs @ (rev ys)
end ;

signature sigQueueEq =
sig
   eqtype element
   type queue
   val emptyQueue   : queue
   val isEmptyQueue : queue -> bool
   val head         : queue -> element
   val enqueue      : element -> queue -> queue
   val dequeue      : queue -> queue
   val showQueue    : queue -> element list
end ;

functor QueueFctr (s : sig
			 eqtype element
		      end) :> sigQueueEq where type element = s.element   =
struct
   type element = s.element
   datatype queue = Q of s.element list * s.element list
   val emptyQueue = Q ([],[])
   fun isEmptyQueue (Q ([],[])) = true
     | isEmptyQueue (Q (xs,ys)) = false
   fun head (Q (x::xs,ys)) = x
   fun normalise (Q ([],ys)) = Q (rev ys,[])
     | normalise q = q
   fun enqueue v (Q (xs,ys)) = normalise (Q (xs,v::ys))
   fun dequeue (Q (x::xs,ys)) = normalise (Q (xs,ys))
   fun showQueue (Q (xs,ys)) = xs @ (rev ys)
end ;

structure IntQueue =
   QueueFctr (type element = int) ;