Simple queue algorithm
This is not a request for a queue algorithm, I know there are many.
I am reading a C # book and it explains the Circular Queue algorithm with sample code. On lines 13, 14 and 15, he explains how to check if the queue is full. However, I cannot understand why the first prerequisite is needed. Can someone show me the situation when it would be necessary?
Here's the class code:
And my question 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;
}
source to share
The first check runs the next part of the statement in the comments.
putloc is one less than getloc
This check is necessary because your turn is round robin. If you can always assume that the end of the queue was the last element in the array, then the check is unnecessary. In this case though ... the end of the queue could happen in the middle of the array, in which case the queue will be full and you will be hit by that condition.
source to share
In a circular queue, whenever you insert something into it, putLoc moves through the array, ending at the end. Whenever you pop something from the queue, getLoc traverses the array and also completes at the end. The queue is full when putLoc is immediately before getLoc.
There are two cases when this can happen. If getLoc has never moved, or turns out to wrap back to the beginning of the array, then it is 0 and the queue is full when putLoc is at the end of the array (next click will cause it to wrap 0). This is the second half of the if statement.
If a pair of values are dequeued, then getLoc can be in the middle of the array. In this case, the queue is not filled when putLoc is at the end of the array, but when it is wrapped and immediately before getLoc. In this case, the first part of the if statement is processed (the part you are asking for).
source to share
Both of them are actually the same condition. Think of it in terms of modulo equality.
A circular queue, implemented with an array, is populated when the last added element is at location N (modulo length), and the earliest element is at location N + 1 (modulo length). This means that there is a "length" of elements in the queue and there is no room for a new one, so it is full.
There are several ways to code this test, but the method used in the example code is to use the string arithmetic version without using a module.
You can also code it like this:
if ((putloc + 1) % q.length == getloc) {}
and it would be logically the same if getloc
it was correctly constrained between 0 and q.length - 1
.
source to share
The logic can be better understood in 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:
- putloc does not rewind, then new_putloc = putloc + 1
- putloc rewinds, then put_loc = q.Length-1
source to share
The left half of the expression is the main one, which works for almost all scenarios, and the right half is for a unique edge, where putloc is the end of the queue and getloc is the beginning of the queue. When putloc is 4 and getloc is 5, the left side is true, but when the queue is 10 and putloc is 9 and getloc is 0, the right side is true.
source to share