CIS 400 Assignment 3 (part 2)
                        Fall 1996

     The definition of abstract data types is best done 
using language independent terms. At some point though, it 
becomes important to implement the type using the constructs 
present in some particular language. Despite the claims that 
any data type may be simulated using any other type, often 
compromises must be made which impair the integrity of the 
type. In this assignment you are to implement the formal 
type specification below using objects in a language which 
supports object oriented programming.

           Structure Dequeue;
             newdq()            -> dequeue
             addr(dequeue,item) -> dequeue
             addl(dequeue,item) -> dequeue
             delr(dequeue)      -> dequeue 
             dell(dequeue)      -> dequeue
             peekr(dequeue)     -> item
             peekl(dequeue)     -> item
             isnewdq(dequeue)   -> boolean

           Declare q :dequeue; i :item;
             isnewdq(newdq())   = true
             isnewdq(addr(q,i)) = false
             isnewdq(addl(q,i)) = false
             delr(addr(q,i))    = q
             delr(addl(q,i))    = if isnewdq(q) then newdq()
                                  else addl(delr(q),i)
             dell(addl(q,i))    = q
             dell(addr(q,i))    = if isnewdq(q) then newdq()
                                  else addr(dell(q),i)
             peekl(addl(q,i))   = i
             peekl(addr(q,i))   = if isnewdq(q) then i
                                  else peekl(q) 
             peekr(addr(q,i))   = i
             peekr(addl(q,i))   = if isnewdq(q) then i
                                  else peekr(q) 
           Restrictions
             peekr(newdq())  = error
             peekl(newdq())  = error
             delr(newdq())   = error
             dell(newdq())   = error
   
     You may use any features of the language(s) to 
implement this ADT, as long as the resulting ADT conforms to 
the above type specification. You will need to devise 
experiments to demonstrate that your ADTs behave correctly. 
You should also include some tests which demonstrate any 
failures of your implementation to completely encapsulate 
the type declaration or its operations. You will need to 
turn in clearly commented source listings of your code and 
any relevant computer output.