如何使用LinkedList樣式實現堆棧並進行修改？

Question

在Java中，很容易實現linkedlist風格的stack。

我們只需要創建一個內部類Item，它有兩個屬性：value和next。

那麼我們總是主要的第一項。

然後當push，我們創建了一個新的Item，讓它的下一個點到當前first item然後讓當前first item成爲新item。

與pop類似。

---

但我怎麼能在OCaml中做到這一點？特別是當我們想要in place modification（mutable）？

我說mutable，因爲一個正常的pop只彈出的價值，而不是新的堆棧。

Answer 1

OCaml是一種多範例語言。使用可變數據並不難。但如果沒有它（IMHO），學會去努力是非常值得的。這個好處驚人地好，而且成本驚人地小。

是的，因爲它可能是，這是一個可變堆棧類型的快速草圖。

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開始，但是這個版本展示瞭如何有自己的可變記錄字段。）

Answer 2

爲了補充傑弗裏的出色答卷，我想指出的是，在 這種情況下，很容易實現這兩個一個持久性接口和 一個可變接口的堆棧數據結構，因爲可變接口可以構建在持久性接口之上。

module Impl = struct 
    type 'a t = 'a list 
    let empty = [] 
    let is_empty = function [] -> true | _ -> false 
    let push x stack = x::stack 

    let pop = function 
    | [] -> raise Not_found 
    | x::xs -> (x,xs) 
end 

module PersistentStack : sig 
    type +'a t 
    val empty : 'a t 
    val is_empty : 'a t -> bool 
    val push : 'a -> 'a t -> 'a t 
    val pop : 'a t -> 'a * 'a t 
end = struct 
    include Impl 
end 

module MutableStack : sig 
    type 'a t 
    val new_stack : unit -> 'a t 
    val is_empty : 'a t -> bool 
    val push : 'a -> 'a t -> unit 
    val pop : 'a t -> 'a 
end = struct 
    type 'a t = 'a Impl.t ref 
    let new_stack() = ref Impl.empty 
    let is_empty stack = Impl.is_empty !stack 
    let push x stack = (stack := Impl.push x !stack) 
    let pop stack = 
    let (x, xs) = Impl.pop !stack in 
    stack := xs; 
    x 
end