signature QUEUE = sig type 'a t (* type of queues *) exception E (* for errors in hd and deq *) val empty: 'a t (* the empty queue *) val null: 'a t -> bool (* test for empty queue *) val enq: 'a -> 'a t -> 'a t (* add to end *) val deq: 'a t -> 'a t (* remove from front *) val hd: 'a t -> 'a (* return the front element *) end ; structure Queue : QUEUE = struct type 'a t = 'a list * 'a list ; exception E ; val empty = ([],[]) ; fun null( ([],[]) ) = true | null _ = false ; fun enq x ([],_) = ( [x] , [] ) | enq x (front,back) = ( front , x::back ) ; fun deq( (_::[],back) ) = ( rev back , [] ) | deq( (_::rest,back) ) = ( rest , back ) | deq( _ ) = empty ; fun hd( (head::rest,_) ) = head | hd( ([],_) ) = raise E ; end ; fun buildq F = foldl ( fn( f , q ) => f q ) Queue.empty F ; val q = buildq [Queue.enq 0, Queue.enq 1, Queue.enq 2, Queue.enq 3 ] ; open Queue ; val q1 = enq 0 empty ; val q2 = enq 1 q1 ; val q3 = enq 2 q2 ; val q4 = enq 3 q3 ; val q5 = enq 4 q4 ; val q6 = enq 5 q5 ; val q7 = deq q6 ; val q8 = deq q7 ; val q9 = deq q8 ; val q10 = deq q9 ; val q11 = deq q10 ; val q12 = deq q11 ; val q13 = deq q12 ; val q14 = deq q13 ; val q15 = enq 6 q14 ; val q16 = enq 7 q15 ; val q17 = deq q16 ;