Queue (linear structure)

1. A queue is a sequence table , It can be used Array or Linked list To achieve
2. follow First in, first out Principles

The illustration

• The queue itself has a sequence table , If you use the structure of the array to store the data of the queue , The declaration of the queue array is shown in the figure below , among maxSize Is the name of the queue The maximum capacity .
• Because the output of the queue 、 Input is processed from the front and back end respectively , So we need two variables front And rear Record the queue separately Subscripts at the front and back ends ,front Will change with data output , and rear It changes with data input , As shown in the figure :

Code

Notes have ideas to explain ~

package com.atguigu.queue;

import java.util.Scanner;

//author qij
public class ArrayQueueDemo {
    

	public static void main(String[] args) {
    
		// Test one 
		// Create a queue 
		ArrayQueue queue = new ArrayQueue(3);
		char key = ' '; // Receive user input 
		Scanner scanner = new Scanner(System.in);//
		boolean loop = true;
		// Output a menu 
		while(loop) {
    
			System.out.println("s(show):  Show queue ");
			System.out.println("e(exit):  Exit procedure ");
			System.out.println("a(add):  Add data to the queue ");
			System.out.println("g(get):  Take data out of the queue ");
			System.out.println("h(head):  View the data of the queue header ");
			key = scanner.next().charAt(0);// Receive a character 
			switch (key) {
    
			case 's':
				queue.showQueue();
				break;
			case 'a':
				System.out.println(" Output a number ");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case 'g': // Take out the data 
				try {
    
					int res = queue.getQueue();
					System.out.printf(" The data is %d\n", res);
				} catch (Exception e) {
    
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'h': // View the data of the queue header 
				try {
    
					int res = queue.headQueue();
					System.out.printf(" The data in the queue header is %d\n", res);
				} catch (Exception e) {
    
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e': // sign out 
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		
		System.out.println(" Program exit ~~");
	}

}

//  Use arrays to simulate queues - Write a ArrayQueue class 
class ArrayQueue {
    
	private int maxSize; //  Represents the maximum capacity of an array 
	private int front; //  Queue header 
	private int rear; //  Queue tail 
	private int[] arr; //  This data is used to store data ,  Simulation queue 

	//  The constructor that creates the queue 
	public ArrayQueue(int arrMaxSize) {
    
		maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = -1; //  Point to the head of the queue , Analysis shows that front It points to the previous position of the queue head .
		rear = -1; //  At the end of the queue , Data pointing to the end of the queue ( That is, the last data in the queue )
	}

	//  Determine if the queue is full 
	public boolean isFull() {
    
		return rear == maxSize - 1;
	}

	//  Determines if the queue is empty 
	public boolean isEmpty() {
    
		return rear == front;
	}

	//  Add data to the queue 
	public void addQueue(int n) {
    
		//  Determine if the queue is full 
		if (isFull()) {
    
			System.out.println(" The queue is full , Can't add data ~");
			return;
		}
		rear++; //  Give Way rear  Move backward 
		arr[rear] = n;
	}

	//  Get the data of the queue ,  Outgoing queue 
	public int getQueue() {
    
		//  Determine whether the queue is empty 
		if (isEmpty()) {
    
			//  By throwing an exception 
			throw new RuntimeException(" The queue is empty , Can't get data ");
		}
		front++; // front Move backward 
		return arr[front];

	}

	//  Show all data in the queue 
	public void showQueue() {
    
		//  Traverse 
		if (isEmpty()) {
    
			System.out.println(" The queue is empty , No data ~~");
			return;
		}
		for (int i = 0; i < arr.length; i++) {
    
			System.out.printf("arr[%d]=%d\n", i, arr[i]);
		}
	}

	//  Display the header data of the queue ,  Be careful not to take out the data 
	public int headQueue() {
    
		//  Judge 
		if (isEmpty()) {
    
			throw new RuntimeException(" The queue is empty , No data ~~");
		}
		return arr[front + 1];
	}
}

Optimize

Circulable array , The tail is full , loop , Add... To the head

The above code , The queue is full To Queue out , Only support Disposable The operation of , use Ring array To optimize

package com.atguigu.queue;

import java.util.Scanner;

//author qij
public class CircleArrayQueueDemo {
    

	public static void main(String[] args) {
    
		
		// Test one 
		System.out.println(" Test array simulation ring queue case ~~~");
		
		//  Create a circular queue 
		CircleArray queue = new CircleArray(4); // Description settings 4,  The maximum valid data of its queue is 3
		char key = ' '; //  Receive user input 
		Scanner scanner = new Scanner(System.in);//
		boolean loop = true;
		//  Output a menu 
		while (loop) {
    
			System.out.println("s(show):  Show queue ");
			System.out.println("e(exit):  Exit procedure ");
			System.out.println("a(add):  Add data to the queue ");
			System.out.println("g(get):  Take data out of the queue ");
			System.out.println("h(head):  View the data of the queue header ");
			key = scanner.next().charAt(0);//  Receive a character 
			switch (key) {
    
			case 's':
				queue.showQueue();
				break;
			case 'a':
				System.out.println(" Output a number ");
				int value = scanner.nextInt();
				queue.addQueue(value);
				break;
			case 'g': //  Take out the data 
				try {
    
					int res = queue.getQueue();
					System.out.printf(" The data is %d\n", res);
				} catch (Exception e) {
    
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'h': //  View the data of the queue header 
				try {
    
					int res = queue.headQueue();
					System.out.printf(" The data in the queue header is %d\n", res);
				} catch (Exception e) {
    
					// TODO: handle exception
					System.out.println(e.getMessage());
				}
				break;
			case 'e': //  sign out 
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println(" Program exit ~~");
	}

}


// Circulable array , The tail is full , loop , Add... To the head  >>>  use  %  modulus 
class CircleArray {
    
	private int maxSize; //  Represents the maximum capacity of an array 
	//front  Make an adjustment to the meaning of the variable ： front  Point to the first element of the queue ,  in other words  arr[front]  It's the first element of the queue  
	//front  The initial value of the  = 0
	private int front; 
	//rear  Make an adjustment to the meaning of the variable ：rear  Point to the last position of the last element in the queue .  Because I want to make a space as an agreement .
	//rear  The initial value of the  = 0
	private int rear; //  Queue tail 
	private int[] arr; //  This data is used to store data ,  Simulation queue 
	
	public CircleArray(int arrMaxSize) {
    
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}
	
	//  Determine if the queue is full 
	public boolean isFull() {
    
		return (rear  + 1) % maxSize == front;
	}
	
	//  Determines if the queue is empty 
	public boolean isEmpty() {
    
		return rear == front;
	}
	
	//  Add data to the queue 
	public void addQueue(int n) {
    
		//  Determine if the queue is full 
		if (isFull()) {
    
			System.out.println(" The queue is full , Can't add data ~");
			return;
		}
		//1、 Add data directly to 
		arr[rear] = n;
		//2、 take  rear  Move backward ,  Consider taking the mold （ The tail is full , Forward storage ）
		rear = (rear + 1) % maxSize;
	}
	
	//  Get the data of the queue ,  Outgoing queue 
	public int getQueue() {
    
		//  Determine whether the queue is empty 
		if (isEmpty()) {
    
			//  By throwing an exception 
			throw new RuntimeException(" The queue is empty , Can't get data ");
		}

		// 1.  The first  front  The corresponding value is kept in a temporary variable 
		int value = arr[front];
		// 2.  take  front  Move backward ,  Consider taking the mold （ The tail is full , Forward storage ）
		front = (front + 1) % maxSize;
		// 3.  Return the temporarily saved variable to 
		return value;

	}
	
	//  Show all data in the queue 
	public void showQueue() {
    
		//  Traverse 
		if (isEmpty()) {
    
			System.out.println(" The queue is empty , No data ~~");
			return;
		}
		//  Ideas ： from front To traverse the , How many elements to traverse 
		//  Use one's brains 
		for (int i = 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() {
    
		// rear = 2
		// front = 1
		// maxSize = 3 
		return (rear + maxSize - front) % maxSize;   
	}
	
	//  Display the header data of the queue ,  Be careful not to take out the data 
	public int headQueue() {
    
		//  Judge 
		if (isEmpty()) {
    
			throw new RuntimeException(" The queue is empty , No data ~~");
		}
		return arr[front];
	}
}