The update is late. The real-time data warehouse has started in the past two days. There is no need to mention the amount of code and steal time. But there is no leisure at all, but it is impossible to challenge with youth
Ring queue
After reading Day2, the students must have found that the queue implemented by this array seems to have no reusability. I'm out of the team, but I can't add it. Let's optimize it this time
First of all, I will write out the contents of the optimization, and then analyze why I do it
1. The former position of front pointing to the first element is changed to the position of front pointing to the first element (moved back one position)
2. The original position of rear pointing to the last element is changed to the position of rear pointing to the last element (moved back one position)
3. The initial values of front and rear are both 0 (originally - 1)
So, overall, we move all the pointers back one grid, and then we define a vacancy in the array
Now let's explain in detail:
So our structure is like this
After improvement, our structure becomes like this ↓
After improvement, our empty space will not save data
Note: the position of the vacancy is not fixed. For example, the following figure
If you have a little partner, you have to ask? Then why do you want an empty seat? I'll use rear to represent the last element, like the following figure. Can't I?
Then, according to the above figure, how should you judge the status of the queue that is empty?
According to common sense, we should think that when the rear and front coincide, the queue is empty. But obviously, when the rear and front coincide in the above figure, it seems that it is not so easy to judge, just like the following figure
In fact, there are many ways to implement ring queue with array. It is not necessary to leave a space, but it is easy to understand
Where is it convenient to understand? Why can't I understand at all?
Judge whether the ring queue is full:
//Determine whether the queue is full public boolean isFull(){ return ((rear + 1) % maxSize) == front; }
It can be seen from the previous design that the empty bit is normally at the last position of the rear pointer, but when the queue is full, the rear will point to the empty bit
Therefore, after taking the module, the above formula rear + 1 can be equal to the front pointer to indicate that the queue is full. As shown in the following figure
For other methods, just pay attention to the mold of maxSize. There are no other difficulties
By the way, there will be another size() method to judge the valid elements in the queue
//Find the number of valid data in the current queue public int size() { return (rear - front) % maxSize; }
According to the question, rear = position of the last element + 1
front = position of the last element
Because the array subscript starts from 0, that is, the valid number is (last element position - first element position + 1)% maxsize
Overall code
import java.util.Scanner; public class CircleArrayQueueDemo { public static void main(String[] args) { //Create a queue CircleArrayQueue queue = new CircleArrayQueue(3); char key = ' ';//Used to receive instructions from users Scanner scanner = new Scanner(System.in); boolean flag = true; while (flag){ System.out.println("=====1.Show queue====="); System.out.println("=====2.Exit program====="); System.out.println("=====3.Add data to queue====="); System.out.println("=====4.Fetch data from queue====="); System.out.println("=====5.View data of queue header====="); key = scanner.next().charAt(0); switch (key){ case '1': try { queue.showQueue(); } catch (Exception e) { System.out.println("Queue is empty"); } break; case '2': flag = false; break; case '3': System.out.println("=====Please enter the number you want to add====="); int i = scanner.nextInt(); try { queue.addQueue(i); } catch (Exception e) { System.out.println("The queue is full,Cannot execute"); } break; case '4': try { int result = queue.getQueue(); System.out.println("====Number removed " + result + " ===="); } catch (Exception e) { System.out.println("Queue is empty,Unable to remove"); } break; case '5': System.out.println("====The data of the current queue header is " + queue.headQueue() + " ===="); break; default: System.out.println("Please enter the correct instruction"); } } } } //Use arrays to simulate queues -- write an ArrayQueue queue class CircleArrayQueue{ private int maxSize; // Represents the maximum capacity of the array private int front; // Point to the first element of the queue (originally pointing to the previous position of the first element) private int rear; // Point to the position after the last element of the queue (originally pointed to the last element) //Therefore, it can be found that after this modification (the head and tail pointers are moved back by one position), we can make a space private int[] arr; //This data is used to store data and simulate the queue //Constructor to create a queue public CircleArrayQueue(int maxSize){ this.maxSize = maxSize; arr = new int[maxSize]; front = 0; //Point to the first element rear = 0; //Points to the last position of the last element } //Determine whether the queue is full public boolean isFull(){ return ((rear + 1) % maxSize) == front; } //Determine whether the queue is empty public boolean isEmpty(){ return rear == front; } //Add data to queue public void addQueue(int n){ if (!isFull()){ //Add data directly arr[rear] = n; //When moving the rear, we must consider modulo (because if we move back endlessly, we will cross the boundary when adding data) rear = (rear + 1) % maxSize; }else{ throw new RuntimeException("sorry , the queue is full"); } } //Get the data of the queue and get out of the queue public int getQueue(){ if (!isEmpty()){ //Don't forget that the current front is the first element pointing to the queue int i = arr[front]; front = (front + 1) % maxSize; return i; }else{ throw new RuntimeException("sorry,there is no element can be gotten"); } } //Displays all data for the queue public void showQueue(){ if (isEmpty()){ System.out.println("the queue is empty"); throw new RuntimeException("sorry,there is no element can be shown"); }else{ for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d]=%d",i % maxSize,arr[i % maxSize]); System.out.println(); } } } //Displays the header data of the queue public int headQueue(){ if (isEmpty()){ System.out.println("the queue is empty"); throw new RuntimeException("sorry,there is no element can be shown"); }else{ return arr[front]; } } //Find the number of valid data in the current queue public int size() { return (rear - front) % maxSize; } }