The `Queue`

abstraction employs a First-In-First-Out (FIFO) policy for removing ("dequeing") elements.

```
enqueue : a -> Queue a -> Queue a
dequeue : Queue a -> Maybe (Queue a)
peek : Queue a -> Maybe a
```

Without having *O(1)* time access to the last element in a `List`

, special care must be taken to provide efficient `Queue`

operations in a purely functional language.

`SlowQueue.elm`

```
type Queue a = Q (List a)
empty : Queue a
empty = Q []
isEmpty : Queue a -> Bool
isEmpty q = q == empty
enqueue : a -> Queue a -> Queue a
enqueue x (Q xs) = Q (xs ++ [x])
dequeue : Queue a -> Maybe (Queue a)
dequeue (Q xs) = case xs of
_::xs' -> Just (Q xs')
[] -> Nothing
peek : Queue a -> Maybe a
peek (Q xs) = case xs of
x::_ -> Just x
[] -> Nothing
```

Running times:

`enqueue`

:*Θ(n)*`dequeue`

:*O(1)*`peek`

:*O(1)*

`AnotherSlowQueue.elm`

```
type Queue a = Front (List a) | Back (List a)
empty : Queue a
empty = Front []
isEmpty : Queue a -> Bool
isEmpty q = case q of
Front [] -> True
Back [] -> True
_ -> False
enqueue : a -> Queue a -> Queue a
enqueue x q = case q of
Front xs -> Back (x :: List.reverse xs)
Back xs -> Back (x :: xs)
dequeue : Queue a -> Maybe (Queue a)
dequeue q = case q of
Back [] -> Nothing
Back (x::xs) -> Just (Back xs)
Front xs -> dequeue (Back (List.reverse xs))
peek : Queue a -> Maybe a
peek q = case q of
Back [] -> Nothing
Back (x::_) -> Just x
Front xs -> peek (Back (List.reverse xs))
```

Running times:

`enqueue`

:*O(n)*`dequeue`

:*O(n)*`peek`

:*O(n)*

`MediumQueue.elm`

```
type Queue a = Q { front: List a, back: List a }
mkQ f b = Q {front = f, back = b}
empty : Queue a
empty = mkQ [] []
isEmpty : Queue a -> Bool
isEmpty q = q == empty
enqueue : a -> Queue a -> Queue a
enqueue x (Q {front, back}) = mkQ front (x::back)
dequeue : Queue a -> Maybe (Queue a)
dequeue (Q {front, back}) = case (front, back) of
(_::f', _) -> Just (mkQ f' back)
([], []) -> Nothing
([], _) -> dequeue (mkQ (List.reverse back) [])
peek : Queue a -> Maybe a
peek (Q {front, back}) = case (front, back) of
(x::_, _) -> Just x
([], []) -> Nothing
([], _) -> peek (mkQ (List.reverse back) [])
```

Running times:

`enqueue`

:*O(1)*`dequeue`

:*O(n)*`peek`

:*O(n)*

`FastQueue.elm`

Same representation `Q {front, back}`

as previous version, but with the invariant `front = []`

implies `back = []`

.

```
enqueue : a -> Queue a -> Queue a
enqueue x (Q {front, back}) = case (front, back) of
([], _) -> mkQ [x] []
_ -> mkQ front (x::back)
dequeue : Queue a -> Maybe (Queue a)
dequeue (Q {front, back}) = case (front, back) of
([] , _) -> Nothing
(_::[], _) -> Just (mkQ (List.reverse back) [])
(_::f', _) -> Just (mkQ f' back)
peek : Queue a -> Maybe a
peek (Q {front, back}) = case (front, back) of
(x::_, _) -> Just x
([] , _) -> Nothing
```

We can factor out a common pattern from `enqueue`

and `dequeue`

. Notice that arguments `f`

and `b`

to `checkFront`

do *not* necessarily satisfy the invariant, but the output `Queue`

does.

```
checkFront : List a -> List a -> Queue a
checkFront f b = case (f, b) of
([], _) -> mkQ (List.reverse b) []
(_ , _) -> mkQ f b
enqueue' : a -> Queue a -> Queue a
enqueue' x (Q {front, back}) = checkFront front (x::back)
dequeue' : Queue a -> Maybe (Queue a)
dequeue' (Q {front, back}) = case front of
[] -> Nothing
_::f' -> Just (checkFront f' back)
```

Running times:

`enqueue`

:*O(1)*`dequeue`

:*O(n)*`peek`

:*O(1)*

The worst-case bound for `dequeue`

does not tell the whole story, however, since it often runs in *O(1)* time and only occasionally runs in *O(n)* time. Using amortized asymptotic analysis, we will be able to argue that `dequeue`

runs in *O(1)* on average.

- Okasaki, Chapter 5.2