2

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
Improve this question
3
  • 2
    Something I always found helpful for this sort of thing is writing a helper method to print out the contents of the array, which will allow you to be sure that all of your other functionality works properly first. Commented Feb 21, 2011 at 19:35
  • That's not a circular array, that's a normal array. Circular array indices wrap around. More formally, A[i] == A[i%A.length] for all integer i. In a circular array implementation of the above, rear will sometimes be less than front. Also, you should need to create a new array only if the capacity changes. Commented Feb 21, 2011 at 19:53
  • As outis pointed out front and rear should always be in the range [0, capacity-1]. In your code, sometimes you maintain it using %, but other times you assume front can be >= capacity. Pick one way or the other and stick to it. Also, you forgot to adjust getLast() where it's telling you to put your code. ;) Commented Feb 21, 2011 at 21:11

4 Answers 4

Reset to default
4

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

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

0

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

Improve this answer

Comments

-1

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

}

Improve this answer

1 Comment

Giving full code on a homework problem, even if not in the programming language required, isn't as useful for educational purposes. It's too easy to copy without thinking.
-1 
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;
        }
    }
};
Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.