二、稀疏数组和队列

稀疏数组

1、基本介绍

当一个数组中大部分元素为0，或者为同一个值的数组时，可以用稀疏数组来保存该数组。

2、处理方式

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

3、思路分析

3.1 二维数组转稀疏数组的思路

• 遍历原始二维数组，得到有效数据的个数sum
• 根据sum创建稀疏数组 int sparseArray[][] = new int[sum + 1][3];(稀疏数组固定是3列)
• 将二维数组中的有效数据存放到稀疏数组中

3.2 稀疏数组转原始二维数组思路

• 读取稀疏数组第一行数据，根据第一行数据创建原始数组，如：int chessArr[][] = new int[11][11];
• 再读取稀疏数组后几行的数据，赋值给原始二维数组即可

4、代码实现

public class SparseArray {

	public static void main(String[] args) {
		//创建一个原始的二维数组 11*11
		//0 表示没有棋子 1 表示黑子 2表示蓝子
		int chessArr[][] = new int[11][11];
		chessArr[1][2] = 1;
		chessArr[2][3] = 2;
		System.out.println("====原始的二维数组====");
		printArray(chessArr);
		
		//将二维数组 转 稀疏数组
		//1、先遍历二维数组，得到非零数据的个数
		int sum = 0;
		for (int i = 0; i < chessArr.length; i++) {
			for (int j = 0; j < chessArr.length; j++) {
				if (chessArr[i][j] != 0) {
					sum++;
				}
			}
		}
		System.out.println("sum = " + sum);
		
		//2、创建对应的稀疏数组 (3列是固定的)
		int sparseArray[][] = new int[sum + 1][3];
		//给稀疏数组赋值
		sparseArray[0][0] = 11;
		sparseArray[0][1] = 11;
		sparseArray[0][2] = sum;
		
		//3、遍历数组，将非0的值放在sparseArray中
		int count = 0;//用于记录是第几个非0数据
		for (int i = 0; i < chessArr.length; i++) {
			for (int j = 0; j < chessArr.length; j++) {
				if (chessArr[i][j] != 0) {
					count++;
					sparseArray[count][0] = i;
					sparseArray[count][1] = j;
					sparseArray[count][2] = chessArr[i][j];
				}
			}
		}
		System.out.println("====得到的稀疏数组====");
		for (int i = 0; i < sparseArray.length; i++) {
			System.out.printf("%d\t%d\t%d\t\n", sparseArray[i][0],sparseArray[i][1],sparseArray[i][2]);
		}
		System.out.println();
		
		//将稀疏数组 转 原始二维数组
		// 1.先读取稀疏数组的第一行，根据第一行的数据，创建原始的二维数组
		int[][] chessArr2 = new int[sparseArray[0][0]][sparseArray[0][1]];
		
		// 2.读取稀疏数组的后几行数据（从第二行开始），并复制给原始的二维数组即可
		for (int i = 1; i < sparseArray.length; i++) {
			chessArr2[sparseArray[i][0]][sparseArray[i][1]] = sparseArray[i][2];
		}
		// 3.输出恢复后的二维数组
		 System.out.println("====恢复后的二维数组====");
	        printArray(chessArr2);
	}
	
