# Module Fdeque

    module Fdeque: sig .. end

A simple polymorphic functional double-ended queue. Use this if you need a queue-like data structure that provides enqueue and dequeue accessors on both ends. For strictly first-in, first-out access, see `Fqueue`.

Amortized running times assume that enqueue/dequeue are used sequentially, threading the changing deque through the calls.

    type 'a t

    include Container.S1

`Container` operations traverse deque elements front-to-back, like `Front_to_back` below. If you need faster traversal and don't care about the order, use `Arbitrary_order` below.

`is_empty` and `length` have worst-case complexity O(1).

    include Invariant.S1

    module Arbitrary_order: sig .. end

Traverse deque elements in arbitrary order.

    module Front_to_back: sig .. end

Traverse deque elements front-to-back.

    module Back_to_front: sig .. end

Traverse deque elements back-to-front.

    val empty : 'a t

The empty deque.

    val singleton : 'a -> 'a t

A one-element deque.

    val of_list : 'a list -> 'a t

`of_list` returns a deque with elements in the same front-to-back order as the list.

    val rev : 'a t -> 'a t

`rev t` returns `t`, reversed.

Complexity: worst-case O(1)

    val enqueue : 'a t -> [ `back | `front ] -> 'a -> 'a t

`enqueue t side x` produces `t` updated with `x` added to its `side`.

Complexity: worst-case O(1).

    val enqueue_front : 'a t -> 'a -> 'a t

    val enqueue_back : 'a t -> 'a -> 'a t

    val peek : 'a t -> [ `back | `front ] -> 'a option

`peek t side` produces `Some` of the element at the `side` of `t`, or `None` if `t` is empty.

Complexity: worst-case O(1).

    val peek_exn : 'a t -> [ `back | `front ] -> 'a

    val peek_front : 'a t -> 'a option

    val peek_front_exn : 'a t -> 'a

    val peek_back : 'a t -> 'a option

    val peek_back_exn : 'a t -> 'a

    val drop : 'a t -> [ `back | `front ] -> 'a t option

`drop t side` produces `Some` of `t` with the element at its `side` removed, or `None` if `t` is empty.

Complexity: amortized O(1), worst-case O(length t).

    val drop_exn : 'a t -> [ `back | `front ] -> 'a t

    val drop_front : 'a t -> 'a t option

    val drop_front_exn : 'a t -> 'a t

    val drop_back : 'a t -> 'a t option

    val drop_back_exn : 'a t -> 'a t

    val dequeue : 'a t -> [ `back | `front ] -> ('a * 'a t) option

`dequeue t side` produces `Option.both (peek t side) (drop t side)`.

Complexity: amortized O(1), worst-case O(length t).

    val dequeue_exn : 'a t -> [ `back | `front ] -> 'a * 'a t

    val dequeue_front : 'a t -> ('a * 'a t) option

    val dequeue_front_exn : 'a t -> 'a * 'a t

    val dequeue_back : 'a t -> ('a * 'a t) option

    val dequeue_back_exn : 'a t -> 'a * 'a t

    module Stable: sig .. end

    val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t

    val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t

    val compare : ('a -> 'a -> int) -> 'a t -> 'a t -> int

    val bin_t : 'a Bin_prot.Type_class.t -> 'a t Bin_prot.Type_class.t

    val bin_read_t : 'a Bin_prot.Read.reader -> 'a t Bin_prot.Read.reader

    val __bin_read_t__ : 'a Bin_prot.Read.reader -> (int -> 'a t) Bin_prot.Read.reader

    val bin_reader_t : 'a Bin_prot.Type_class.reader -> 'a t Bin_prot.Type_class.reader

    val bin_size_t : 'a Bin_prot.Size.sizer -> 'a t Bin_prot.Size.sizer

    val bin_write_t : 'a Bin_prot.Write.writer -> 'a t Bin_prot.Write.writer

    val bin_writer_t : 'a Bin_prot.Type_class.writer -> 'a t Bin_prot.Type_class.writer

`Container` operations traverse deque elements front-to-back, like `Front_to_back` below. If you need faster traversal and don't care about the order, use `Arbitrary_order` below.

`is_empty` and `length` have worst-case complexity O(1).
Traverse deque elements in arbitrary order.
Traverse deque elements front-to-back. Incurs up to O(n) additional time and space cost over `Arbitrary_order`.
Traverse deque elements back-to-front. Incurs up to O(n) additional time and space cost over `Arbitrary_order`.
The empty deque.
A one-element deque.
`of_list` returns a deque with elements in the same front-to-back order as the list.
`rev t` returns `t`, reversed.

Complexity: worst-case O(1)
`enqueue t side x` produces `t` updated with `x` added to its `side`.

Complexity: worst-case O(1).
`peek t side` produces `Some` of the element at the `side` of `t`, or `None` if `t` is empty.

Complexity: worst-case O(1).
`drop t side` produces `Some` of `t` with the element at its `side` removed, or `None` if `t` is empty.

Complexity: amortized O(1), worst-case O(length t).
`dequeue t side` produces `Option.both (peek t side) (drop t side)`.

Complexity: amortized O(1), worst-case O(length t).