1. Double-Ended Queues

Re-implement the dequeue from HW 3 so that it can handle an unbounded number of elements. Your dequeue should have the same interface as in HW 3, except that the constructor will no longer take a maximum size parameter, since there is no maximum size. You should probably use some form of linked list in your implementation. Your implementation will be judged on both correctness and efficiency. Submit (at least) three files (header, implementation, test program) as usual.

2. Sparse Arrays, take two

Recall the sparse arrays of HW 2. In that case we were interested in arrays of a very restricted form (all zeroes, followed by some numbers, followed by all zeroes). A more general (and useful) setting is an array where most elements are zero but the non-zero elements are allowed to appear anywhere. In this exercise you must implement a data structure for this scenario.

• It should have a read_element and a write_element method, a constructor and a destructor if necessary. The user will not supply you with the size of the array when constructing an object.
• Your class should accomodate reads and writes on any position. A read on a position where the user has not written anything should return a 0.
• Overload the [] operator so that the user can use this class as if it were an array. (This requires some thought to decide what the proper behavior should be. Include a detailed comment explaining what your implementation does and why)
• The memory used in your implementation should be proportional to the number of non-zero elements the user currently has in the array. It should not depend on the positions where the user is writing.

Hint: You will probably want to implement this using some form of list to hold the elements the user writes.