Part I: Data structure and algorithm sparse sparsearray array

The main contents mentioned above:

• Save sparse arrays to disk, such as map data
• When restoring the original array, read the map Data for recovery

Data structure and algorithm - queue

1. Application scenario and introduction of queue

scene

Case of Bank Queuing

Queue introduction

• Queue is a sequential list, which can be implemented 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. After the deposit, it shall be taken out

Using arrays to simulate queue footprints

2. Analysis of array simulation queue

• The queue itself has a sequence table. If the array structure is used to store the data of the queue, the declaration of the queue array is shown in the figure below, where maxSize is the maximum capacity of the queue
• Because the output and input of the queue are processed from the front and rear ends respectively, two variables front and rear are required to record the subscripts at the front and rear ends of the queue respectively. The front will change with the data output, while the rear will change with the data input

As shown in the figure

Array emulation queue

When we put data into a queue, it is called "addQueue"

Train of thought analysis

The processing of addQueue requires two steps

• Move the tail pointer backward: rear+1, when front == rear [empty]
• If the tail pointer rear is less than the maximum subscript maxSize-1 of the queue, the data will be stored in the array element referred to by rear, otherwise the data cannot be stored. Rear = = maxSize - 1 [queue full]

3. Array simulation queue code implementation

Code implementation:

package com.code.queue;

import java.util.Scanner;

/**
 * Array simulation queue code implementation
 */
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 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");
            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': //Fetch data
                    try {
                        int res = queue.getQueue();
                        System.out.printf("The extracted data is%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': //View data of 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 an ArrayQueue class
class ArrayQueue {
    private int maxSize; // Represents the maximum capacity of the array
    private int front; // Queue header
    private int rear; // Queue tail
    private int[] arr; // This data is used to store data and simulate the queue

    // Constructor to create a queue
    public ArrayQueue(int arrMaxSize) {
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; // Point to the queue header and analyze that front is the previous position pointing to the queue header
        rear = -1; // Data pointing to the end of the queue (that is, the last data of the queue)
    }

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

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

    // Add data to queue
    public void addQueue(int n) {
        // Determine whether the queue is full
        if (isFull()) {
            System.out.println("The queue is full and data cannot be added~");
            return;
        }
        rear++; // Move rear
        arr[rear] = n;
    }

    // Get the data of the queue and get out of the queue
    public int getQueue() {
        // Judge whether the queue is empty
        if (isEmpty()) {
            // By throwing an exception
            throw new RuntimeException("The queue is empty and data cannot be retrieved");
        }
        front++; // front backward
        return arr[front];

    }

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

    // The header data of the queue is displayed. Note that it is not taken out
    public int headQueue() {
        // judge
        if (isEmpty()) {
            throw new RuntimeException("The queue is empty and there is no data~~");
        }
        return arr[front + 1];
    }

}

Test printout:

E:\Development_Tool_Library\JDK\Installation_Directory\bin\java.exe "-javaagent:E:\Development_Tool_Library\IDEA2021\Installation_Directory\IntelliJ IDEA 2020.3.4\lib\idea_rt.jar=54373:E:\Development_Tool_Library\IDEA2021\Installation_Directory\IntelliJ IDEA 2020.3.4\bin" -Dfile.encoding=UTF-8 -classpath E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\charsets.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\deploy.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\access-bridge-64.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\cldrdata.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\dnsns.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\jaccess.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\jfxrt.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\localedata.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\nashorn.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunec.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunjce_provider.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunmscapi.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunpkcs11.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\zipfs.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\javaws.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jce.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jfr.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jfxswt.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jsse.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\management-agent.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\plugin.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\resources.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\rt.jar;E:\TestDemo\Algorithm_Code\target\classes com.code.queue.ArrayQueueDemo
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
 The queue is empty and there is no data~~
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
10
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]=10
arr[1]=0
arr[2]=0
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
20
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]=10
arr[1]=20
arr[2]=0
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
30
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]=10
arr[1]=20
arr[2]=30
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
40
 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
h
 The data in the queue header is 10
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 10
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
h
 The data of the queue header is 20
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 20
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 30
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 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 data of queue header

There is a problem in the test of the above program, for example, it can not be reused in adding data to the queue

Array emulation queue

• Out of queue operation getQueue
• Show the status of the queue showQueue
• View the queue header element headQueue
• Exit system exit

4. Analysis of array simulation ring queue

Analysis of using array to simulate ring queue

The idea is as follows:

