mutable stack with queue implemented as two stacks

mutable_stack_queue.ml

(** Mutable stack and queue. 
 ** Queue implemented as two stacks. This is all the rage. *)

module type STACK = sig
  type 'a t

  val create : unit -> 'a t
  
  val peek : 'a t -> 'a option

  val push : 'a -> 'a t -> unit

  val pop : 'a t -> 'a option

  val to_list : 'a t -> 'a list

  val is_empty : 'a t -> bool
end


module Stack : STACK = struct
  type 'a t = ('a list) ref

  let create () = ref []
  
  let peek s = match !s with
    | [] -> None
    | x :: _ -> Some x

  let push x s = s := x :: !s

  let pop s = match !s with
    | [] -> None
    | x :: xs -> s := xs; Some x

  let to_list s = !s

  let is_empty s = match !s with
    | [] -> true
    | otherwise -> false
end


module type QUEUE = sig
  type 'a t

  val create : unit -> 'a t
  
  val peek : 'a t -> 'a option

  val enqueue : 'a -> 'a t -> unit

  val dequeue : 'a t -> 'a option

  val to_list : 'a t -> 'a list
end


module Queue : QUEUE = struct
  module S = Stack
  
  type 'a t = { inbox : 'a S.t;
               outbox : 'a S.t }

  let create () = { inbox = S.create ();
                    outbox = S.create () }

  (* "reverse" the stack by popping from inbox and pushing to outbox *)
  let rec transfer q = match S.pop q.inbox with
    | None -> ()
    | Some x -> S.push x q.outbox; transfer q
  
  let peek q =
    if S.is_empty q.outbox then transfer q;
    S.top q.outbox 
  
  let enqueue x q = S.push x q.inbox

  let rec dequeue q =
    if S.is_empty q.outbox then transfer q;
    S.pop q.outbox

  let to_list q = S.to_list q.inbox @ S.to_list q.outbox
  
end