Queue

type Queue a

A linear data structure where elements are added to the back (enqueue) and removed from the front (dequeue).

Construct

empty : Queue a

The empty queue.

fromList : List a -> Queue a

Create a queue from a list.

Query

isEmpty : Queue a -> Bool

isEmpty empty == True


isEmpty (fromList []) == True


isEmpty (fromList [ 1 ]) == False

peek : Queue a -> Maybe a

Get the first element added to the queue without modifying the queue.

peek empty == Nothing


peek (fromList [ 1, 2, 3 ]) == Just 1


peek (enqueue 3 (enqueue 2 (enqueue 1 empty))) == Just 1

Modify

enqueue : a -> Queue a -> Queue a

Add an element to the back of the queue.

toList (enqueue 1 empty) == [ 1 ]


toList (enqueue 2 (fromList [ 1 ])) == [ 1, 2 ]

The worst-case time is O(1).

dequeue : Queue a -> Maybe ( a, Queue a )

Remove and return the first element added to the queue.

dequeue empty == Nothing


dequeue (enqueue 1 empty) == Just ( 1, empty )


dequeue (enqueue 2 (fromList [ 1 ])) == Just ( 1, fromList [ 2 ] )

The worst-case time is O(n). However, a sequence of n enqueue and dequeue operations starting from an empty queue has a total running time of O(n). Therefore, the amortized time per operation is O(1).

Convert

toList : Queue a -> List a

toList empty == []


toList (fromList [ 1, 2, 3, 4, 5 ]) == [ 1, 2, 3, 4, 5 ]

Modules

Queue