-- implements Queue data structure
-- by Scot Drysdale on 8/25/07

-- This version has O(1) amortized enqueue and dequeue

module Queue (Queue (Queue), makeQueue, enqueue, dequeue, isEmpty) where

import qualified Stack as S

data Queue a = Queue {inStack :: S.Stack a, outStack :: S.Stack a}
     deriving Show

-- Create an empty queue
makeQueue             :: Queue a
makeQueue             =  Queue S.makeStack S.makeStack

-- Add x to end of queue, returning the updated queue
enqueue               :: a -> Queue a -> Queue a
enqueue x q           =  Queue (S.push x (inStack q)) (outStack q)

-- return the front of the queue paired with the updated queue
dequeue               :: Queue a -> (a, Queue a)
dequeue q@(Queue inSt outSt) 
   | (isEmpty q)        = error "Cannot dequeue an empty Queue"
   | (S.isEmpty outSt)  = dequeue (Queue outSt (transfer inSt outSt))
   | otherwise          = let (x,s) = S.pop outSt
                          in  (x, Queue inSt s)

-- returns true if queue is empty
isEmpty              :: Queue a -> Bool
isEmpty q            =  S.isEmpty (inStack q) && S.isEmpty (outStack q)

-- Transfer everything in stack 1 to stack 2 and return the new s2.
transfer              :: S.Stack a -> S.Stack a -> S.Stack a 
transfer s1 s2  | S.isEmpty s1  = s2
                | otherwise     = let (x, s) = S.pop s1
                                  in transfer s (S.push x s2)