Circular Queue without wasting an entry or using counter

Question

Is it possible to implement a circular queue by use of an array, without having a counter to count the number of items in the queue or without wasting any entry of the array ?

What I guess :

It's not possible , let's assume that we have two pointers front and rear, the first one points to the first element of the queue ,

we can define the rear pointer in two ways :

1.It points to the last element which was inserted into the queue , so the next entry is the possible place for the next element which will be inserted

2.It points to the place where the next element is going to be inserted

In either case we cannot distinguish between full & empty queue if we don't waste at least one entry of the array or if we don't keep a counter counting the number of inserted - number of deleted elements

Answer 1

Your concerns are usually recognized as the full vs. empty difficulty of circular queues. Quoting:

To solve this confusion there are a number of solutions:

1. Always keep one slot open.
2. Use a fill count to distinguish the two cases.
3. Use an extra mirroring bit to distinguish the two cases.
4. Use read and write counts to get the fill count from.
5. Use absolute indices.
6. Record last operation.

Numbers 1, 2, and 4 you address directly in your question. They do consume certain amounts of memory aside from the array and start/end (or front/rear as you name them) indices/pointers. The other solutions also consume memory.

#3 - use a mirroring bit

Only adds one extra boolean or enum, essentially isEmpty or isFull. The idea, logic and proof of this approach is more complicated.

#5 - absoulte indices

Indices are incremented when an operation is performed and never reduced. They are essentially counters of the number of operations of each type performed. This has other drawbacks.

#6 - record last operation

Essentially the same as #3, but different semantics.

Anyways, all those links are to the wikipedia article. I highly recommend it. There may be other approaches, but it would be hard to improve on one of the 6 approaches outlined in your article. They all have drawbacks as well as advantages, so think carefully about the intended use case before settling on an implementation.