如何使用 LinkedList 样式和就地修改实现堆栈？

Question

在 中Java，很容易实现一种linkedlist风格stack。

我们只是创建了一个内部类Item，它有两个属性：value和next。

然后我们主要总是第一个项目。

然后什么时候push，我们创建一个 newItem并让它下一个指向当前first item然后让当前first item成为新的item。

可以对pop.

---

但是我怎么能在 OCaml 中做到这一点呢？特别是当我们想要in place modification( mutable)?

我说mutable是因为正常pop只弹出值，而不是新堆栈。

Answer 1

OCaml 是一种多范式语言。使用可变数据一点也不困难。但学习没有它（恕我直言）确实值得努力。好处出奇的大，成本出奇的小。

尽管如此，这里还是一个可变堆栈类型的快速草图。

type 'a stack = { mutable stack: 'a list }

let new_stack () = { stack = [] }

let is_empty stack = stack.stack = []

let push x stack = stack.stack <- x :: stack.stack

let pop stack =
    match stack.stack with
    | [] -> raise Not_found
    | x :: xs -> stack.stack <- xs; x

（您也可以从定义开始type 'a stack = 'a list ref，但此版本展示了如何拥有自己的可变记录字段。）