	public static void  printArray(int[][] array) {
		for (int[] row : array) {
			for (int data : row) {
				System.out.printf("%d\t",data);
			}
			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

输出结果如下：

原始的二维数组
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 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 0
sum = 2
得到的稀疏数组
11 11 2
1 2 1
2 3 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 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 0

练习

1. 在代码实现的的基础上，将稀疏数组保存到磁盘上，比如map.data
2. 恢复原来的数组，读取map.data进行恢复

/**
     * 存储稀疏数组，相邻数据使用\t划分
     * @param path 文件的存放路径
     * @param sparseArr 稀疏数组对象
     */
	public static void save(String path,int[][] sparseArr) {
		FileWriter fileWriter = null;
		try {
			fileWriter = new FileWriter(path);
			for (int[] row : sparseArr) {
				fileWriter.write(row[0]+"\t" + row[1] + "\t" + row[2]);
				fileWriter.write("\r\n");
			}
		} catch (IOException e) {
			e.printStackTrace();
		}finally {
			try {
				fileWriter.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
	/**
     * 读取二维稀疏数组，相邻数据使用\t划分
     * @param path 文件的存放路径
     * @return 二维的稀疏数组
     */
	public static void read(String path) {
		int[][] sparseArr = null;
		BufferedReader bufferedReader = null;
		try {
			bufferedReader = new BufferedReader(new FileReader(path));
			String lineStr = null;
			int lineCount = 0;
			while ((lineStr = bufferedReader.readLine()) != null ) {
				String[] tempStr = lineStr.split("\t");
				if (lineCount == 0) {
					// 稀疏数组的[0,2]位置记录了非0数据个数，所以稀疏数组大小为[Integer.parseInt(tempStr[2]) + 1][3]
					sparseArr = new int[Integer.parseInt(tempStr[2] ) +1 ][3];
				}
				sparseArr[lineCount][0] =Integer.parseInt(tempStr[0]); 
				sparseArr[lineCount][1] =Integer.parseInt(tempStr[1]); 
				sparseArr[lineCount][2] =Integer.parseInt(tempStr[2]); 
				lineCount++;
			}
		} catch (Exception e) {
			e.printStackTrace();
		}finally {
			try {
				bufferedReader.close();
			} catch (IOException e) {
				e.printStackTrace();
			}
		}
	}
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

队列

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

1、数组模拟队列

• 队列本身也是有序列表，若使用数组的结构来存储队列的数据，则队列数组的声明如下图，其中MaxSize为队列的最大容量
• 因为队列的输出输入是分别从前后端来处理，因此需要两个变量front和rear分别记录前后端的下标，front会随着数据输出而改变，而rear会随着数据输入而改变
  当我们将数据存入队列时称为”addQueue”，addQueue 的处理需要有两个步骤：思路分析

1. 将尾指针往后移：rear + 1 , 当 rear==front 【空】
2. 若尾指针 rear 小于队列的最大下标 MaxSize-1，则将数据存入 rear 所指的数组元素中，否则无法存入数据。 reatr==MaxSize - 1[队列满]

注：rear是队列最后（含）， front是队列最前（不含）

2、代码实现

public class ArrayQueueDemo {

	public static void main(String[] args) {
		//创建一个队列
		ArrayQueue arrayQueue = new ArrayQueue(3);
		char key = ' ';// 接受用户输入
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		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):查看队列头的数据");
		while (loop) {
			key = scanner.next().charAt(0);// 接收第一个字符
			switch (key) {
			case 's':
				arrayQueue.showQueue();
				break;
			case 'a':
				System.out.println("输入一个数:");
				int value = scanner.nextInt();
				arrayQueue.addQueue(value);
				break;
			case 'g':
				try {
					int res = arrayQueue.getQueue();
					System.out.printf("取出的数据是%d\n", res);
					continue;
				} catch (RuntimeException e){
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res = arrayQueue.headQueue();
					System.out.printf("队列头的数据是%d\n", res);
				} catch (RuntimeException e){
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;

			default:
				break;
			}
		}
		System.out.println("程序退出");
	}
}

class ArrayQueue{
	private int maxSize;//表示数组的最大容量
	private int front; //队列头
	private int rear; //队列尾
	private int[] arr; //该数组用于存放数据，模拟队列

	public ArrayQueue(int maxSize) {
		this.maxSize = maxSize;
		arr = new int[maxSize];
		front = -1;// 指向队列头部,指向队列头部的数据的前一个位置
		rear = -1; // 指向队列尾，指向队列尾部的数据
	}

	/**
	 * 判断队列是否满
	 * @return
	 */
	public boolean isFull() {
		// 例如最大容量为5，rear是指向队列尾部数据，所以rear为4（maxSize - 1）的时候就为满了
		return rear == maxSize -1;
	}

	/**
	 * 判断队列是否为空
	 * @return
	 */
	public boolean isEmpty() {
		// 因为不是循环队列，头尾不相连,所以rear == front 时队列就为空
		return rear == front;
	}

	/**
	 * 添加数据到队列
	 * @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
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

4、此种实现方式存在缺陷和优化方案

• 数组使用一次就不能使用了，没有达到复用的效果
• 使用算法，改成一个环形的队列：取模%

环形队列

1、声明与结论

• front指向队列的头部元素，也就是说arr[front]就是队列的第一个元素，front的初始值为0
• rear指向队列的尾部元素的后一个位置，因为希望空出一个空间做为约定，rear的初始值为0
• 当队列满时，条件是 (rear +1) % maxSize= front 【满】
• 对队列为空的条件，rear == front 【空
• 队列中有效的数据的个数 (rear + maxSize - front) % maxSize 【rear=1 front=0，元素个数为1

2、结论分析

疑问：当空队列时，front等于rear，现在队列满时，也是front等于rear，那么如何判断此时的队列是空还是满呢？

办法1：设置一个标志变量flag。当front == rear，且flag = 0时队列为空，当front == rear，且flag = 1时队列为满。
办法2：当队列为空时，条件就是front == rear，当队列满时，我们保留一个元素空间，这样数组中还有一个空闲单元。如图1：

图1 图2 图3

我们重点来讨论一下第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是（rear+1）%QueueSize == front（取模“%”的目的就是为了整合rear与front大小为一个问题）。比如图1，QueueSize = 5，front=0，而rear=4，（4+1）%5 = 0，所以此时队列满。再比如图2，front=2而rear=1，（1+1）%5 =2，所以此时队列也是满的。再比如图3，front=2，而rear=0，（0+1）%5 = 1,front ≠rear，所以此时队列并没有满。
另外，当rear>front时，即图1，此时队列的长度为rear-front。但当rear （rear-front+Queue）/ QueueSize

3、代码实现

public class CircleArrayQueueDemo {

	public static void main(String[] args) {
		// 创建一个队列
		CircleArray circleArray = new CircleArray(4); // 其队列的有效数据最大是3
		char key = ' '; // 接受用户输入
		Scanner scanner = new Scanner(System.in);
		boolean loop = true;
		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):查看队列头的数据");
		while (loop) {
			key = scanner.next().charAt(0); // 接收第一个字符
			switch (key) {
			case 's':
				circleArray.showQueue();
				break;
			case 'a':
				System.out.println("输入一个数:");
				int value = scanner.nextInt();
				circleArray.addQueue(value);
				break;
			case 'g':
				try {
					int res = circleArray.getQueue();
					System.out.printf("取出的数据是%d\n", res);
					continue;
				} catch (RuntimeException e){
					System.out.println(e.getMessage());
				}
				break;
			case 'h':
				try {
					int res = circleArray.headQueue();
					System.out.printf("队列头的数据是%d\n", res);
				} catch (RuntimeException e){
					System.out.println(e.getMessage());
				}
				break;
			case 'e':
				scanner.close();
				loop = false;
				break;
			default:
				break;
			}
		}
		System.out.println("程序退出");

	}
}

class CircleArray{
	private int maxSize;//表示数组的最大容量
	private int front; //队列头
	private int rear; //队列尾
	private int[] arr; //该数组用于存放数据，模拟队列

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

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

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

	// 添加数据到队列
	public void addQueue(int n) {
		// 判断队列是否满
		if (isFull()) {
			System.out.println("队列满，不能加入数据~~");
			return;
		}
		// 直接将数据加入
		arr[rear] = n;
		// 将 rear 后移 ，这里必须考虑取模
		rear = (rear + 1) % maxSize;
	}

	// 数据出队列
	public int getQueue() {
		if (isEmpty()) {
			// 通过抛出异常
			throw new RuntimeException("队列为空，不能取数据~~");
		}
		// front是指向队列的第一个元素
		// 1.先把front对应的值保存到一个临时变量,
		int value = arr[front];
		// 2.将front后移，考虑取模
		front = (front + 1) % maxSize;
		return value;
	}

	// 显示队列的所有数据
	public void showQueue() {
		if (isEmpty()) {
			System.out.println("队列空的，没有数据~~");
			return;
		}
		// 从front开始遍历，遍历多少个元素
		for (int i = front; i < front + size(); i++) {
			int index = i % maxSize; // 加上size之后可能会超过数组范围，需要进行取模
			System.out.printf("arr[%d]=%d\n", index, arr[index]);
		}
	}
	
	// 求出当前队列的有效数据个数
	public int size(){
		// 这里 + maxSize保证分子是正数，也可以使用Math.abs(rear - front)
		return (rear + maxSize - front) % maxSize;
	}

	// 显示队列的头数据，不是取数据而仅仅是显示
	public int headQueue() {
		// 判断队列是否为空
		if (isEmpty()){
			// 通过抛出异常
			throw new RuntimeException("队列为空，没有数据~~");
		}
		return arr[front];
	}
}
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
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131