fork download
copy 
  1. exception Empty_stack
  2.  
  3. class ['a] list_stack =
  4.   object
  5.     val mutable items : 'a list = []
  6.  
  7.     method push (x : 'a) =
  8.       items <- x :: items
  9.  
  10.     method pop : 'a =
  11.       match items with
  12.       | [] -> raise Empty_stack
  13.       | head :: rest ->
  14.         begin
  15.           items <- rest ;
  16.           head
  17.         end
  18.  
  19.   end
  20.  
  21. class ['a] array_stack =
  22.   let grow_factor = 1.6
  23.   and init_capacity = 10 in
  24.  
  25.   object (self)
  26.     val mutable items : 'a option array = Array.make init_capacity None
  27.     val mutable count = 0
  28.  
  29.     method push (x : 'a) =
  30.       self#ensure_cap ;
  31.       Array.set items count (Some x) ;
  32.       count <- count + 1
  33.  
  34.     method pop : 'a =
  35.       if count = 0
  36.       then raise Empty_stack
  37.       else
  38.         count <- count - 1 ;
  39.         match Array.get items count with
  40.         | None   -> raise (Failure "unreachable")
  41.         | Some x ->
  42.           begin
  43.             Array.set items count None ;
  44.             x
  45.           end
  46.  
  47.     method private ensure_cap =
  48.       if count < Array.length items
  49.       then ()
  50.       else items <- self#grow
  51.  
  52.     method private grow =
  53.       let old_cap = Array.length items in
  54.       let new_cap = int_of_float (grow_factor *. float_of_int old_cap) in
  55.       let dst = Array.make new_cap None in
  56.       Array.blit items 0 dst 0 old_cap ;
  57.       dst
  58.  
  59.   end
  60.  
  61. type 'a stack =
  62.   < push : 'a -> unit
  63.   ; pop  : 'a
  64.   >
  65.  
  66. let main (make_stack : unit -> 'a stack) =
  67.   let s = make_stack () in
  68.   for i = 1 to 3 do
  69.     s#push i
  70.   done ;
  71.   for i = 1 to 3 do
  72.     s#pop |> Printf.printf "%d "
  73.   done ;
  74.   Printf.printf "\n"
  75.  
  76. let _ =
  77.   main (fun () -> new list_stack) ;
  78.   main (fun () -> new array_stack)
  79.  
Success #stdin #stdout 0.01s 5460KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
3 2 1 
3 2 1
https://ideone.com/tgCMGc
language:
OCaml (ocamlopt 4.05.0)
created:
2 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!