implementation of a queue using a circular array

Question

Hi I have found these algorithms in the internet but I can not understand that why in the enqueue method we compare size with N-1??? please help me thanks!!

Algorithm size():
return (N-f+r)mod N



Algorithm enqueue(e):
if size()=N-1 then
   throw a FullQueueException
Q[r]<---e
r<----(r+1)mod N

Answer 1

You provided a very broken (and incorrect) implementation.

That being said, a circular queue in an array usually starts at a given index and ends at another given index (thus the f and r). However, no matter what you do, you can't have more items in the queue than you do in the underlying array.

The size function here is supposed to calculate the number of elements in the queue. If the number becomes dangerously close to the total array size, then the queue is full.

Answer 2

I agree with @Matthew Flaschen's comment, but I will take a guess. I suspect that the queue is N long, and one element is reserved for a sentinel for searching. It is not how I would do it, though.

Answer 3

Given an implementation of circular queues wherein the begin and end are kept as indicies modulo the size of the allocated underlying array, say N, it is necessary that the actual capacity of the queue (not the array) be less than N, elsewise the begin and end indicies will be equal and there would be ambiguity between empty and full.

Thus, when the allocated underlying array is of size N the true capacity of the queue is N-1. That is the why of the test.

There are ways around this that actually allow use of all N slots AND eliminate the division implicit in taking the index modulo n.