# 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

[ Top | Parent | Contents | Index | Root ]

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