queue
hsでは
先頭から要素を取り除くのは安価
末尾に要素を追加するのは高価
なので、内部で2つのリストを持つように作る
hsdata Queue a = Queue [a] [a]
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)で済む