数据结构--java实现稀疏数组和队列

稀疏数组和队列

package use2;

/**
 * 数组实现队列，插入
 */
public class ArrayQueue {

    private int[] array;

    private int maxSize;

    private int frontPoint;

    private int rearPoint;


    public ArrayQueue(int maxSize){
        this.maxSize = maxSize;
        array  = new int[maxSize];

        frontPoint = -1;
        rearPoint = -1;

    }

    /**
     * 判断当前队列是否已满
     */
    public boolean isFull(){
        return rearPoint == maxSize-1;
    }

    /**
     * 判断是否是空队列
     */
    public boolean isEmpty(){
        return frontPoint == rearPoint;
    }

    /**
     * 添加元素进入队列
     */
    public void add(int n){
        //判断是否已满
        if (isFull()){
            System.out.println("队列已满");
            return;
        }
        rearPoint++;
        array[rearPoint] = n;
    }

    /**
     * 获取队列元素并且删除元素，出队列
     */
    public int get(){
        if (isEmpty()){
            throw new RuntimeException("空队列");
        }
        frontPoint++;
        return array[frontPoint];
    }

    /**
     * 查看队列中的元素
     */
    public void findQueue(){
        if (isEmpty()){
            throw new RuntimeException("空队列");
        }
        for (int i=0;i<array.length;i++){
            System.out.printf("array[%d]=%d\n",i,array[i]);
        }
    }

    /**
     * 查看队头元素，不能是出队列
     */
    public int frontQueue(){
        if (isEmpty()){
            throw new RuntimeException("空队列");
        }
        return array[frontPoint+1];
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86

package use2;


public class SparseArray {

    public static void main(String[] args) {

        /**
         * 1.模拟出来棋盘数据，使用二维数组
         */
        int[][] array = new int[11][11];
        array[1][2] = 1;
        array[2][4] = 2;

        //打印棋盘查看效果
        for (int[] row :array){
            for (int val :row){
                System.out.printf("%d\t",val);
            }
            System.out.println();
        }

        /**
         * 需要把如上的二维数组中有效数据压缩至稀疏数组中去
         */
        //计算二维数组中有效数据
        int sum = 0;
        for (int i=0;i<11;i++){
            for (int j=0;j<11;j++){
                if (array[i][j] !=0){
                    sum++;
                }
            }
        }

        //定义稀疏数组
        int [][] sparseArray = new int[sum+1][3];
        sparseArray[0][0] = 11;//行
        sparseArray[0][1] = 11;//列
        sparseArray[0][2] = sum;//有效数据个数

        //把有效数据存放至稀疏数组中去
        int count= 0;
        for(int i=0;i<11;i++){//行的索引
            for (int j=0;j<11;j++){//列的索引
                //判断是否是有效数据
                if (array[i][j] !=0){
                    count++;
                    sparseArray[count][0] = i;
                    sparseArray[count][1] = j;
                    sparseArray[count][2] = array[i][j];
                }
            }
        }

        /**
         * 打印稀疏数组
         */
        for (int i=0;i<sparseArray.length;i++){
            System.out.printf("%d,%d,%d\t",sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
        }


        /**
         * 把稀疏数组转原始二维数组（面试题）
         */

        int[][] oldArray = new int[sparseArray[0][0]][sparseArray[0][1]];

        for (int i=1;i<=count;i++){
            oldArray[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
        }

        System.out.println("---------------------------------------------------");

        /**
         * 原始二维数组棋盘
         */
        for (int[] row:oldArray){
            for (int val:row){
                System.out.printf("%d\t",val);
            }
            System.out.println();
        }


    }


}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90

package use2;

public class TestApp {
    public static void main(String[] args) {

        ArrayQueue arrayQueue = new ArrayQueue(5);
        arrayQueue.add(1);
        arrayQueue.add(2);
        arrayQueue.add(3);
        arrayQueue.add(4);
        arrayQueue.add(5);


        int i = arrayQueue.get();
        System.out.println(i);


        arrayQueue.findQueue();



    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24