实现在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)