稀疏数组与队列

1.稀疏数组与队列

1.1 稀疏数组

介绍：

• 记录数组一共有几行，有多少个不同的值
• 把具有不同值的元素的行列及值记录在一个小规模的数组中，从而缩小程序的规模

分析问题：二维数组的很多值默认为0，记录了很多没有意义的数据 --> 转为稀疏数组

稀疏数组

分析思路：

二维数组转稀疏数组
1.遍历原始二维数组，得到有效数据的个数sum
2.根据sum创建稀疏数组 sparseArr[sum+1][3]
3.将二维数组的有效数据存入到稀疏数组
4.将稀疏数组以文件形式存于磁盘

稀疏数组转二维数组
1.读取磁盘文件
2.根据稀疏数组的第一行数据创建二维数组，如上图 chessArr = int[11][11]
3.在读取稀疏数组后几行的数据，并赋值给二维数组即可

代码实现：

package sparsearray;

import java.io.*;

public class SparseArray {
    //棋盘行数
    private static final int ROWS = 11;
    //棋盘列数
    private static final int COLUMNS = 11;
    //二维数组
    static int[][] chessArr = new int[ROWS][COLUMNS];
    //黑子和白字之和
    private static int sum = 0;

    /**
     * 打印二维数组
     *
     * @param chessArr
     */
    public static void printArr(int[][] chessArr) {
        System.out.println("二维数组");
        for (int[] row : chessArr) {
            for (int data : row) {
                System.out.printf("%d\t", data);
            }
            System.out.println();
        }
    }

    /**
     * 二维数组转稀疏数组
     *
     * @param chessArr
     * @return
     */
    public static int[][] chessArr2SparesArr(int[][] chessArr) {
        //求黑子和白子的总数
        for (int[] row : chessArr) {
            for (int data : row) {
                if (data != 0) {
                    sum++;
                }
            }
        }

        //创建稀疏数组
        int[][] sparseArr = new int[sum + 1][3];
        sparseArr[0][0] = ROWS;
        sparseArr[0][1] = COLUMNS;
        sparseArr[0][2] = sum;
        int count = 0;
        //遍历二维数组，将不为0的值填入稀疏数组
        for (int i = 0; i < ROWS; i++) {
            for (int j = 0; j < COLUMNS; j++) {
                if (chessArr[i][j] != 0) {
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = chessArr[i][j];
                }
            }
        }
        return sparseArr;
    }

