Simple FIFO (first in, first out) queue data structure. First element added to the
Queue is the first one to be removed.
If you're interested in double-ended queue implementation please see folkertdev/elm-deque.
This package is highly experimental and might change a lot over time.
Feedback and contributions to both code and documentation are very welcome.
This implementation uses pair of
as described by Chris Okasaki in his Purely Functional Data Structures
(page 15). One list is used for dequeuing elements, the other one is used for enqueuing new ones. Items in enqueuing
stored in reversed order so adding new elements is cheap (O(1)). When last element is taken out from dequeuing list
Queue happens. Rebalacing is done by reversing enqueuing list and storing it as new dequeuing list. This is costly operation
(O(n)). However it shouldn't happen too often due to access from just one side of a
Queue. Most of the time both
dequeue happens in O(1).
front is guaranteed to be O(1).