Checking if a circular queue is full

In summary: A queue can be full if the front index is equal to the back index.In summary, 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)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. Without the modulo operator, the r pointer would move from position i=6 to position i=7, but there is no position i=7
  • #1
0131313131313
6
0
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:-

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)
 
Technology news on Phys.org
  • #2
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:

Code:
void Queue::addQ (int x)
{
    if (myFront != (myBack + 1) % max)
    {
        Queue[myBack] = x;
        myBack = (myBack + 1) % max;
    }
else
    cout << "Queue is full"
 
Last edited:
  • #3
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:-

Code:
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?
 
  • #4
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.

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

The modulo operator returns the remainder of myBack / max, and accomplishes the same thing.
 
  • #5
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.
Code:
   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.
Code:
   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.
Code:
   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), Q.add(3), Q.add(5), Q.add(9)

Code:
   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 and 3 such that the r pointer moved to position i=6. Afterwards, the element 5 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.
 
Last edited by a moderator:
  • #6
Edgardo said:
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.
 

Related to Checking if a circular queue is full

What is a circular queue?

A circular queue is a data structure that follows the First-In-First-Out (FIFO) principle, where the first item inserted into the queue is the first item to be removed. It differs from a regular queue in that it uses a circular array instead of a linear array, allowing for efficient use of memory and avoiding the need to shift elements when adding or removing items.

How do you check if a circular queue is full?

To check if a circular queue is full, we need to compare the number of items in the queue with the size of the queue. If the number of items equals the size, then the queue is full. We can also use a variable to keep track of the number of items and update it when items are added or removed from the queue.

What is the time complexity of checking if a circular queue is full?

The time complexity of checking if a circular queue is full is O(1) or constant time. This is because we only need to compare the number of items with the size of the queue, which does not depend on the number of items in the queue.

What happens if we try to add an item to a full circular queue?

If we try to add an item to a full circular queue, it will result in an overflow error. This means that the queue is unable to hold any more items and we need to either remove an item from the queue or increase the size of the queue to add more items.

Can a circular queue be resized?

Yes, a circular queue can be resized by increasing or decreasing the size of the underlying array that it uses. This can be done by creating a new array with the desired size, copying the items from the old array to the new one, and then updating the queue's front and rear pointers to reflect the new array size.

Similar threads

  • Programming and Computer Science
Replies
1
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
3
Views
1K
  • Engineering and Comp Sci Homework Help
Replies
11
Views
3K
  • Programming and Computer Science
Replies
23
Views
1K
  • Programming and Computer Science
Replies
22
Views
4K
  • Programming and Computer Science
3
Replies
75
Views
4K
  • Programming and Computer Science
Replies
17
Views
1K
  • Programming and Computer Science
Replies
33
Views
6K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
3K
  • Programming and Computer Science
Replies
1
Views
1K
Back
Top