CODEWITHSUNDEEP
javaqueueadt
Ryman Holmes
Ryman Holmes

Reputation: 756

Enqueue method in CircularArrayQueue class

I have come across the enqueue() method in CircularArrayQueue class:

public void enqueue (T element) {
if (size() == queue.length){
expandCapacity();
}
queue[rear] = element;
rear = (rear+1) % queue.length;
count++;
}

I don't quite understand what the rear = (rear+1) % queue.length; part of the code does, can someone break down the steps of that line of code.

I do understand that it increments rear as a new element has been added however I am unsure of the % operation.

Upvotes: 0

Views: 2083

Answers (3)

Kevin Gurney
Kevin Gurney

Reputation: 1471

One way to visualize what is happening is to imagine a clock (often used as an analogy for modular arithmetic, which is happening in the line you mentioned with the use of the % operator).

For example, imagine that the CircularArrayQueue has a size of 4 at the moment and that its length is 5 (indices 0 - 4). In the example below, the current value of rear is 4 (index 4)

The items in the internal array might look like this:

INDEX | 0 | 1 | 2 | 3 | 4 |
VALUE |   | 8 | 9 | 2 | 1 |
                        ^
                        |
                       Rear

Now let's say that you insert the value 7 into the CircularArrayQueue, then the line

rear = (rear + 1) % queue.length;

would be executed. This effectively computes the following:

add 1 to rear (4) -> 5
divide by queue.length (5) -> 5 / 5 = 1 (remainder of 0)
take the remainder of the previous division (0) and set it equal to rear

INDEX | 0 | 1 | 2 | 3 | 4 |
VALUE | 7 | 8 | 9 | 2 | 1 |
        ^
        |
       Rear

so after all of these steps, rear now equals 0 and points to the first index in the internal array of the CircularArrayQueue. This behavior of the index "wrapping back around" the array when it reaches the end is the circular behavior that is characteristic of a CircularArrayQueue.

The way that this relates to a clock, is that the minute hand on a clock always "wraps back around" when it reaches 60, and "resets" back to 0.

In other words, the internal array used as an example above, can be thought of as a clock with only 5 minutes (indices 0 - 4). You can think of (rear + 1) as advancing by a minute on the clock. After the "minute hand" (rear) has been incremented 4 times, it starts again at 0.

Upvotes: 1

user987339
user987339

Reputation: 10707

rear = (rear+1) % queue.length; achieves circularity. As CircularArrayQueue class name suggests it is circular. It means that when the last element (queue.length-th) is reached it begins to insert elements from the beginning. rear = (rear+1) % queue.length returns rear+1 in case the rear+1 < queue.length , and 0 if rear+1 == queue.length and in this case it start inserting elements from the beginning of the array.

Upvotes: 0

java seeker
java seeker

Reputation: 1266

it basically rounding your queue index for circular queue.

lets say your array queue.length==10,so when rear incremented to 10 it will be rounded to 0 to insert next element at 0 index.

Upvotes: 0

Related Questions