Circular queue without wasting a record or using a counter

Question

Is it possible to implement a circular queue using array without having a counter to count the number of elements in the queue or without losing any array record?

What I think:

Impossible, let's say that we have two front and rear pointers, the first points to the first element of the queue,

we can define a back pointer in two ways:

1. It points to the last item that was inserted into the queue, so the next record is a possible place for the next item to be inserted

2.It points to where the next element will be inserted

In any case, we cannot distinguish between a full and an empty queue if we do not spend at least one array entry, or if we do not store the counter of the number of inserted - number of deleted elements

Answer 1

Your problems are usually recognized as a complete or empty circular queue problem . Citation:

To solve this confusion, there are a number of solutions:

• Always keep one slot open.
• Use the fill amount to distinguish two cases.
• Use the extra mirror bit to distinguish between two cases.
• Use the read and write amount to get a fill counter.
• Use absolute indexes.
• Record the last operation.

Numbers 1, 2 and 4 you directly address your question. They consume a certain amount of memory, except for the array and indexes / start / end indexes (or front / back, as you call them). Other solutions also consume memory.

# 3 - use the mirror bit

Adds only one additional logical value or enumeration, essentially isEmpty or isFull . The idea, logic, and proof of this approach are more complex .

# 5 - absoulte indices

Indexes increase when an operation is performed and never decreases. They are essentially counters of the number of operations of each type performed. These are other disadvantages .

# 6 - record the last operation

Essentially the same as # 3, but different semantics.

In any case, all of these links relate to the wikipedia article. I highly recommend it. There may be other approaches, but it would be difficult to improve one of the 6 approaches outlined in your article. They all have disadvantages as well as advantages, so think carefully about the intended use case before proceeding with implementation.

Answer 2

As soon as I implemented it, I used an extra bool called "empty". You are right, it cannot be distinguished if both pointers are in the same place.

Depending on which pointers you use, you can use the low-order bit of a single pointer to store an empty variable.
In the case where the size is an integer number of variables, you can also use a negative value to indicate that there are no elements in the queue.

Answer 3

at the beginning, let first = 0, rear = -1;

we add it as follows ..... array [rear]; back = (back + 1)% MAX;

we remove it as follows: array [front]; front = (front + 1)% MAX;

when removing an element from the array, we can add a condition after it as follows: ... if(front==rear+1) first=0, rear=-1

then an empty condition can be specified as ...

 if(rear==-1) printf("Empty"); 

the full condition will then be ...

 if ( ( front==(rear+1) || (front==0 && rear==(n-1) ) && rear!=-1 ) printf("Full"); 

it might work. the count function is not used

Answer 4

An alternative is to use three pointers, where the third pointer points to the space between the two pointers. There are a number of ways to implement this. The main thing to note, however, is that the middle pointer should only say the following two things.

• The queue is empty. All pointers point to the same place (second definition for the back pointer).
• There is 1 element in the queue, and deleting the element will make it empty. The middle pointer and another pointer point to the same place.

This can simply be done by holding the middle pointer between the first and last and offset by one from the first or last pointer as long as the queue has 1 or more elements.

This is probably, at best, only a slight improvement in counter usage, and even worse.