Summary of two methods to realize circular queue based on Java array

The method of implementing circular queue in Java:

1. Add an attribute size to record the current number of elements.

The purpose is when head = rear. By size = 0 or size = array length. The incoming queue is empty or the queue is full.

2. Only - 1 element of the array size is stored in the array to ensure that the rear will not be equal to the head after one revolution. That is, when the queue is full. Rear + 1 = head, with just one empty element in the middle.

When rear = head. The queue must be empty.

The types of consent operations at both ends of the queue are different:

The end that can be deleted is called the queue head, and such an operation is also called the queue dequeue;

The end that can be inserted is called the end of the queue. This operation is also called enqueue.

Schematic of the queue

When implementing the queue, we should pay attention to the false overflow phenomenon. As shown in the last picture above.

As you can see, the false overflow phenomenon

Solution: use chained storage, which obviously can. In sequential storage. Our common solution is to connect it head to tail to form a circular queue. This can make full use of the storage space of the queue.

Circular queue diagram:

In the figure above. Front points to the first element in the queue. Rear points to the next position at the end of the queue.

But there is still a problem: when front and rear point to the same position, does this mean that the team is empty or full? You can imagine such a scene.

A common way to solve this problem is:

Use a marker to distinguish such confusing situations.

Sacrifice an element space. Null when front and rear are equal. When the next position of the rear is front. Is full.

For example, the following figure:

Below, we give a circular queue and find out what to do with the location

Several key points:

1. Front points to the head of the team. Rear points to the next position at the end of the team.

2. Inference if the queue is empty: front = = rear; Inference when the queue is full: (rear + 1)% maxsize = = front.

The above summary of the two methods to realize circular queue based on Java array is all the content shared by Xiaobian. I hope it can give you a reference and support more programming tips.