stack_as_array.ml:

---------------------------------------------------------------------------

type nat = int ;;

type element = string ;;

let (max_height : nat) = 10 ;;

type stack = {contents : element array ; mutable height : nat} ;;

exception Stack_full ;;
exception Stack_empty ;;

let bottom () = 
  let dummy_element = "" in 
  {contents = Array.create max_height dummy_element ;
   height = 0} ;;

let is_empty s =
  height s = 0 ;;

let height s =
  s.height  ;;

let top s =
  let ht = s.height in
  if ht = 0 
  then raise Stack_empty
  else s.contents.(ht - 1) ;;

let push e s =
  let ht = s.height in
  if ht = max_height 
  then raise Stack_full
  else
    begin
      s.contents.(ht) <- e ;
      s.height <- ht + 1 
    end ;;

let pop s = 
  let ht = s.height in
  if ht = 0 
  then raise Stack_empty
  else s.height <- ht - 1 ;;

===========================================================================

OCaml session

---------------------------------------------------------------------------

wmfarmer% ocaml
        Objective Caml version 3.08.0

# # use "stack_as_array.ml" ;;
Cannot find file stack_as_array.ml.
# # use "stack_as_array.ml" ;;
type nat = int
type element = string
val max_height : nat = 10
type stack = { contents : element array; mutable height : nat; }
exception Stack_full
exception Stack_empty
val bottom : unit -> stack = <fun>
val height : stack -> nat = <fun>
val top : stack -> element = <fun>
val pop : stack -> unit = <fun>
# let s = bottom () ;;
val s : stack =
  {contents = [|""; ""; ""; ""; ""; ""; ""; ""; ""; ""|]; height = 0}
# pop s ;;
Exception: Stack_empty.
# let push e s =
  let ht = s.height in
  if ht = max_height 
  then raise Stack_full
  else
    begin
    s.contents.(ht) <- e ;
    s.height <- ht + 1 
    end ;;
                val push : element -> stack -> unit = <fun>
# push "a" s ;;
- : unit = ()
# s ;;
- : stack =
{contents = [|"a"; ""; ""; ""; ""; ""; ""; ""; ""; ""|]; height = 1}
# push "a" s ;;
- : unit = ()
# push "a" s ;;
- : unit = ()
# push "a" s ;;
- : unit = ()
# push "b" s ;;
- : unit = ()
# push "b" s ;;
- : unit = ()
# push "b" s ;;
- : unit = ()
# push "b" s ;;
- : unit = ()
# s ;;
- : stack =
{contents = [|"a"; "a"; "a"; "a"; "b"; "b"; "b"; "b"; ""; ""|]; height = 8}
# push "c" s ;;
- : unit = ()
# push "c" s ;;
- : unit = ()
# push "c" s ;;
Exception: Stack_full.
# s ;;
- : stack =
{contents = [|"a"; "a"; "a"; "a"; "b"; "b"; "b"; "b"; "c"; "c"|];
 height = 10}
# pop s ;;
- : unit = ()
# s ;;
- : stack =
{contents = [|"a"; "a"; "a"; "a"; "b"; "b"; "b"; "b"; "c"; "c"|]; height = 9}
# pop s ;;
- : unit = ()
# pop s ;;
- : unit = ()
# pop s ;;
- : unit = ()
# pop s ;;
- : unit = ()
# pop s ;;
- : unit = ()
# s ;;
- : stack =
{contents = [|"a"; "a"; "a"; "a"; "b"; "b"; "b"; "b"; "c"; "c"|]; height = 4}
# push "d" s ;;
- : unit = ()
# s ;;
- : stack =
{contents = [|"a"; "a"; "a"; "a"; "d"; "b"; "b"; "b"; "c"; "c"|]; height = 5}
# let is_empty s =
  s.height = 0 ;;
  val is_empty : stack -> bool = <fun>
# is_empty s ;;
- : bool = false
# is_empty (bottom ()) ;;
- : bool = true
#