The Queue structure

The Queue structure provides an imperative queue data structure, which are implemented as a pair of stacks (lists) representing the front and rear of the queue. Single-threaded enqueuing and dequeuing operations will have amortized constant time.

Synopsis

signature QUEUE
structure Queue :> QUEUE

Interface

type 'a queue

exception Dequeue

val mkQueue : unit -> 'a queue
val clear : 'a queue -> unit
val isEmpty : 'a queue -> bool
val enqueue : 'a queue * 'a -> unit
val dequeue : 'a queue -> 'a
val next : 'a queue -> 'a option
val delete : ('a queue * ('a -> bool)) -> unit
val head : 'a queue -> 'a
val peek : 'a queue -> 'a option
val length : 'a queue -> int
val contents : 'a queue -> 'a list
val app : ('a -> unit) -> 'a queue -> unit
val map : ('a -> 'b) -> 'a queue -> 'b queue
val foldl : ('a * 'b -> 'b) -> 'b -> 'a queue -> 'b
val foldr : ('a * 'b -> 'b) -> 'b -> 'a queue -> 'b

Description

type 'a queue: The type constructor for queues.

exception Dequeue

This exceptions is raised when the dequeue function is applied to an empty queue.

val mkQueue : unit -> 'a queue

mkQueue () returns a new empty queue.

val clear : 'a queue -> unit

clear q removes any elements from q leaving it empty.

val isEmpty : 'a queue -> bool

ifEmpty q returns true if the queue is empty.

val enqueue : 'a queue * 'a -> unit

enqueue (q, x) adds x to the end of q.

val dequeue : 'a queue -> 'a

dequeue q removes and returns the first element in q. This function raises the Dequeue exception if it is called on an empty queue.

val next : 'a queue -> 'a option

next q returns SOME x and removes x from q, where x was the first element in q, or NONE if q is empty.

val delete : ('a queue * ('a -> bool)) -> unit

delete (q, pred) removes those items from q for which the function pred returns true.

val head : 'a queue -> 'a

head q returns the first element of q or raises the exception Dequeue if q is empty. The queue is unchanged.

val peek : 'a queue -> 'a option

peek q returns SOME x, where x is the first element of q, or NONE if q is empty. The queue is unchanged.

val length : 'a queue -> int

length q returns the number of elements in the queue.

val contents : 'a queue -> 'a list

contents q returns the contents of q as a list.

val app : ('a -> unit) -> 'a queue -> unit

app f q applies the function f to the elements of q. This expression is equivalent to

List.app f (contents q)

val map : ('a -> 'b) -> 'a queue -> 'b queue

map f q returns a new queue that results from mapping the function f across the elements of the queue.

val foldl : ('a * 'b -> 'b) -> 'b -> 'a queue -> 'b

foldl f init q folds the function f over the elements of q from front to back. This expression is equivalent to

List.foldl f init (contents q)

val foldr : ('a * 'b -> 'b) -> 'b -> 'a queue -> 'b

foldr f init q folds the function f over the elements of q from back to front. This expression is equivalent to

List.foldr f init (contents q)

Synopsis

Interface

Description

See Also