Checking if a circular queue is full

[0131313131313]

So, my teacher comes to the lecture, writes the notes on the board... and then says: "from now on this part is intuitive"...
he means this part: (myFront != (myBack + 1) % max)
of the following (C++) code:-

void Queue::addQ (int x)
{
     if (myFront != (myBack + 1) % max)
     {
           ...
           ...
     }
else
     cout << "Queue is full"

I don't understand it, can anyone explain it please? I don`t understand the relationship between finding whether a queue is full or not, and this line of code: (myFront != (myBack + 1) % max)

 

[rcgldr]

Without a separate count for the number of items in the circular queue, if myFront == myBack, you don't know if the queue is full or empty. By considering the queue to be full at (max - 1) entries, then the separate count is not needed, and only the indexes are needed. The queue is "full" when the input (add to queue) index ((myBack+1) % max) == the output (remove from queue) index myFront. It would have helped if the addQ example included the code fragment where myBack gets incremented:

void Queue::addQ (int x)
{
    if (myFront != (myBack + 1) % max)
    {
        Queue[myBack] = x;
        myBack = (myBack + 1) % max;
    }
else
    cout << "Queue is full"

 

[0131313131313]

Without a separate count for the number of items in the circular queue, if myFront == myBack, you don't know if the queue is full or empty.

Actually, I have this code for checking whether a queue is empty or not:-

bool Queue::empty()
{
     return (myBack == myFront);
}

Is it wrong?
Also,

The queue is "full" when the input (add to queue) index ((myBack+1) % max) == the output (remove from queue) index myFront.

I don`t understand the use of the mod operator, what does it represent? I understand it solves a problem (that we can`t simply say myFront==myBack) but how does it do that?

 

[rcgldr]

The cicular queue is an array with "max" entries in it. Each time you increment an index if it's equal to max, you need to reset the index to zero to "wrap" the index back from the end of the array to the start of the array.

    myBack = myBack+1;
    if(myBack == max)
        myBack = 0;

The modulo operator returns the remainder of myBack / max, and accomplishes the same thing.

 

[Edgardo]

The mod operator calculates the remainder of a division, e.g. 17 mod 3 = 2.
Reason: 17/3=5 with a remainder of 2.

Other examples:
20 mod 5 = 0
13 mod 5 = 3
27 mod 5 = 2A circular queue is like a tube that has both ends glued together. It then looks like a donut (see http://en.wikipedia.org/wiki/Circular_buffer" ).

This data structure can be implemented using an array. There are two pointers called "Front" and "Rear" that tell you where the content starts and ends. You can think of them as head and tail of a snake inside the donut.

Example for a circular queue that can can hold at most 7 elements:

Step (i) First start with an empty array A where i is the index.
Both the f and r pointer point to position 0 at the beginning.

   i  | 0 1 2 3 4 5 6 
A[i]  | _ _ _ _ _ _ _
       f,r

Step (ii) Add some elements:
Q.add(3), Q.add(1), Q.add(0), Q.add(8), Q.add(4)
Each time the Rear pointer r moves to the right. The r pointer is now at position i=4.

   i  | 0 1 2 3 4 5 6 
A[i]  | 3 1 0 8 4 _ _
        f       r

Step (iii) Remove some elements:
Q.delete(), Q.delete()
The Front pointer f moves to the right twice.

   i  | 0 1 2 3 4 5 6 
A[i]  | _ _ 0 8 4 _ _
            f   r

Step (iv) Add more elements and watch closely what happens to the r pointer:
Q.add(1[/color]), Q.add(3[/color]), Q.add(5[/color]), Q.add(9)

   i  | 0 1 2 3 4 5 6 
A[i]  | 5 9 0 8 4 1 3
          r f

In Step (iii) the r pointer was initially at position i=4. Then, in Step(iv) we added the elements 1[/color] and 3[/color] such that the r pointer moved to position i=6. Afterwards, the element 5[/color] is added, but what happens? The r pointer jumps to the very left of the array, to position i=0 and inserts the 5 there. (This is because we have a donut).

The question is how do you tell your computer to jump to position 0? And the answer is: Use the modulo operator. If you don't use the modulo operator your r pointer will move from position i=6 to position i=7, but there is no position i=7!

So in summary:
Without modulo:
old_position = 6
new_position = old_position+1 = 7

With modulo:
old_position = 6
new_position = (old_position+1) mod (sizeArray)
= 7 mod (sizeArray) = 7 mod 7 = 0

Step (v) Add one more element
This results in an error since your f and r pointer would collide which corresponds to your code (myBack==myFront). Your queue is full.

 

[rcgldr]

Example for a circular queue that can can hold at most 7 elements

The examples show an array of size 7, but it can only hold at most 6 elements, unless you add another variable to distinguish between an empty or full queue when front == back.