signature QUEUE =
sig
    type 'a T                        (* type of queues *)

    exception EMPTY                  (* raised by pop(empty) or first(empty) *)

    val empty   : 'a T               (* the empty queue *)
    val isempty : 'a T -> bool       (* return true if queue is empty *)

    val inject  : 'a * 'a T -> 'a T  (* add element to rear of queue *)

    val pop     : 'a T -> 'a T       (* remove front element of queue *)
    val first   : 'a T -> 'a         (* return front element of queue *)

    val size    : 'a T -> int        (* return number of elements in queue *)
end

structure Queue : QUEUE =
    (* The following implementation of queues supports all operations    *)
    (* in constant amortized time.  Implementations of purely functional *)
    (* queues that support all operations in constant worst-case time    *)
    (* can be found in                                                   *)
    (*     Robert Hood and Robert Melville                               *)
    (*     "Real-time queue operations in pure Lisp"                     *)
    (*     Information Processing Letters 13(2):50-53, Nov 1981          *)
    (* or                                                                *)
    (*     Chris Okasaki                                                 *)
    (*     "Simple and efficient purely functional queues and deques"    *)
    (*     Journal of Functional Programming, to appear Oct 1995.        *)
    (*     http://foxnet.cs.cmu.edu/people/cokasaki/papers.html          *)
struct

    type 'a T = int * 'a Stream.T * int * 'a Stream.T
      (* invariants for (n,front,m,rear):            *)
      (*   n = length front, m = length rear, n >= m *)

      (* NOTE: at some cost in clarity, rear may be more efficiently *)
      (*       represented as a regular list instead of a stream.    *)

    exception EMPTY

    fun check (q as (n,front,m,rear)) =
          (* enforce invariant that n >= m *)
          if n >= m then q
          else (n+m,Stream.append (front,Stream.reverse rear),
                0,Stream.empty)

    val empty = (0,Stream.empty,0,Stream.empty)
    fun isempty (n,front,m,rear) = (n = 0)

    fun inject (x,(n,front,m,rear)) = check (n,front,m+1,Stream.cons (x,rear))

    fun first (0,front,m,rear) = raise EMPTY
      | first (n,front,m,rear) = Stream.head front

    fun pop (0,front,m,rear) = raise EMPTY
      | pop (n,front,m,rear) = check (n-1,Stream.tail front,m,rear)

    fun size (n,front,m,rear) = n+m : int

(***** 
This data structure also supports an efficient push:
    fun push (x,(n,front,m,back)) = (n+1,Stream.cons(x,front),m,back)
*****)

end