(* Chris Okasaki
   School of Computer Science
   Carnegie Mellon University
   Pittsburgh, PA 15213
   cokasaki@cs.cmu.edu *)

functor StandardQueue () : QUEUE =
    (* Standard implementation of queues as a pair of lists.        *)
    (*                                                              *)
    (* O(n) worst-case performance, but O(1) amortized performance  *)
    (* provided queues are used in a "single-threaded" manner,      *)
    (* i.e. all operations refer to the most recent queue, never an *)
    (* earlier one.                                                 *)
struct
    type 'a Queue = 'a list * 'a list

    exception Empty

    val empty = ([], [])

    fun isempty ([],[]) = true
      | isempty _ = false

    fun size (front,rear) = length front + length rear

    fun insert (x, (front,rear)) = (front, x :: rear)

    fun insertf (x, (front,rear)) = (x :: front, rear)

    fun remove (x::front,rear) = (x, (front, rear))
      | remove ([],rear) =
          case rev rear of
              [] => raise Empty
            | x::front' => (x, (front', []))
end