SML/NJ Library Manual

The Queue structure

Synopsis

signature QUEUE
structure Queue : QUEUE


The Queue structure provides a simple implementation of mutable queues. The current implementation relies on the applicative queues defined in Fifo, and therefore has similar performance.

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

exception Dequeue

mkQueue ()

returns an empty queue.

clear qu

removes all the elements in qu.

isEmpty qu

returns true if qu is empty.

enqueue (qu, a)

appends a to the end of qu.

dequeue qu

removes and returns the head element in qu. Raises the exception Dequeue if qu is empty.

delete (qu, f)

deletes all elements in qu satisfying the predicate f.

head qu

returns the head of qu without removing it. Raises the exception Dequeue if qu is empty.

peek qu

returns the head of qu if it exists; otherwise, returns NONE.

length qu

returns the number of elements in qu. At present, this is a linear time operation.

contents qu

returns the elements in qu in queue order. This is a linear time operation.

app f qu

applies the function f to the elements in qu in queue order. This is equivalent to:

            List.app f (contents qu)
          

map f qu

creates a new queue by mapping the elements in qu by f. This is equivalent to:

            let
              val newq = mkQueue ()
            in
              app (fn v => enqueue(newq,f v)) qu;
              newq
            end
          

foldl f a qu

folds the elements of the queue from the head to the tail. This is equivalent to:

            List.foldl f a (contents qu))
          

foldr f a qu

folds the elements of the queue from the tail to the head. This is equivalent to:

            List.foldr f a (contents qu))
          

See Also

Fifo

Last Modified May 14, 1998
Comments to John Reppy
Copyright © 1998 Bell Labs, Lucent Technologies