1. Sparse array

1.1 actual demand

• The Gobang program has the functions of saving, exiting and continuing the upper board
• Because many values of the two-dimensional array are the default value of 0, a lot of meaningless data are recorded. We turn it into a sparse array for storage

1.2. Sparse array application

1.2.1 sparse array processing method

• Sparse array records the rows, columns and values of elements with different values in a small-scale array, so as to reduce the scale of the program
• Sparse array is also a two-dimensional array. The number of rows is determined by the data of the original array, and the number of columns is generally 3 columns
• The first row of the sparse array records the total number of rows and columns of the original array, and how many non-zero values there are
  • First column: the number of rows of the original array
  • Second column: the number of columns of the original array
  • The third column: how many non-zero values does the original array have
• The subsequent rows record the number of rows and columns where the non-zero (x) value in the original array is located, as well as the value of X
  • First column: the number of rows of x in the original array
  • Second column: the number of columns of x in the original array
  • Column 3: value of x

1.2.2. Examples

• The original two-dimensional array is large, and the occupied space is reduced after compression

1.3 application examples

1.3.1 train of thought analysis

• Use a sparse array to preserve a two-dimensional array similar to the previous one (chessboard, map, etc.)
• Save the sparse array and restore the original number of two-dimensional arrays

1.3.2 code implementation

• code

public class SparseArray {

	public static void main(String[] args) {

		int chessArr1[][] = new int[11][11];
		chessArr1[1][2] = 1;
		chessArr1[2][3] = 2;
		chessArr1[4][5] = 2;

		System.out.println("Original two-dimensional array~~");
		for (int[] row : chessArr1) {
			for (int data : row) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}

		int sum = 0;
		for (int i = 0; i < chessArr1.length; i++) {
			for (int j = 0; j < chessArr1[i].length; j++) {
				if (chessArr1[i][j] != 0) {
					sum++;
				}
			}
		}

		int sparseArr[][] = new int[sum + 1][3];

		sparseArr[0][0] = chessArr1.length;
		sparseArr[0][1] = chessArr1[0].length;
		sparseArr[0][2] = sum;

		int count = 0;
		for (int i = 0; i < chessArr1.length; i++) {
			for (int j = 0; j < chessArr1[i].length; j++) {
				if (chessArr1[i][j] != 0) {
					count++;
					sparseArr[count][0] = i;
					sparseArr[count][1] = j;
					sparseArr[count][2] = chessArr1[i][j];
				}
			}
		}

		System.out.println();
		System.out.println("Get the sparse array as~~~~");
		for (int i = 0; i < sparseArr.length; i++) {
			System.out.printf("%d\t%d\t%d\n", sparseArr[i][0], sparseArr[i][1], sparseArr[i][2]);
		}
		System.out.println();

		int chessArr2[][] = new int[sparseArr[0][0]][sparseArr[0][1]];

		for (int i = 1; i < sparseArr.length; i++) {
			chessArr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
		}

		System.out.println();
		System.out.println("Restored 2D array");

		for (int[] row : chessArr2) {
			for (int data : row) {
				System.out.printf("%d\t", data);
			}
			System.out.println();
		}
	}

}

• Program running results

原始的二维数组~~
0	0	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	0
0	0	0	2	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	2	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

得到稀疏数组为~~~~
11	11	3
1	2	1
2	3	2
4	5	2

恢复后的二维数组
0	0	0	0	0	0	0	0	0	0	0
0	0	1	0	0	0	0	0	0	0	0
0	0	0	2	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	2	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0	0

1.4 after class exercises

• Based on the above, save the sparse array to disk, such as map data
• When restoring the original array, read the map Data recovery

2. Queue

2.1 queue usage scenario

• Cases of Bank Queuing:

2.2 queue introduction

• Queue is a sequential list, which can be realized by array or linked list.
• Follow the principle of first in first out, that is, the data stored in the queue should be taken out first, and the data stored later should be taken out later
• Schematic: (use array to simulate queue schematic)

2.3 array simulation queue

2.3.1 train of thought analysis

