## _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