Algorithm Problems 2

## _4. Problem: Interface Deque_ A deque (doubly-ended queue) is a list that only allows elements to be added or removed from the front or rear. interface Deque { void addFront(Object o); void removeFront(Ob ject o) throws NoSuchElementException; void addRear(Object o); void removeRear(Ob ject o) throws NoSuchElementException; } Implement and test an adapter that implements Deque by pre-processing messages before forwarding them to a List object: class AdapterDeque implements Deque { List elems; AdapterDeque(List elems) { [login to view URL] = elems; } // etc. } Implement and test a linked-list-backed implementation of Deque. The operations should be O(1): class ListDeque implements Deque { Cell front, rear; // etc. } ## Deliverables __5. Problem: Inteface Stack, Interface Queue__ A stack is a list that only allows elements to be removed or added to the front: interface Stack { void push(Object o); void pop() throws EmptyStackException; Object top() throws EmptyStackException; } A queue is a list that only allows elements to be removed from the front and added to the rear: interface Queue { void enqueue(Object o); void dequeue() throws NoSuchElementException; Object front() throws NoSuchElementException; } Implement and test an adapter that implements Stack by pre-processing messages before forwarding them to a Deque object: class AdapterStack implements Stack { Dequeue elems; // etc. } Implement and test an adapter that implements Queue by pre-processing messages before forwarding them to a Deque object: class AdapterQueue implements Queue { Deque elems; // etc. } 6. Problem: class LinkedList Following the style of ArrayCollection, implement and test a linked-list-backed non-mutable and mutable implementations of the Collection interface: class LinkedListCollection extends [login to view URL] { protected Cell head; // etc. } class MutableLinkedListCollection extends ListListCollection { // etc. } _7. Problem: class ArrayList_ Following the style of ArrayCollection, implement and test an array-backed non-mutable and mutable implementations of the List interface: class ArrayList extends [login to view URL] { protected Object[] a; // etc. } class MutableArrayList extends ArrayList { // etc. } _8. Problem: Profiling_ The List interface specifies several position-dependent methods: interface List extends Collection { void add(int index, Object obj); Object remove(int index); Object get(int index); // etc. } Assume the following definitions: n = lenght of list i = an index d = min(i, n ??" i) = shortest distance to end For the LinkedList implementation of List we get the following runtimes: interface LinkedList implements List { void add(int index, Object obj); // O(d) Object remove(int index); // O(d) Object get(int index); // O(d) // etc. } For the ArrayList implementation of List we get the following runtimes: interface ArrayList implements List { void add(int index, Object obj); // O(n - i)amortized Object remove(int index); // O(n - i) Object get(int index); // O(1) // etc. } ## Platform JavA, run on textpad