• Adjust the meaning of the front variable: front points to the first element of the queue, that is, arr[front] is the first element of the queue, and the initial value of front = 0
• Adjust the meaning of the rear variable: rear points to the next position of the last element of the queue Because I want to make a space as an agreement Initial value of rear = 0
• When the queue is full, the condition is (rear + 1)% maxsize = = front [Full]
• For the condition that the queue is empty, rear == front is empty
• When we analyze this way, the number of valid data in the queue (rear + maxsize - front)% maxsize / / rear = 1, front = 0
• We can modify the original queue to get a ring queue

5. Array simulation ring queue implementation

It is mainly to solve the problem that the array simulation queue cannot be reused when adding data to the queue

Code implementation:

package com.code.queue;

/**
 * Array simulation ring queue implementation
 */
import java.util.Scanner;

public class CircleArrayQueueDemo {

    public static void main(String[] args) {

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

        // Create a ring queue
        CircleArray queue = new CircleArray(4); //Description set 4, and 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 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");
            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': // Fetch data
                    try {
                        int res = queue.getQueue();
                        System.out.printf("The extracted data is%d\n", res);
                    } catch (Exception e) {
                        // TODO: handle exception
                        System.out.println(e.getMessage());
                    }
                    break;
                case 'h': // View data of 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~~");
    }

}


class CircleArray {
    private int maxSize; // Represents the maximum capacity of the array
    //Adjust the meaning of the front variable: front points to the first element of the queue, that is, arr[front] is the first element of the queue
    //Initial value of front = 0
    private int front;
    //Adjust the meaning of the rear variable: rear points to the next position of the last element of the queue Because I want to make a space as an agreement
    //Initial value of rear = 0
    private int rear; // Queue tail
    private int[] arr; // This data is used to store data and simulate the queue

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

    // 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) {
        // Determine whether the queue is full
        if (isFull()) {
            System.out.println("The queue is full and data cannot be added~");
            return;
        }
        //Add data directly
        arr[rear] = n;
        //Move the rear, and here you must consider taking the mold
        rear = (rear + 1) % maxSize;
    }

    // Get the data of the queue and get out of the queue
    public int getQueue() {
        // Judge whether the queue is empty
        if (isEmpty()) {
            // By throwing an exception
            throw new RuntimeException("The queue is empty and data cannot be retrieved");
        }
        // Here, we need to analyze that front is the first element pointing to the queue
        // 1. First keep the value corresponding to front to a temporary variable
        // 2. Move the front backward and consider taking the mold
        // 3. Return temporarily saved variables
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;

    }

    // Displays all data for the queue
    public void showQueue() {
        // ergodic
        if (isEmpty()) {
            System.out.println("The queue is empty and there is no data~~");
            return;
        }
        // Idea: start traversing from front, and how many elements are traversed
        // Use your head
        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;
    }

    // The header data of the queue is displayed. Note that it is not taken out
    public int headQueue() {
        // judge
        if (isEmpty()) {
            throw new RuntimeException("The queue is empty and there is no data~~");
        }
        return arr[front];
    }
}

Test, printout

E:\Development_Tool_Library\JDK\Installation_Directory\bin\java.exe "-javaagent:E:\Development_Tool_Library\IDEA2021\Installation_Directory\IntelliJ IDEA 2020.3.4\lib\idea_rt.jar=56817:E:\Development_Tool_Library\IDEA2021\Installation_Directory\IntelliJ IDEA 2020.3.4\bin" -Dfile.encoding=UTF-8 -classpath E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\charsets.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\deploy.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\access-bridge-64.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\cldrdata.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\dnsns.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\jaccess.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\jfxrt.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\localedata.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\nashorn.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunec.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunjce_provider.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunmscapi.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\sunpkcs11.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\ext\zipfs.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\javaws.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jce.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jfr.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jfxswt.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\jsse.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\management-agent.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\plugin.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\resources.jar;E:\Development_Tool_Library\JDK\Installation_Directory\jre\lib\rt.jar;E:\TestDemo\Algorithm_Code\target\classes com.code.queue.CircleArrayQueueDemo
 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
s
 The queue is empty and there is no data~~
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
10
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]=10
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
20
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]=10
arr[1]=20
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
30
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]=10
arr[1]=20
arr[2]=30
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
40
 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 10
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[1]=20
arr[2]=30
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
30
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[1]=20
arr[2]=30
arr[3]=30
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
70
 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 20
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 30
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 30
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 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 data of queue header
a
 Output a number
50
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
60
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]=50
arr[1]=60
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
70
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
90
 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
s
arr[0]=50
arr[1]=60
arr[2]=70
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 50
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[1]=60
arr[2]=70
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
100
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[1]=60
arr[2]=70
arr[3]=100
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