Methods to implement loop queues using java:
1. Add an attribute size to record the number of elements currently.
The purpose is when head=rear. By size=0 or size=array length. to distinguish the queue as empty, or the queue is full.
2. Only the array size -1 element is stored in the array, ensuring that the rear will not be equal to the head after turning it around. That is when the queue is full. rear+1=head, there is just one element in the middle.
When rear=head. The queue must be empty.
The types of agreed operations on both ends of the queue are different:
The end that can be deleted is called the head of the team, and such an operation is also called the dequeue;
The end that can be inserted is called the tail of the team, and such an operation is also called enqueue.
Schematic diagram of the queue
When implementing a queue, you should pay attention to the false overflow phenomenon. As shown in the last picture above.
Fake overflow as seen in the figure
Solution: Use chain storage, which obviously can. When stored sequentially. Our common solution is to connect it to the end and form a circular queue. This makes full use of the queue's storage space.
Loop queue diagram:
In the picture 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 situation.
Common practices to solve this problem are this:
A mark is used to distinguish such confusing situations.
Sacrifice an elemental space. When front and rear are equal, they are empty. When the next position of the rear is front. It's full.
For example, the following figure:
Below we give the loop queue and use another way, that is, sacrificing an element space to distinguish between empty and full teams.
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 that the team is empty: front==rear; inference that the team is full: (rear+1)%MAXSIZE==front.
import java.io.*; public class QueueArray { Object[] a; //Object array, the queue stores up to a.length-1 object int front; //From the first subscript int rear; //From the end subscript public QueueArray(){ this(10); //Call other constructors} public QueueArray(int size){ a = new Object[size]; front = 0; rear = 0; } /** * Append an object to the end of the queue* @param obj object* @return Return false when the queue is full, otherwise true */ public boolean enqueue(Object obj){ if((rear+1)%a.length==front){ return false; } a[rear]=obj; rear = (rear+1)%a.length; return true; } /** * The first object in the head of the queue is dequeued* @return The object dequeued when the queue is empty */ public Object dequeue(){ if(rear==front){ return null; } Object obj = a[front]; front = (front+1)%a.length; return obj; } public static void main(String[] args) { QueueArray q = new QueueArray(4); System.out.println(q.enqueue("Zhang San")); System.out.println(q.enqueue("Li Si")); System.out.println(q.enqueue("Zhao Wu")); System.out.println(q.enqueue("Wang Yi")); //Cannot enter the queue, the queue is full for(int i=0;i<4;i++){ System.out.println(q.dequeue()); } } }The above summary of the two methods of implementing circular queues based on Java arrays is all the content I share with you. I hope you can give you a reference and I hope you can support Wulin.com more.