Модуль Stack

module Stack: sig .. end

Стек по принципу «последним пришёл — первым вышел».

Этот модуль реализует стеки (LIFO) с модификацией на месте.

Предупреждение unsynchronized_access. Несинхронизированный доступ к стекам является ошибкой программирования.

Несинхронизированный доступ

Несинхронизированный доступ к стеку может привести к некорректному состоянию очереди. Поэтому конкурентный доступ к стекам необходимо синхронизировать (например, с помощью Mutex.t).

type !'a t

Тип стеков, содержащих элементы типа 'a.

exception Empty

Возникает, когда к пустому стеку применяется Stack.pop или Stack.top.

val create : unit -> 'a t

Возвращает новый, изначально пустой стек.

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

push x s добавляет элемент x на вершину стека s.

val pop : 'a t -> 'a

pop s удаляет и возвращает верхний элемент стека s или вызывает исключение Stack.Empty, если стек пуст.

val pop_opt : 'a t -> 'a option

pop_opt s удаляет и возвращает верхний элемент стека s или возвращает None, если стек пуст.

Начиная с версии 4.08

val drop : 'a t -> unit

drop s удаляет верхний элемент стека s или вызывает исключение Stack.Empty, если стек пуст.

Начиная с версии 5.1

val top : 'a t -> 'a

top s возвращает верхний элемент стека s или вызывает исключение Stack.Empty, если стек пуст.

val top_opt : 'a t -> 'a option

top_opt s возвращает верхний элемент стека s или None, если стек пуст.

Начиная с версии 4.08

val clear : 'a t -> unit

Удаляет все элементы из стека.

val copy : 'a t -> 'a t

Возвращает копию указанного стека.

val is_empty : 'a t -> bool

Возвращает true, если указанный стек пуст, и false в противном случае.

val length : 'a t -> int

Возвращает количество элементов в стеке. Временная сложность O(1)

val iter : ('a -> unit) -> 'a t -> unit

iter f s последовательно применяет f ко всем элементам s — от элемента на вершине стека до элемента в его основании. Сам стек не изменяется.

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

fold f accu s — это (f (... (f (f accu x1) x2) ...) xn), где x1 — вершина стека, x2 — второй элемент, а xn — элемент в основании. Стек не изменяется.

Начиная с версии 4.03

Стеки и последовательности

val to_seq : 'a t -> 'a Seq.t

Перебирает стек сверху вниз. Во время перебора стек можно безопасно изменять.

Начиная с версии 4.07

val add_seq : 'a t -> 'a Seq.t -> unit

Добавляет элементы последовательности на вершину стека.

Начиная с версии 4.07

val of_seq : 'a Seq.t -> 'a t

Создаёт стек из последовательности.

Начиная с версии 4.07