Implementing a deque using a circular array?

I'm having a lot of trouble implementing this deque using a circular array; in particular, the remove methods seem to be removing the wrong elements no matter what I try. 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;
    }

   /**
     * 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];    开发者_如何学Go   
    }
    /**
     * 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

the code size() == capacity will never be true, this is why it's not expanding. Make it size() == capacity - 1.

I'm giving this away is because it's very easy to overlook

According to your given code, the value of front will always retain the value zero.

1. In removeFirst(), you have to do front++;
2. In insertLast() you are doing rear++ twice. You can remove the rear++ outside the if/else.
3. Your removeFirst() always returns the second element, because the for-loop in that method looses the first element.

NOTE: Any of the above will not make it a circular queue. Advice: read and reimplement:)

I have an implementation on C that I have made some time ago. I think should be easy to port to Java or at least gives you a hint on how to implement it in Java.

Thanks, Sergio.

typedef struct { void *elems; / The data. */ size_t sz; /* Capacity of queue. */ size_t nelems; /* Number of elements in the queue. */ size_t first; /* Points to the first element in the queue. */ } 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);

}

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;
        }
    }
};