module Queue: Queue非同步存取
對佇列進行非同步存取可能會導致佇列狀態無效。因此，對佇列的並行存取必須同步（例如使用 Mutex.t）。
type !'a t
包含 'a 型別元素的佇列型別。
exception Empty
當將 Queue.take 或 Queue.peek 應用於空佇列時會引發此例外。
val create : unit -> 'a t返回一個新的佇列，初始為空。
val add : 'a -> 'a t -> unitadd x q 將元素 x 加入佇列 q 的末尾。
val push : 'a -> 'a t -> unitpush 是 add 的同義詞。
val take : 'a t -> 'atake q 移除並返回佇列 q 的第一個元素，如果佇列為空，則引發 Queue.Empty 例外。
val take_opt : 'a t -> 'a optiontake_opt q 移除並返回佇列 q 的第一個元素，如果佇列為空，則返回 None。
val pop : 'a t -> 'apop 是 take 的同義詞。
val peek : 'a t -> 'apeek q 返回佇列 q 的第一個元素，但不從佇列中移除它，如果佇列為空，則引發 Queue.Empty 例外。
val peek_opt : 'a t -> 'a optionpeek_opt q 返回佇列 q 的第一個元素，但不從佇列中移除它，如果佇列為空，則返回 None。
val top : 'a t -> 'atop 是 peek 的同義詞。
val clear : 'a t -> unit從佇列中捨棄所有元素。
val copy : 'a t -> 'a t返回給定佇列的副本。
val is_empty : 'a t -> bool如果給定的佇列為空，則返回 true，否則返回 false。
val length : 'a t -> int返回佇列中的元素數量。
val iter : ('a -> unit) -> 'a t -> unititer f q 依次將 f 應用於 q 的所有元素，從最近加入的到最晚加入的。佇列本身保持不變。
val fold : ('acc -> 'a -> 'acc) -> 'acc -> 'a t -> 'accfold f accu q 等同於 List.fold_left f accu l，其中 l 是 q 的元素列表。佇列保持不變。
val transfer : 'a t -> 'a t -> unittransfer q1 q2 將 q1 的所有元素加入佇列 q2 的末尾，然後清除 q1。它等同於序列 iter (fun x -> add x q2) q1; clear q1，但在常數時間內執行。
val to_seq : 'a t -> 'a Seq.t以從前到後的順序迭代佇列。如果在迭代期間修改了佇列，則行為未指定。
val add_seq : 'a t -> 'a Seq.t -> unit將序列中的元素加入佇列末尾。
val of_seq : 'a Seq.t -> 'a t從序列建立佇列。
一個基本範例
# let q = Queue.create ()
val q : '_weak1 Queue.t = <abstr>
# Queue.push 1 q; Queue.push 2 q; Queue.push 3 q
- : unit = ()
# Queue.length q
- : int = 3
# Queue.pop q
- : int = 1
# Queue.pop q
- : int = 2
# Queue.pop q
- : int = 3
# Queue.pop q
Exception: Stdlib.Queue.Empty.
對於更詳細的範例，佇列的經典演算法應用是用於實現圖形的 BFS（廣度優先搜尋）。
type graph = {
edges: (int, int list) Hashtbl.t
}
(* Search in graph [g] using BFS, starting from node [start].
It returns the first node that satisfies [p], or [None] if
no node reachable from [start] satisfies [p].
*)
let search_for ~(g:graph) ~(start:int) (p:int -> bool) : int option =
let to_explore = Queue.create() in
let explored = Hashtbl.create 16 in
Queue.push start to_explore;
let rec loop () =
if Queue.is_empty to_explore then None
else
(* node to explore *)
let node = Queue.pop to_explore in
explore_node node
and explore_node node =
if not (Hashtbl.mem explored node) then (
if p node then Some node (* found *)
else (
Hashtbl.add explored node ();
let children =
Hashtbl.find_opt g.edges node
|> Option.value ~default:[]
in
List.iter (fun child -> Queue.push child to_explore) children;
loop()
)
) else loop()
in
loop()
(* a sample graph *)
let my_graph: graph =
let edges =
List.to_seq [
1, [2;3];
2, [10; 11];
3, [4;5];
5, [100];
11, [0; 20];
]
|> Hashtbl.of_seq
in {edges}
# search_for ~g:my_graph ~start:1 (fun x -> x = 30)
- : int option = None
# search_for ~g:my_graph ~start:1 (fun x -> x >= 15)
- : int option = Some 20
# search_for ~g:my_graph ~start:1 (fun x -> x >= 50)
- : int option = Some 100