when is a queue full?

Question

I have seen many ways to check when a queue is full, but I don`t understand any, so in simple words when is a queue full?

(If there is a code please make it in C++ or pseudocode)

I have this code to check if the queue is full:-

myFront != (myBack+1) % max

(e.g. why isn`t it simply " myBack == max ")

Answer 1

A queue is full when you have no more space to enqueue/insert new items whether do to storage constraints, or programmatic constraints. (assuming its bounded)

Check here(wikipedia) and it shows a C# example with a "size" limit.

Code snippet(from link above):

#region Constructor
public Queue(int Size)
 {
     this._Size = Size;
 }

 //Enqueue
if (this.IsFull())
{
    throw new Exception("Queue is full !");
}
... do enqueue

// check full
public virtual bool IsFull()
{
   return (this._Count == this._Size);
}

Answer 2

The wikipedia article en.wikipedia.org/wiki/Circular_buffer cited by Helper Method gives a very good explanation of this (including diagrams) that I won't try to repeat here.

The "myFront != (myBack+1) % max" test implies that the code is using the "Always Keep One Slot Open" strategy to detect a full queue; there's sample code in the wikipedia article that uses the exact same test for "buffer full" (they write it as: (end + 1) % BUFFER_SIZE != start).

In case it's not clear, the purpose of the "(myBack+1) % max" is to add 1 to myBack, and if the result == max, instead set the result to 0.

Answer 3

This question seems to be about a circular queue implemented with an array. In this case, myFront, myBack and myBack+1 must all be in the range [0,max). Most of the time you could check for a full queue by checking myFront != (myBack+1). The one additional case where this simple check would fail to be true is where myBack==max-1 and myFront==0. Adding in the modulus % makes the code simpler by wrapping the two cases into one check becuause (max-1)+1 % max == 0.