signature Stack =
  sig
    type 'a stack
    exception Empty
    val empty : 'a stack
    val push : 'a stack -> 'a -> 'a stack
    val pop : 'a stack -> ('a * 'a stack)
  end


structure List_Stack :> Stack =
  struct
    type 'a stack = 'a list
    exception Empty
    val empty = []
    fun push s a = a::s
    fun pop s = case s of
                  [] => raise Empty
                 | x::xs => (x, xs)
  end

structure Cons_Stack :> Stack =
  struct
    datatype 'a stack = Nil | Cons of 'a * 'a stack
    exception Empty
    val empty = Nil
    fun push s a = Cons (a, s)
    fun pop s = case s of
                    Nil => raise Empty
                  | Cons (x, xs) => (x, xs)
  end


signature Queue =
  sig
    type 'a queue
    exception Empty
    val empty : 'a queue
    val enqueue : 'a queue -> 'a -> 'a queue
    val dequeue : 'a queue -> ('a * 'a queue)
  end

functor Double_Stack_Queue_Fn (myStack : Stack) :> Queue =
  struct
    val empty = (myStack.empty, myStack.empty)
    fun enqueue (f, s) e = (push f e, s)
    fun dequeue (f, s) = case s of
                             [] => if f = myStack.empty then raise Empty else dequeue (empty, rev f)
                           | x::xs => (x, (f, xs))
  end

structure Double_List_Stack_Queue = Double_Stack_Queue_Fn (List_Stack);