Queue implementation with circular array

Question

I am reading about implementation of DynaArrayQueue (queue that doubles in size when there are no enough elements)

I have certain questions regarding two methods in it.

Let capacity be the capacity of the queue.

getQueueSize() Method

public int getQueueSize()
 {
if(front == -1) return 0;

//Here why can't the size by  simply [(rear -front +1) %capacity ]
int size = (capacity - front + rear +1) % capacity;

if(size == 0) return capacity;
else return size;
 }

When calculating the size why are we using

size = (capacity - front + rear +1 ) % capacity , instead of simply (rear - front +1) % capacity. ?

Question 2:

resizeQueue()

This is the method that resizes the queue

  private void resizeQueue()
 {
int initCapacity = capacity;
capacity *=2;

int[] oldArray = array;

array = new init[this.capacity];

//this is fine
for(int i=0; i<oldArray.length;i++)
{
    array[i] =oldArray[i];
}

//why do we need this ?
if(rear < front)
{
    for(int i =0 ; i<front ; i++)
    {
        array[i+initCapacity] = this.array[i];
        array[i]= null;

    }

    rear = rear + initCapacity;

}


  }

The first for loop in the method is straight forward, but why do we need the second if loop for ?. What conditions it is taking care of ?

dpington · Accepted Answer · 2011-12-30 04:52:48Z

8

1. The reason capacity is there is because

(rear - front)

can be negative, negative modulus vary by language implementations.

2. The reason you have the 2nd loop is because

In this situation

[#####000000####]
     ^      ^
    rear   front

# is array item
0 is empty space

When you copy to a larger array, you get a disjointed array

[#####000000####000000000000000]

The second loop moves

[#####000000####000000000000000]
 ^---^

to

[00000000000#########0000000000]
                ^---^

edited Dec 30, 2011 at 4:52

answered Dec 30, 2011 at 4:46

dpington

1,8943 gold badges17 silver badges30 bronze badges

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

1 Comment

Dave L. Over a year ago

But isn't the condition in the orig code 'rear < front'? In your example rear is greater than front right?

Jim Mischel · Accepted Answer · 2011-12-30 04:47:15Z

1

The second loop is making sure that items are stored in the proper order in the new array. Imagine a circular buffer where front (the place you're taking from) is greater than rear (where you're adding things). So capacity is 50, front is 40, and rear is 10. Items will be removed from the queue in the order 40, 41, 42, 43...0, 1, 2, ... 9.

Now, when you resize the queue, items are copied to the new array in the same order. But removing items from the queue, which now has capacity of 100, will be 40, 41, 42, ... 49, 50, 51. But there's nothing at position 50!

So those 10 items are moved from positions 0 through 9 to positions 50 through 59. That's what the second loop does.

answered Dec 30, 2011 at 4:47

Jim Mischel

135k25 gold badges197 silver badges377 bronze badges

Comments

Dawood ibn Kareem · Accepted Answer · 2011-12-30 04:47:55Z

0

Not familiar with this class, but I guess if the queue has wrapped around, so that new items are being written at the start of the array, then "rear" could be less than "front". This kind of answers both of your questions, because in this case, (rear - front +1) % capacity would be negative, which is not what you want (Q1), and also the new part of the queue would have to be transplanted to the end, which the capacity increases (Q2).

answered Dec 30, 2011 at 4:47

Dawood ibn Kareem

80.2k15 gold badges102 silver badges112 bronze badges

1 Comment

Dawood ibn Kareem Over a year ago

I would go into more detail with the second bit, but Herp posted a really good answer just as I was finishing mine; and his is better.

Collectives™ on Stack Overflow

Queue implementation with circular array

3 Answers 3

1. The reason capacity is there is because

2. The reason you have the 2nd loop is because

1 Comment

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

1. The reason capacity is there is because

2. The reason you have the 2nd loop is because

1 Comment

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related