實現在F＃

Question

我試圖實現在F＃隊列中的隊列類型到目前爲止，這是我，但我認爲它的作用更像是一個堆棧：

type 'a queue = NL| Que of 'a * 'a queue;; 

let enque m = function 
    |NL -> Que(m, NL) 
    |Que(x, xs) -> Que(m, Que(x, xs));; 

let rec peek = function 
    |NL -> failwith "queue is empty" 
    |Que(x, xs) -> x;; 

let rec deque = function 
    |NL -> failwith "queue is empty" 
    |Que(x, xs) -> xs;; 

let rec build = function 
    | [] -> NL 
    | x::xs -> enque x (build xs);; 

的操作是，除了做工精細enque，我想這樣做，它會在隊列的後面添加一個新元素，而不是前面。

Answer 1

目前你正在把它放在前面;如果你想在你的隊列的末尾排隊進步一路爲此，然後把你的價值：

let rec enque m = function 
    NL   -> Que (m, NL) 
| Que (x, xs) -> Que (x, enque m xs) // Note : not tail-rec 

Answer 2

功能性隊列中的典型做法是有兩個列表，從而導致攤銷 O（1）access：

type queue<'a> = 
    | Queue of 'a list * 'a list 

let empty = Queue([], []) 

let enqueue q e = 
    match q with 
    | Queue(fs, bs) -> Queue(e :: fs, bs) 

let dequeue q = 
    match q with 
    | Queue([], []) -> failwith "Empty queue!" 
    | Queue(fs, b :: bs) -> b, Queue(fs, bs) 
    | Queue(fs, []) -> 
     let bs = List.rev fs 
     bs.Head, Queue([], bs.Tail)