owanturist/elm-queue

Elm Queue implementation

Queue

Simple FIFO (first-in first-out) queue data structure. First element added to the Queue is the first one to be removed. The implementation has almost the same API as List.

elm install owanturist/elm-queue

If you need double-ended queue please check out Skinney/elm-deque implementation.

Feedback and contributions of any kind a very welcome!

Example

queue : Queue Int
queue =
    Queue.empty
        |> Queue.enqueue 1 -- Queue.fromList [ 1 ]
        |> Queue.enqueue 2 -- Queue.fromList [ 2, 1 ]
        |> Queue.enqueue 3 -- Queue.fromList [ 3, 2, 1 ]


headQueue : Maybe Int
headQueue =
    Queue.head queue -- Just 1


dequeueQueue1 : ( Maybe Int, Queue Int )
dequeueQueue1 =
    Queue.dequeue queue         -- (Just 1, Queue.fromList [ 3, 2 ])


dequeueQueue2 : ( Maybe Int, Queue Int )
dequeueQueue2 =
    Queue.dequeue dequeueQueue1 -- (Just 2, Queue.fromList [ 3 ])


dequeueQueue3 : ( Maybe Int, Queue Int )
dequeueQueue3 =
    Queue.dequeue dequeueQueue2 -- (Just 3, Queue.fromList [])


dequeueQueue4 : ( Maybe Int, Queue Int )
dequeueQueue4 =
    Queue.dequeue dequeueQueue2 -- (Nothing, Queue.fromList [])

Performance

The implementation uses pair of Lists and a peek value for non-empty case. Due to the peek value it takes constant time O(1) to take a look for Queue.head. Lists are used to store incoming and outcomint values. Incoming are stored in natural order and outcoming in reversed one.

Each time when Queue.enqueue happens the value goes to incoming list for constant O(1) time.

Each time when Queue.dequeue happens it extracts next item for constant time O(1). Incoming list becomes outcoming by revert if outcoming list is empty. Then head of outcoming list becomes a new peek. So you can notice that rebalancing happens only when outcoming list is empty at takes time proportional to O(N). Otherwise it takes constant time O(1).