datatype 'a N = E | N of {l:'a N ref, v: 'a, r:'a N ref} type 'a Q = 'a N ref fun mkQ () = ref E fun lt (N {l,...}) = l and rt (N {r,...}) = r fun enq x q = case !q of N {l,v,r} => let val new = N {l = ref (!q), v = x, r = ref (!r)} in lt(!r) := new; r := new end | E => let val n = N {l = ref E, v = x, r = ref E} in lt n := !q; rt (!q) := n; rt n := !(rt (!q)); lt (!(rt (!q))) := n; q := n end; exception Deq; fun deq q = case !q of E => raise Deq | N {l, v, r} => if rt(!r) = r then (q := E; v) else (q := !l; lt(!l) := !r; lt(!r) := !l; v);