(* Signature for queues.  This should be implemented in two structures:
 *
 *    ListQueue      : QUEUE
 *    AmortizedQueue : QUEUE
 *
 * In the former case, queues are represented as lists, and you merely
 * have to implement get and set.
 *
 * In the latter case, you should design a better representation such
 * that both get and set operate in amortized constant time.

 * Clients of QUEUE should behave the same regardless of which
 * representation they use.
 *)
signature QUEUE =
sig
  (* Raised by _get_ if the given queue is empty. *)
  exception Empty

  (* The type of a queue of 'a. *)
  type 'a queue

  (* The empty queue. *)
  val empty : 'a queue

  (* Enqueue a value, returning a new queue. *)
  val put   : 'a queue * 'a -> 'a queue

  (* Given a queue, return the first value in the queue and a new
   * queue with that value removed. *)
  val get   : 'a queue -> 'a * 'a queue
end