# Queues

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.

## First Attempt — `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)

## Second Attempt — `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)

## Third Attempt — `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)

## Final Version — `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.