我在使用圆形阵列实现此双端队列时遇到了很多麻烦;特别是，无论我尝试什么，删除方法似乎都在删除错误的元素。有人可以帮忙吗？
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;
}
/**
* Returns the number of items in this collection.
* @return the number of items in this collection.
*/
public int size( )
{
return rear - front;
}
/**
* Returns true if this collection is empty.
* @return 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[(front + rear - 1) % capacity]; // replace this line with your code
}
/**
* Inserts e at the beginning (as the first element) of the deque
*/
public void insertFirst( int e )
{
rear++;
if(size() == capacity){
capacity *= 2;
}
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;
front = front % capacity;
}
/**
* Inserts e at the end (as the last element) of the deque
*/
public void insertLast( int e )
{
if(size() == capacity){
capacity *= 2;
A[rear++] = e;
}
else{
A[rear++] = e;
}
rear++;
}
/**
* 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(size() == 0){
throw new EmptyDequeException("Deque is empty.");
}
if(capacity >= 8){
if(size() < capacity/4){
capacity /= 2;
}
}
int[] B = new int[capacity];
for(int i = 1; i < size(); i++){
B[i-1] = A[i];
}
A = B;
return A[front];
}
/**
* 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(size() == 0){
throw new EmptyDequeException("Deque is empty.");
}
if(capacity >= 8){
if(size() < capacity/4){
capacity /= 2;
}
}
int[] B = new int[capacity];
for(int i = front; i<size()-1; i++){
B[i] = A[i];
}
A = B;
rear--;
return A[rear];
}
} // end class
代码size() == capacity将永远不会成真，这就是为什么它不会扩展。让它size() == capacity - 1。
我放弃它是因为它很容易被忽视
我在C上实现了一段时间以前的实现。我认为应该很容易移植到Java或者至少提供一些如何在Java中实现它的提示。
谢谢，塞尔吉奥。
typedef struct {void * elems; / 数据。 * / size_t sz; / *队列容量。 * / size_t nelems; / *队列中的元素数量。 * / size_t优先; / *指向队列中的第一个元素。 * /} nx_queue_t;
nx_queue_t * nx_queue_create（size_t size）{nx_queue_t * q;
if ( (q = malloc (sizeof(nx_queue_t))) == NULL )
return (NULL);
q->sz = size;
q->nelems = 0;
q->first=0;
if ( (q->elems = malloc (sizeof(void*)*size)) == NULL ) {
free (q);
return (NULL);
}
return (q);
}
size_t nx_queue_capacity（nx_queue_t * q）{return（q-> sz）; }
size_t nx_queue_size（nx_queue_t * q）{return（q-> nelems）; }
int nx_queue_empty（nx_queue_t * q）{return（！q-> nelems）; }
int nx_queue_full（nx_queue_t * q）{return（q-> nelems == q-> sz）; }
int nx_queue_enqueue（nx_queue_t * q，void * elem）{size_t i;
if (nx_queue_full (q))
return (-1);
i = (q->first + q->nelems) % q->sz;
q->elems[i] = elem;
q->nelems++;
}
void * nx_queue_dequeue（nx_queue_t * q）{void * elem;
if (nx_queue_empty (q))
return (NULL);
elem = q->elems[q->first];
q->first = (q->first + 1) % q->sz;
q->nelems--;
return (elem);
}
根据您给定的代码，front的值将始终保持零值。
注意：以上任何一项都不会使其成为循环队列。建议：阅读和重新实现:)
class Deque{
int capacity=0,back=-2,front=0;
int*array=NULL;
bool isEmpty(){
return back==-2;
}
bool isFull(){
return ((front-1+capacity)%capacity==back)||((back+1)%capacity==front);
}
public:
Deque(int n){
capacity=n;
array= new int[n];
cout<<"deque allocated with capacity "<<n<<endl;
}
~Deque(){
delete[] array;
cout<<"deque deleted\n";
}
bool push_back(int x){
if(isFull())
return false;
if(back==-2)
back=-1;
back=(back+1)%capacity;
array[back]=x;
return true;
}
bool push_front(int x){
if(isFull())
return false;
if(back==-2){
back=0;
front=1;
}
front=(front-1+capacity)%capacity;
array[front]=x;
return true;
}
int pop_back(){
if(isEmpty())
return -1000;
int a=array[back];
if(back==front){
front=0;
back=-2;
}
else
back=(back-1+capacity)%capacity;
return a;
}
int pop_front(){
if(isEmpty())
return -1000;
int a=array[front];
if(back==front){
front=0;
back=-2;
}
else
front=(front+1)%capacity;
return a;
}
void print(){
if(isEmpty())
cout<<"deque is empty\n";
else{
int temp=front;
while(temp!=back){
cout<<array[temp]<<" ";
temp=(temp+1)%capacity;
}
cout<<array[temp]<<endl;
}
}
};