• maxSize: queue capacity (length of array)
• arr: array of simulated queues
• front: refers to the previous element of the queue header element, with an initial value of - 1
• rear: refers to the element at the end of the queue. The initial value is - 1

• basic operation
  • Queue: front = empty
  • Queue full: rear == (maxSize - 1), that is, whether the rear has pointed to the last position of the array
  • Number of queue elements: rear - front
  • Queue join: only when the queue is not satisfied can you join the queue, arr[++rear] = value
  • Queue exit: only when the queue is not empty can you exit the queue, return arr[front + +]

2.3.2 code implementation

• Definition of queue

class ArrayQueue {
	private int maxSize;
	private int front;
	private int rear;
	private int[] arr;

	public ArrayQueue(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
		front = -1;
		rear = -1;
	}

	public boolean isFull() {
		return rear == maxSize - 1;
	}

	public boolean isEmpty() {
		return rear == front;
	}

	public void addQueue(int n) {

		if (isFull()) {
			System.out.println("The queue is full and data cannot be added~");
			return;
		}
		rear++;
		arr[rear] = n;
	}

	public int getQueue() {

		if (isEmpty()) {

			throw new RuntimeException("The queue is empty and data cannot be retrieved");
		}
		front++;
		return arr[front];

	}

	public void showQueue() {

		if (isEmpty()) {
			System.out.println("The queue is empty and there is no data~~");
			return;
		}
		for (int i = front + 1; i  rear; i++) {

			System.out.printf("arr[%d]=%d\n", i, arr[i]);
		}
	}

	public int headQueue() {

		if (isEmpty()) {
			throw new RuntimeException("The queue is empty and there is no data~~");
		}
		return arr[front + 1];
	}
}

• Test code

public class ArrayQueueDemo {

