Simple queue algorithm question

Question

This is not a request for a queueing algorithm, I know there are plenty.

I'm reading a C# book and it explains the Circular Queue algorithm with a code example. On lines 13, 14 and 15, he explains how to check if the queue is full. However I can't understand why the first optional condition is necessary. Could someone show me a situation where it will be needed?

Here's the class code:

Pastie.org

And my question is about this section: (putloc + 1 == getloc)

public bool Put(char ch) {    
    /* Queue is full if either putloc is one less than 
    getloc, or if putloc is at the end of the array 
    and getloc is at the beginning. */
    if (putloc + 1 == getloc || ((putloc == q.Length - 1) && (getloc == 0)))
    {
     return false;
    }

Answer 1

The first check is performing the following part of the statement in the comments.

putloc is one less than getloc

This check is needed because your Queue is circular. If you could always assume the end of the Queue was the last element in the Array, then the check would not be needed. In this case though...the end of the Queue could happen in the middle of the Array in which case the Queue would be full and you hit this condition.

Answer 2

Say getloc is 5 and putloc is 4, then that means you have no more room to put anything. Because if you put something in at 5, then you just lost what was there are 5 since you didn't read it out yet.

Answer 3

The logic can be better understood by the following form:

int new_putloc = (putloc + 1) % q.Length;
if (new_putloc == getloc) return false;

the original code just breaks the above logic down to two scenarios:

1. putloc is not rewinding, then new_putloc = putloc+1
2. putloc is rewinding, then put_loc=q.Length-1

Answer 4

In a circular queue whenever you push something into it the putLoc moves down the array, wrapping at the end. Whenever you pop something from the queue getLoc moves down the array, also wrapping at the end. The queue is considered full when putLoc is just before getLoc.

There are 2 cases where this can happen. If getLoc has never moved, or happens to have wrapped back to the beginning of the array then it is at 0 and the queue is full when putLoc is at the end of the array (the next push would cause it to wrap to 0). That's the 2nd half of the if statement.

If a couple values have been popped from the queue then getLoc may be in the middle of the array. In this case, the queue is full not when putLoc is at the end of the array, but when it's wrapped around and is just before getLoc. This is the case the first part of the if statement (the part you're asking about) is handling.

Answer 5

Both of those are actually the same condition. Think of it in terms of modulo equality.

A circular queue implemented with an array is full when the latest element added is in location N (modulo the length) and the earliest element is in location N+1 (modulo the length). This means that there are "length" elements in the queue, and there's no more space for a new one, so it's full.

There are a number of ways to code that test, but the method that the code example uses is to use the straight-up arithmetic version without using modulus.

You could also code it like this:

if ((putloc + 1) % q.length == getloc) {}

and it would be logically the same, as long as getloc was correctly bounded to be between 0 and q.length - 1.

Answer 6

The left half of the expression is the main one that works for almost all the scenarios, the right half is for the unique edge case where the putloc is the end of the queue and the getloc is the beginning of the queue. When putloc is 4 and getloc is 5, the left side is true, but when the queue has a length of 10 and putloc is 9 and getloc is 0, the right side is true.