module Queue =
  struct
    exception Empty_queue
	
    type 'element queue =
	{ front : 'element list;
	  rear  : 'element list;
	} 
	  
    let empty = { front = []; rear = []; }
	
    let is_empty { front = front } = front = []

    let reverse list =
      let rec rev list result =
	match list with
	  [] -> result
	| head::tail ->
	    rev tail (head::result)
      in
      rev list []
	
    let snoc queue element =
      match queue with
	{ front = []; } ->
	  { front = [element]; rear = []; }
      | { front = front; rear = rear; } ->
	  { front = front; rear = element :: rear; }
	    
    let head queue =
      match queue with
	{ front = []; } ->
	  raise Empty_queue
      |	{ front = first :: _; } ->
	  first
    let tail queue =
      match queue with
	{ front = []; } -> raise Empty_queue
      | { front = [element]; rear = rear; } ->
	  { front = reverse rear; rear = []; }
      | { front = first :: rest; rear = rear; } ->
	  { front = rest; rear = rear; }
  end

let q1 = Queue.snoc Queue.empty 5

let q2 = Queue.snoc q1 3

let e1 = Queue.head q1

let e2 = Queue.head q2

let q3 = Queue.tail q2

let e3 = Queue.head q3

let q4 = Queue.tail q3

module type QUEUE =
    sig
      exception Empty_queue
      type 'a queue (* abstract *)
      val empty : 'a queue
      val is_empty : 'a queue -> bool
      val snoc : 'a queue -> 'a -> 'a queue
      val head : 'a queue -> 'a
      val tail : 'a queue -> 'a queue
    end

module AbstractQueue = ( Queue : QUEUE )

let q1 = AbstractQueue.snoc AbstractQueue.empty 5

let q2 = AbstractQueue.snoc q1 3

let e1 = AbstractQueue.head q1

let e2 = AbstractQueue.head q2

let q3 = AbstractQueue.tail q2

let e3 = AbstractQueue.head q3

let q4 = AbstractQueue.tail q3