queue

hsでは

先頭から要素を取り除くのは安価

末尾に要素を追加するのは高価

なので、内部で2つのリストを持つように作る

code:hs

emptyQueue :: Queue a

emptyQueue = Queue [] []

-- backに追加

enqueue :: a -> Queue a -> Queue a

enqueue x (Queue front back) = Queue front (x:back)

-- 基本的にはfrontから取り出す. frontがなくなればbackをfrontに持ってくる

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

dequeue (Queue [] []) = (Nothing, Queue [] [])

dequeue (Queue (x:xs) back) = (Just x, Queue xs back)

dequeue (Queue [] back) = dequeue (Queue (reverse back) [])

reverseするときだけO(N)。それ以外はO(1)で済む