The queue
- A queue is an ordered list that can be used
Arrays (sequential storage)orLinked list (chain storage)To implement. - follow
First-in, first-outThe principle of. That is, data stored in the queue must be retrieved first. What is put in later is taken out later.
Use arrays to simulate queues
- The queue itself is an ordered list. If the structure of an array is used to store the data of the queue, the declaration of the queue array is shown in the following figure, where maxSize is the maximum capacity of the queue.
- Because the output of the queue, the input is processed from the front and rear end, so we need two variables to record the subscripts of the front and rear end of the queue, front will change with the output of the data, and rear will change with the input of the data.
As shown in the figure:
Analysis of ideas:
When we put data into a queue, we call it addQueue, and addQueue takes two steps
- Move the tail pointer back:
rear+1whenFront == rear[empty] - If the tail pointer
rearLess than the maximum index of the queuemaxSize - 1, the data is savedrearOtherwise, data cannot be stored to an array element.Rear == maxsize-1 [queue full].
Code implementation: use array simulation queue, write an ArrayQueue class
class ArrayQueue{
private int maxSize; // Indicates the maximum size of the array
private int front; / / queue head
private int rear; / / queue tail
private int [] arr; // This array is used to store data, simulating a queue
// Create a queue constructor
public ArrayQueue(int arrMaxSize){
this.maxSize=arrMaxSize;
this.arr=new int[this.maxSize];
this.front=-1; // Front points to the head of the queue.
this.rear=-1; // Point to the end of the queue, which is the last data in the queue.
}
// Check whether the queue is full
public boolean isFull(a){
return this.rear == this.maxSize-1;
}
// Check whether the queue is empty
public boolean isEmpty(a){
return this.rear == this.front;
}
// Add data to the queue
public void addQueue(int n){
if (isFull()){
System.out.println("Queue full, cannot add data");
return;
}
this.rear++; // Make rear move
this.arr[rear]=n;
}
// Get the queue data and exit the queue
public int getQueue(a){
// Check whether the queue is empty
if (isEmpty()){
// Throw an exception
throw new RuntimeException("Queue empty, can't fetch data.");
}
front++; / / the front back
return arr[front];
}
// Display all data in the queue
public void showQueue(a){
if (isEmpty()){
System.out.println("Queue empty, no data.");
}
for (int i=0; i<arr.length; i++){ System.out.printf("arr[%d]=%d\n",i,arr[i]); }}// Display queue header data, note: not fetch data
public int headQueue(a){
/ / determine
if (isEmpty()){
throw new RuntimeException("Queue empty, no data.");
}
return arr[front+1]; }}Copy the codeTest the simulated queue
public static void main(String[] args) {
ArrayQueue arrayQueue= new ArrayQueue(3);
Scanner inpunt =new Scanner(System.in);
Boolean b=true;
do {
switch (inpunt.nextInt()){
case 1: {try {
System.out.println("Display all data in queue");
arrayQueue.showQueue();
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 2:{
System.out.println("Add data to queue");
arrayQueue.addQueue(inpunt.nextInt());
break;
}
case 3: {try {
System.out.println("Show queue header data");
int headQueue = arrayQueue.headQueue();
System.out.println("Queue header:"+headQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 4: {try {
System.out.println("Fetch data from queue");
int queueQueue = arrayQueue.getQueue();
System.out.println("Fetch data:"+queueQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
default:{
b=false; }}}while (b);
}
Copy the code- Test 1: Add data and display all data in the queue
You can see that we've now added three numbers to the queue: 10,20,30
- Test 2: Look at the header data, then look at the header data again after the data is taken out
Because the queue follows the first-in, first-out principle, the first data is the second data added to the queue.
- Test 3: Fetching all data before adding data.
Notice here, when we run out of data, we have problems adding data.
Problem analysis and optimization:
- At present, our array cannot be used once, so it does not achieve the effect of reuse.
- We can algorithmically modify this array to form a circular queue.
Use arrays to simulate circular queues
- Arr [front] is the first element in the queue. The initial value of front is 0.
- The meaning of the rear variable is also adjusted so that rear points to the last position of the last element in the queue. Because I want to leave a space as a convention. The initial value of rear is also 0;
- When the queue is full, the condition is
(rear+1) % maxSize = front [full] - When the queue is empty, the condition is
rear == frontEmpty. - The number of valid data in the queue
(rear+maxSize-front)%maxSize// rear = 1 front = 0
Code implementation
The array simulation queue above is optimized to make full use of the array, so that the array is treated as a ring. (By taking the mode to achieve)
class CircleArray{
private int maxSize; // Indicates the maximum size of the array
Arr [front] is the first element in the queue. The initial value of front = 0;
private int front;
// The meaning of the rear variable is also adjusted so that rear points to the last position of the last element in the queue. Because I want to leave a space as a convention. The initial value of rear is also 0;
private int rear;
private int [] arr; // This array is used to store data, simulating a queue
public CircleArray(int arrMaxSize){
maxSize = arrMaxSize;
arr = new int[maxSize];
}
// Check whether the queue is full
public boolean isFull(a){
return (rear + 1) % maxSize == front;
}
// Check whether the queue is empty
public boolean isEmpty(a){
return this.rear == this.front;
}
// Add data to the queue
public void addQueue(int n){
if (isFull()){
System.out.println("Queue full, cannot add data");
return;
}
// Add data directly
arr[rear] = n;
// Move rear, you have to think about de-modulo here
rear = (rear + 1) % maxSize;
}
// Get the queue data and exit the queue
public int getQueue(a){
// Check whether the queue is empty
if (isEmpty()){
// Throw an exception
throw new RuntimeException("Queue empty, can't fetch data.");
}
/** * front is the first element in the queue * 1. First leave the value of front to a temporary variable * 2. Move front back and consider modulo * 3. Return the temporarily saved variable */
int value = arr[front];
front = (front + 1) % maxSize;
return value;
}
// Display all data in the queue
public void showQueue(a){
/ / traverse
if (isEmpty()){
throw new RuntimeException("Queue empty, no data.");
}
// Start with front and iterate through the elements
for (inti= front; i < front + size(); i++){ System.out.printf("arr[%d]=%d\n",i % maxSize,arr[i % maxSize]); }}// Find the number of valid data in the current queue
public int size(a){
return (rear + maxSize - front) % maxSize;
}
// Display queue header data, note: not fetch data
public int headQueue(a){
/ / determine
if (isEmpty()){
throw new RuntimeException("Queue empty, no data.");
}
returnarr[front]; }}Copy the codeTest the ring queue
public static void main(String[] args) {
// Test the array to simulate a ring queue
CircleArray circleArray= new CircleArray(4); // Set to 4, the maximum number of valid data in the queue is 3
Scanner inpunt =new Scanner(System.in);
Boolean b=true;
do {
switch (inpunt.nextInt()){
case 1: {try {
System.out.println("Display all data in queue");
circleArray.showQueue();
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 2:{
System.out.println("Add data to queue");
circleArray.addQueue(inpunt.nextInt());
break;
}
case 3: {try {
System.out.println("Show queue header data");
int headQueue = circleArray.headQueue();
System.out.println("Queue header:"+headQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
case 4: {try {
System.out.println("Fetch data from queue");
int queueQueue = circleArray.getQueue();
System.out.println("Fetch data:"+queueQueue);
}catch (Exception e){
e.printStackTrace();
}
break;
}
default:{
b=false; }}}while (b);
}
Copy the code- Test 1 adds data to a ring queue
- Test 2 fetches data from a ring queue
- Test 3 Obtain data and add data again
