Greetings,
I'm trying to implement a Deque using a circular array that extends when the array gets full. My problem seems to be that the array refuses to extend. Either I am computing size() incorrectly or there is a problem with how I update my front and rear indices. I've looked over it many times and I seem to figure this out. Can anyone help?
public class ArrayDeque
{
public static final int INIT_CAPACITY = 8; // initial array capacity
protected int capacity; // current capacity of the array
protected int front; // index of the front element
protected int rear; // index of the rear element
protected int[] A; // array deque
public ArrayDeque( ) // constructor method
{
A = new int[ INIT_CAPACITY ];
capacity = INIT_CAPACITY;
front = rear = 0;
}
/**
* Display the content of the deque
*/
public void printDeque( )
{
for ( int i = front; i != rear; i = (i+1) % capacity )
System.out.print( A[i] + " " );
System.out.println();
}
/**
* Returns the number of items in this collection.
*/
public int size()
{
return (capacity - front + rear) % capacity;
}
/**
* Returns true if this collection is empty.
*/
public boolean isEmpty()
{
return front == rear;
}
/**
* Returns the first element of the deque
*/
public int getFirst() throws EmptyDequeException
{
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
return A[front % capacity];
}
/**
* Returns the last element of the deque
*/
public int getLast() throws EmptyDequeException
{
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
return A[(rear - 1) % capacity];
}
/**
* Inserts e at the beginning (as the first element) of the deque
* If array is full, extend array by doubling its capacity and insert element in new array
*/
public void insertFirst(int e)
{
if(size() == capacity){
int[] B = new int[2*capacity];
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
A = B;
}
int[] B = new int[capacity];
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
A = B;
for(int i = size(); i >= front; i--){
A[i+1] = A[i];
}
A[front] = e;
rear = (rear + 1) % capacity;
}
/**
* Inserts e at the end (as the last element) of the deque
* If array is full, extend array by doubling its capacity and insert element in new array
*/
public void insertLast(int e)
{
if(size() == capacity){
capacity *= 2;
int[] B = new int[capacity];
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
A = B;
}
A[rear] = e;
rear = (rear + 1) % capacity;
}
/**
* Removes and returns the first element of the deque
* Shrink array by half of current size N when number of elements in the deque falls below N/4
* minimum capacity should always be 8
*/
public int removeFirst() throws EmptyDequeException
{
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
else if(capacity >= 8){
if(size() < capacity/4){
capacity /= 2;
int[] B = new int[capacity];
for(int i = 0; i < size(); i++){
B[i] = A[i];
}
A = B;
}
}
int temp = A[front];
A[front] = 0;
front = (front + 1) % capacity;
return temp;
}
/**
* Removes and returns the last element of the deque
* Shrink array by half of current size N when number of elements in the deque falls below N/4
* minimum capacity should always be 8
*/
public int removeLast() throws EmptyDequeException
{
if(isEmpty()){
throw new EmptyDequeException("Deque is empty.");
}
else if(capacity >= 8){
if(size() < capacity/4){
int[] B = new int[capacity/2];
for(int i = 0; i < capacity; i++){
B[i] = A[i];
}
A = B;
}
}
int temp = A[rear - 1];
A[rear] = 0;
rear = (rear - 1) % capacity;
return temp;
}
} // end class
Test Input:
for(i = 1; i <= 100; i++)
q.insertLast(i);
q.printDeque();
for(i = 1; i <= 99; i++)
k = q.removeFirst();
q.printDeque();
Test Output: I've set up several print statements and the size always remains at 7 for some reason...
Exception in thread "main" A3.EmptyDequeException: Deque is empty.
at A3.ArrayDeque.removeFirst(ArrayDeque.java:133)
at A3.ArrayMain.main(ArrayMain.java:37)
