rear value not working properly in circular array queue

Question

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!

r is the rear, and f is the front. q is the name of the queue. — randomizertech
– randomizertech, Commented Oct 11, 2011 at 22:58

millhouse · Accepted Answer · 2011-10-12 00:15:38Z

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

cheekoo · Accepted Answer · 2011-10-11 23:05:10Z

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.

answered Oct 11, 2011 at 23:05

cheekoo

87712 silver badges22 bronze badges

1 Comment

randomizertech Over a year ago

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.

Collectives™ on Stack Overflow

rear value not working properly in circular array queue

2 Answers 2

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related