CISC 3130 — Lab #1

Code a class that implements a deque conforming to the Deque interface presented in Lecture 5.

The container should have a built-in array as its underlying container
- The array should be under capacity management (i.e., you should have a checkCapacity method, or whatever you introduced for your capacity management back in Lab 02, and you need to resize as needed)
  - the initial capacity should be 5 and the capacity should be doubled when resizing
    - The redoubling is for proper amortization of the resizing cost, as well as to stay in synch with the CodeLab output when submitting it
- There should be a single default (i.e., no arguments) constructor
  - The user has no control over capacity in this implementation (including at the initial creation of the object) and thus there is no need for any information to be passed to the container as an argument to the constructor).
The container should throw exceptions when appropriate
- You can simply follow the demo output for this
The container should be generic
The array should be treated as a ring-buffer (circular array) and front and rear pointers should be used.

Notes:

You have front/rear logic for a circular array in Lecture 7's treatment of the FIFO queue; the difference here is that the two additional operations introduce decrements on the front/rear indices as well (as discussed in the treatment of deques in that lecture).
- first = (first + 1) % capacity (and similarly for rear) is fine; however, when decrementing, the variables may go negative (to -1 from 0) and Java's modulo operator might not act the way you expect, so when decrementing, you should use an explicit conditional rather than the % operator, e.g.:
```
	front--;
	if (front < 0) front = capacity()-1;
				
```
Even though the deque resizes and thus does not get 'full', you will have to detect when resizing is necessary, and the issue of distinguishing between full and empty still arises (as discussed in class and in that lecture). Please use a size variable, rather than the 'single unused element' technique (the latter may throw off the checking performed in the demo).

I've supplied you with the code for:

the source and class files for the CollectionException class,
the Demo app CodeLab will use to check your submission, as well as the correct output of that program (i.e., using a correct ArrayDeque implementation.)
- There are two 'Demo' classes … both need to be added to your project, and the ArrayDequeDemo class is the one you need to launch (i.e., the one containing the main method for the app).

After developing in your IDE (don't forget I gave yo all the classes you need to complete your app), submit your class to CodeLab

CISC 3130
Data Structures
Lab #7
Array Implementations
A Ring-Buffer Implementation of a Deque