    /**
     * 稀疏数组转二维数组
     *
     * @param sparseArr
     * @return
     */
    public static int[][] sparseArr2chessArr(int[][] sparseArr) {
        int[][] chessArr = new int[sparseArr[0][0]][sparseArr[0][1]];
        for (int i = 1; i < sparseArr.length; i++) {
            chessArr[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        return chessArr;
    }

    /**
     * 保存数组
     *
     * @param sparseArr 需要保存的数组
     * @param fileName  文件名
     */
    public static void saveArr2File(int[][] sparseArr, String fileName) {
        File file = new File(fileName);
        FileWriter out = null;
        try {
            out = new FileWriter(file);
            //将稀疏数组中的数据存入文件
            for (int i = 0; i < sparseArr.length; i++) {
                out.write(sparseArr[i][0] + "\t" + sparseArr[i][1] + "\t" + sparseArr[i][2] + "\r\n");
            }
            System.out.println("文件保存成功！");
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                out.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
    }

    /**
     * 从文件读取数组
     *
     * @param fileName
     * @return
     */
    public static int[][] readArrFromFile(String fileName) {
        //从文件中读取稀疏数组
        BufferedReader in = null;
        int[][] sparseArr = new int[sum + 1][3];
        try {
            in = new BufferedReader(new FileReader(fileName));
            String line;
            int row = 0;
            while ((line = in.readLine()) != null) {
                String[] temp = line.split("\t");
                sparseArr[row][0] = Integer.valueOf(temp[0]);
                sparseArr[row][1] = Integer.valueOf(temp[1]);
                sparseArr[row][2] = Integer.valueOf(temp[2]);
                row++;
            }
        } catch (Exception e) {
            e.printStackTrace();
        } finally {
            try {
                in.close();
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return sparseArr;
    }

    public static void main(String[] args) throws InterruptedException {
        chessArr[1][2] = 1;
        chessArr[2][3] = 2;
        printArr(chessArr);
        int[][] parseArr = chessArr2SparesArr(chessArr);
        printArr(parseArr);
        saveArr2File(parseArr, "test.data");
        Thread.sleep(1);
        int[][] parseArr2 = readArrFromFile("test.data");
        printArr(parseArr2);
        chessArr = sparseArr2chessArr(parseArr2);
        printArr(chessArr);
    }

}

1.2 队列

介绍：

• 队列是一个有序列表，可以用数组或链表来实现
• 遵循先入先出的原则。即：先存入队列的数据先取出，后存入的数据后取出

1.2.1 数组队列

分析问题：使用数组实现数据存储，先入先出

队列

分析思路：

1.队列本身是有序列表，若使用数组结构存储队列数据，则数组的声明如上图，MaxSize是该队列的最大容量
2.因为队列的输入、输出是从前后端来处理，需要两个变量front及rear来记录队列前后端的下标，front会随着数据输出而改变，rear随着数据输入而改变
3.front变量指向队列第一个元素的前一位，初始值=-1
4.rear变量指向队列最后一个元素，初始值=-1
5.当队列存入数据时，
    (1)判断队列是否已满：rear == MaxSize - 1 ?
    (2)将尾指针往后移一位：rear+1;
6.当队列取数据时，
    (1)判断队列是否为空：rear == front ?
    (2)将头指针往后移一位：front+1;

代码实现：

package queue;

import java.util.Scanner;

/**
 * 数组使用一次就没用了，没有达到复用效果
 */
public class ArrayQueueDemo {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        ArrayQueue queue = new ArrayQueue(3);
        char option = ' ';
        boolean loop = true;
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            option = scanner.next().charAt(0);
            switch (option) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入需要添加的数据：");
                    int vaule = scanner.nextInt();
                    queue.addQueue(vaule);
                    break;
                case 'g':
                    try {
                        int value = queue.getQueue();
                        System.out.println("取出的数据为：" + value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h':
                    try {
                        int value = queue.headQueue();
                        System.out.println("队列头数据为：" + value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'e':
                    loop = false;
                    scanner.close();
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出！");
    }

}

class ArrayQueue {
    //最大容量
    private int maxSize;
    //队列头，指向第一个元素的前一个位置，初始值为-1
    private int front;
    //队列尾，指向最后一个元素的位置，初始值为-1
    private int rear;
    //用于存放数据
    private int[] arr;

    //构造方法
    public ArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
        this.front = -1;
        this.rear = -1;
    }

    /**
     * 判断是否满了
     *
     * @return
     */
    public boolean isFull() {
        return rear == maxSize - 1;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return front == rear;
    }

    /**
     * 添加队列
     *
     * @param n
     */
    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满，无法添加！");
            return;
        }
        rear++;
        arr[rear] = n;
    }

    /**
     * 获取队列
     *
     * @return
     */
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据！");
        }
        front++;
        return arr[front];
    }

    /**
     * 显示队列
     */
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

    /**
     * 获取头数据,不是取出数据
     *
     * @return
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据！");
        }
        return arr[front + 1];
    }
}

1.2.2 环形队列

分析问题：

• 数组队列只能使用一次，不能复用；
• 将数组队列使用算法，改进成一个环形队列，取模：%

队列

分析思路：

1.尾索引的下一个为头索引时，表示队列已满，即将队列容量空出一位作为约定
2.front变量指向队列的第一个元素，初始值=0
3.rear变量指向队列的最后一个元素的后一个位置，因为希望空出一位作为约定，初始值=0
4.当队列存入数据时，
    (1)判断队列是否已满：(rear+1) % MaxSize == front?
    (2)将尾指针往后移一位：rear = (rear + 1) % maxSize;
5.当队列取数据时，
    (1)判断队列是否为空：rear == front?
    (2)将头指针往后移一位：front = (front + 1) % maxSize;
6.队列中有效数据的个数：(rear + maxSize - front) % maxSize

代码实现：

package queue;

import java.util.Scanner;

public class CircleArrayQueueDemo {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        CircleArrayQueue queue = new CircleArrayQueue(4);
        char option = ' ';
        boolean loop = true;
        while (loop) {
            System.out.println("s(show): 显示队列");
            System.out.println("e(exit): 退出程序");
            System.out.println("a(add): 添加数据到队列");
            System.out.println("g(get): 从队列取出数据");
            System.out.println("h(head): 查看队列头的数据");
            option = scanner.next().charAt(0);
            switch (option) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("请输入需要添加的数据：");
                    int vaule = scanner.nextInt();
                    queue.addQueue(vaule);
                    break;
                case 'g':
                    try {
                        int value = queue.getQueue();
                        System.out.println("取出的数据为：" + value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'h':
                    try {
                        int value = queue.headQueue();
                        System.out.println("队列头数据为：" + value);
                    } catch (Exception e) {
                        e.printStackTrace();
                    }
                    break;
                case 'e':
                    loop = false;
                    scanner.close();
                    break;
                default:
                    break;
            }
        }
        System.out.println("程序退出！");
    }
}

class CircleArrayQueue {
    //最大容量
    private int maxSize;
    //队列头,指向第一个元素位置,初始值为0
    private int front;
    //队列尾，指向最后一个元素的后一个位置,初始值为0
    private int rear;
    //用于存放数据
    private int[] arr;

    public CircleArrayQueue(int maxSize) {
        this.maxSize = maxSize;
        this.arr = new int[maxSize];
    }

    /**
     * 判断是否满了
     *
     * @return
     */
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return rear == front;
    }

    /**
     * 添加队列
     *
     * @param n
     */
    public void addQueue(int n) {
        if (isFull()) {
            System.out.println("队列已满，无法添加！");
            return;
        }
        arr[rear] = n;
        rear = (rear + 1) % maxSize;
    }

    /**
     * 获取队列
     *
     * @return
     */
    public int getQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据！");
        }
        int value = arr[front];
        front = (front + 1) % maxSize;
        return value;
    }

    /**
     * 显示队列
     */
    public void showQueue() {
        if (isEmpty()) {
            System.out.println("队列为空，没有数据");
            return;
        }
        for (int i = front; i < front + size(); i++) {
            System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i % maxSize]);
        }
    }

    /**
     * 获取有效元素个数
     *
     * @return
     */
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }

    /**
     * 获取头数据,不是取出数据
     *
     * @return
     */
    public int headQueue() {
        if (isEmpty()) {
            throw new RuntimeException("队列为空，没有数据！");
        }
        return arr[front];
    }
}