Design and implement a variant of ArrayDeque that does not do any modular arithmetic at all. Instead, all the data sits in a consecutive block, in order, inside an array. When the data overruns the beginning or the end of this array, a modified rebuild() operation is performed. The amortized cost of all operations should be the same as in an Array Deque. Hint: Getting this to work is really all about how you implement the rebuild() operation. You would like rebuild() to put the data structure into a state where the data cannot run off either end until at least n/2 operations have been performed. Test the performance of your implementation against the Array Deque. Optimize your implementation (by using System. Array copy(a, i, b, i, n)) and see if you can get it to outperform the Array Deque implementation.
