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

```

Fifo

[ Top | Parent | Contents | Index | Root ]