0

I have this code for adding:

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    }
    else{
        if(size==q.length){
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, r);
            f = 0;
            q = copyQ;
        }
    }
    q[r]=item;
    r = (r+1)%(q.length);
    size++;
}

But then when I want to get the value of r it gives me one more value than it actually is. Also, when I copy the values from one Array to the other there is a value that it is skipping one value. I know everything has to do with the value of r = (r+1)%(q.length); and I've been working on it for hours and can't figure it out. After assigning the value to q[r], even if it is only the first value, and I try to get the value of where r should be it gives me 1 because it is increased by the formula, but I can't figure out how to write it in a different way without messing up the circular queue formula. Any help would be greatly appreciated. Thanks!

2
  • you might want to explain what r is meant to be
    – Matt
    Oct 11, 2011 at 22:57
  • r is the rear, and f is the front. q is the name of the queue. Oct 11, 2011 at 22:58

2 Answers 2

1

Unit tests are your friend! :-)

Express your desired behaviour as tests, gradually building up complexity in your add() method until it all works. I did it for your circular buffer and the working add() looked like this:

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    } 
    else {
        if (size == q.length) {
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, (r + 1));
            f = 0;
            r = q.length -1;
            q = copyQ;
        }
    }

    r = (r+1)%(q.length); 
    q[r]=item;
    size++;
}

Note the differences:

  • r is an offset - you can't use it as a length in the second arraycopy()
  • r needs to be updated when you resize your internal array
  • Changed order of evaluation, incrementing r before storing item
0

Is it because the the last three lines should in within the else block? Try a code like:

public void add(AnyType item){
    if(isEmpty()){
        q[f]=item;
    }
    else{
        if(size==q.length){
            AnyType[] copyQ = (AnyType[]) new Object[q.length*2];
            System.arraycopy(q, f, copyQ, 0, q.length-f);
            System.arraycopy(q, 0, copyQ, q.length-f, r);
            f = 0;
            q = copyQ;
        }
    q[r]=item;
    r = (r+1)%(q.length);
    size++;
    }
}

When the three lines are outside the else block, you were adding the new element twice in case when the data structure is empty.

1
  • Not twice, only once. Since is a Queue, you can only add to R and remove from F. Plus, R needs to be incremented after each add somehow, and so does the size. Oct 11, 2011 at 23:07

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.