Homework #2

Implement class CircularArrayDeque which implements Deque interface using wrap-around resizable array.

class CircularArrayDeque <E> implements Deque {

public CircularArrayDeque();

public CircularArrayDeque(Collection <? extends E> other);

public int size();

public boolean isEmpty(); // check this first for removes

public E getFirst();

public void addFirst(E e);

public E removeFirst();

public E getLast();

public void addLast(E e);

public E removeLast();

publicc E get(int idx); // return the element with an offset of idx relative to front i.e. items[ (front+idx) % capacity]

private int increment(int x);

private void doubleDeque(); // check whether deque is full (reaches capacity) first before insertions; if yes expand

private E [] items;

private int currentSize, capacity, front, back;

private static final int DEFAULT_CAPACITY =10;

}

Test the Deque with initial integer array int[] arr ={8, 7, 5, 3, 6, 7, 12, 4} as the parameter of constructor call;

Stack use: call addLast(1); addLast(2); addLast(3); removeLast(); print the array after these operations.

Queue use: then call removeFirst(); addLast(3); print the final Deque and get(5) element.