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