Привет,
Я пытаюсь реализовать Deque, используя круговой массив, который расширяется при заполнении массива. Кажется, моя проблема в том, что массив отказывается расширяться. Либо я неправильно вычисляю size (), либо возникла проблема с обновлением моих передних и задних индексов. Я просмотрел это много раз и, кажется, понял это. Кто-нибудь может помочь?
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
Тестовый ввод:
for(i = 1; i <= 100; i++)
q.insertLast(i);
q.printDeque();
for(i = 1; i <= 99; i++)
k = q.removeFirst();
q.printDeque();
Тестовый вывод: я настроил несколько операторов печати, и размер почему-то всегда остается равным 7 ...
Exception in thread "main" A3.EmptyDequeException: Deque is empty.
at A3.ArrayDeque.removeFirst(ArrayDeque.java:133)
at A3.ArrayMain.main(ArrayMain.java:37)