Module Queue

module Queue: sig .. end

FIFO キュー

このモジュールでは破壊的変更のできるキューを実装します。

type 'a t

'a 型の要素を格納するキューの型。

exception Empty

Queue.take や Queue.peek を空のキューに適用したときに発生する例外です。

val create : unit -> 'a t

空の新しいキューを返します。

val add : 'a -> 'a t -> unit

add x q はキュー q の末尾に要素 x を追加します。

val push : 'a -> 'a t -> unit

add と同義です。

val take : 'a t -> 'a

take q はキュー q から最初の要素を取り除いてその要素を返します。キューが空のときは Empty 例外が発生します。

val pop : 'a t -> 'a

take と同義です。

val peek : 'a t -> 'a

peek q はキュー q の先頭の要素を返します。要素自体はキューから取り除きません。キューが空のときは Empty 例外が発生します。

val top : 'a t -> 'a

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 -> unit

iter f q は q の要素に、最初から追加されたものから最近追加されたものへ、順に f を適用します。キュー自体は変更されません。

val fold : ('a -> 'b -> 'a) -> 'a -> 'b t -> 'a

fold f accu q は List.fold_left f accu l と等価です。ここで、 l は q の要素のリストです。キュー自体は変更されません。

val transfer : 'a t -> 'a t -> unit

transfer q1 q2 は q1 の要素をすべてキュー q2 の末尾に追加し、 q1 を clear します。これは iter (fun x -> add x qs); clear q1 と等価ですが定数時間で実行されます。