Queue implementation in haskell using 2 stacks.

queue.hs

module QueueStacks where

type Stack v = [v]

push :: v -> Stack v -> Stack v
push value stack = value:stack

pop :: Stack v -> Stack v
pop [] = []
pop (_:newStack) = newStack



data Queue v = InStackOutStack (Stack v) (Stack v) deriving (Eq, Show)

enqueue :: v -> Queue v -> Queue v
enqueue tmp (InStackOutStack ins out) = (InStackOutStack (push tmp ins) out)

dequeue :: Queue v -> Queue v
dequeue q = dequeueDisp (dispatch q)


dequeueDisp (InStackOutStack ins out) = (InStackOutStack ins (pop out))

dispatch :: Queue v -> Queue v
dispatch (InStackOutStack [] []) = (InStackOutStack [] [])
dispatch (InStackOutStack ins []) = (InStackOutStack [] (reverse ins))
dispatch (InStackOutStack ins out) = (InStackOutStack ins out)