问候，
我正在尝试使用在数组已满时扩展的循环数组来实现 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)