	public static void main(String[] args) {

		ArrayQueue queue = new ArrayQueue(3);
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;

		while (loop) {
			System.out.println("s(show): Show queue");
			System.out.println("e(exit): Exit program");
			System.out.println("a(add): Add data to queue");
			System.out.println("g(get): Fetch data from queue");
			System.out.println("h(head): View the data of the queue header");
			System.out.println();
			key = scanner.next().charAt(0);
			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':
				try {
					int res = queue.getQueue();
					System.out.printf("The data taken out is%d\n", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res = queue.headQueue();
					System.out.printf("The data of the queue header is%d\n", res);
				} catch (Exception e) {
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}

		System.out.println("Program exit~~");
	}

}

• Program running results

s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

s
队列空的，没有数据~~
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

a
输出一个数
1
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

a
输出一个数
2
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

a
输出一个数
3
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

s
arr[0]=1
arr[1]=2
arr[2]=3
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

a
输出一个数
4
队列满，不能加入数据~
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

g
取出的数据是1
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

g
取出的数据是2
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

g
取出的数据是3
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

g
队列空，不能取数据
s(show): 显示队列
e(exit): 退出程序
a(add): 添加数据到队列
g(get): 从队列取出数据
h(head): 查看队列头的数据

2.4 array model ring queue

2.4.1 raising questions

• At present, the array cannot be used once, which does not achieve the effect of reuse, resulting in a waste of memory space
• Use the algorithm to improve this array into a ring queue (modulus:%)

2.4.2 train of thought analysis

• Optimize the front queue and transform it into a ring queue (realized by taking a module)
• maxSize: queue capacity (length of array)
• arr: array of simulated queues
• front: points to the queue header element, with an initial value of 0
• rear: refers to the last element at the end of the queue. The initial value is 0

• basic operation
  • Empty queue: front == rear
  • Queue full:
    • Why make space for an element available after the rear and before the front? Because if an element is not empty, the queue empty condition is: front == rear, and the queue full condition is also: front == rear, which is ambiguous!
    • Queue capacity: because an element is vacated, the queue capacity becomes (maxSize - 1)
    • When the space of an element is vacated, how to judge the full space? When there is one element left, the queue is full, so the judgment condition is (rear + 1)% maxsize = = front
  • Number of queue elements:
    • Calculation formula: (rear + maxsize - front)% maxsize, think like this:
    • When the rear is larger than the front, (rear -front) > 0, the ring structure has not been formed at this time, (rear -front) is the number of queue elements
    • When the rear is smaller than the front, that is, (rear -front) < 0, a ring structure has been formed, (rear -front) indicates how many elements of the array are still full (negative), and (rear + maxSize - front) is the number of queue elements
    • To sum up: (rear + maxsize - front)% maxsize
  • Queue in:
    • First, only when the queue is dissatisfied can you join the team
    • Since rear points to the next element at the end of the queue, you can set it directly: arr[rear] = value
    • Next, the rear should be moved back one position: rear = (rear + 1)% maxsize
    • The purpose of modulo is to prevent the array from crossing the boundary and make the pointer return to the first element of the array
  • Queue out:
    • First, the queue cannot be empty before leaving the queue
    • Since the front directly points to the queue header element, you can directly return the element: int value = arr[front]
    • Next, front should be moved back one position: front = (front + 1)% maxsize
    • The purpose of modulo is to * prevent the array from crossing the boundary and let the pointer return to the first element of the array

2.4.3 code implementation

• Implementation of ring queue

class CircleArray {
	private int maxSize;

	private int front;

	private int rear;
	private int[] arr;

	public CircleArray(int arrMaxSize) {
		maxSize = arrMaxSize;
		arr = new int[maxSize];
	}

	public boolean isFull() {
		return (rear + 1) % maxSize == front;
	}

	public boolean isEmpty() {
		return rear == front;
	}

	public void addQueue(int n) {

		if (isFull()) {
			System.out.println("The queue is full and data cannot be added~");
			return;
		}

		arr[rear] = n;

		rear = (rear + 1) % maxSize;
	}

	public int getQueue() {

		if (isEmpty()) {

			throw new RuntimeException("The queue is empty and data cannot be retrieved");
		}

		int value = arr[front];
		front = (front + 1) % maxSize;
		return value;

	}

	public void showQueue() {

		if (isEmpty()) {
			System.out.println("The queue is empty and there is no data~~");
			return;
		}

		for (int i = front; i < front + size(); i++) {
			System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
		}
	}

	public int size() {

		return (rear + maxSize - front) % maxSize;
	}

	public int headQueue() {

		if (isEmpty()) {
			throw new RuntimeException("The queue is empty and there is no data~~");
		}
		return arr[front];
	}
}

• Test code

public class CircleArrayQueueDemo {

	public static void main(String[] args) {

		System.out.println("Test array simulation ring queue case~~~");

		CircleArray queue = new CircleArray(4);
		char key = ' ';
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;

		while (loop) {
			System.out.println("s(show): Show queue");
			System.out.println("e(exit): Exit program");
			System.out.println("a(add): Add data to queue");
			System.out.println("g(get): Fetch data from queue");
			System.out.println("h(head): View data of queue header");
			System.out.println();
			key = scanner.next().charAt(0);
			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':
				try {
					int res = queue.getQueue();
					System.out.printf("The data taken out is%d\n", res);
				} catch (Exception e) {

					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res = queue.headQueue();
					System.out.printf("The data of the queue header is%d\n", res);
				} catch (Exception e) {

					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("Program exit~~");
	}

}

• Program running results

Test array simulation ring queue case~~~
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View data of queue header

a
 Output a number
1
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View data of queue header

a
 Output a number
2
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View data of queue header

a
 Output a number
3
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View data of queue header

s
arr[0]=1
arr[1]=2
arr[2]=3
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View data of queue header

a
 Output a number
4
 The queue is full and data cannot be added~
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View data of queue header

g
 The extracted data is 1
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View the data of the queue header

g
 The extracted data is 2
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View the data of the queue header

s
arr[2]=3
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View the data of the queue header

g
 The extracted data is 3
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View the data of the queue header

g
 The queue is empty and data cannot be retrieved
s(show): Show queue
e(exit): Exit program
a(add): Add data to queue
g(get): Fetch data from queue
h(head): View the data of the queue header