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.
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.
CircularArrayQueue have a size of 4 and a length of 5, that is a bit confusing?
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.
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.
