Implementing a deque using a circular array?

Question

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];       
    }
    /**
     * 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

Answer 1

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

Answer 2

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:)

Answer 3

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

}

Answer 4

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