SA-8

Exercises

Implement a deque — a double ended queue — where items can be added or removed from the front or the back. Your deque implementation should conform to this SimpleDeque.java interface.

You can implement the deque using a doubly linked list or an array. If you use a doubly linked list, keep a head and tail pointer (like SA-4), and each element in the list should have a previous and next pointer, instead of just the next pointer we implemented previously. If you use an array, the array should grow when full (e.g., no limit to the number of items stored in the deque). For full credit, the SimpleDeque methods except contains should run in constant time.

Include test cases to show that your implementation works as intended.

Submission Instructions

Turn in your completed Java code with test cases. Also give the run-time complexity of each of the deque's methods.