数据结构

稀疏数组(SparseArray)

最为基础的一个数据结构
原理很简单,比如一个棋盘,只摆放了两个棋子
存储的时候不需要将整个棋盘存起来
只需要记录棋盘的大小以及棋子的坐标即可
很大程度的节省了存储空间

  • 将二维数组转为稀疏数组
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    static int[][] toSparseArray(int[][] map){
    //寻找非空的值的数量
    int notNullCount = 0;
    for (int i = 0; i < 15; i++) for (int j = 0; j < 15; j++) if(map[i][j]!=0) notNullCount++;
    //创建稀疏数组
    int[][] sMap = new int[notNullCount+1][3];
    //稀疏数组的第一个值是 [原数组行数,原数组列数,非空值数量]
    sMap[0][0] = map.length;
    sMap[0][1] = map[0].length;
    sMap[0][2] = notNullCount;
    //记录非空的坐标以及值
    int sMapIndex = 1;
    for (int i = 0; i < 15; i++) for (int j = 0; j < 15; j++) if(map[i][j]!=0) {
    sMap[sMapIndex][0] = i;
    sMap[sMapIndex][1] = j;
    sMap[sMapIndex][2] = map[i][j];
    sMapIndex++;
    }
    return sMap;
    }
  • 稀疏数组转换回二维数组
    1
    2
    3
    4
    5
    6
    static int[][] toDoubleDimensionalArray(int[][] sMap){
    int[][] map = new int[sMap[0][0]][sMap[0][1]];
    for (int i = 1; i < sMap.length; i++)
    map[sMap[i][0]][sMap[i][1]]=sMap[i][2];
    return map;
    }
    同理,无论多少维的数组,都可以用这种方式来表示,仅仅是稀疏数组的列需要增加而已
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
import java.util.Arrays;

public class App {
public static void main(String[] args) {
int[][] map = new int[15][15];
map[2][3] = 1;
map[3][4] = 2;
eachArray(map);
/*
原数组遍历结果
[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, 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, 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, 0, 0, 0, 0, 0, 0, 0, 0, 0]
*/

int[][] sMap = toSparseArray(map);
eachArray(sMap);
/*
稀疏数组遍历结果
[15, 15, 2]
[2, 3, 1]
[3, 4, 1]
*/
eachArray(toDoubleDimensionalArray(sMap));
}
static void eachArray(int[][] map) {
for (int i = 0; i < map.length; i++) System.out.println(Arrays.toString(map[i]));
}
}

队列(Queue)

队列是只允许在一端进行插入操作,在另外一段进行删除操作的线性表
队列不允许在中间部位进行操作
先进先出(FIFO, First-In-First-Out)的线性表

队列在计算机领域的应用:

  1. 在图形遍历的先广后深搜索法(BFS)
  2. 用于计算机的模拟(simulation)
  3. CPU的工作调度等。
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
import java.util.Arrays;

public class ArrayQueue {

private int maxSize;
private int front; //队列首个元素下标-1
private int rear; //队列最后一个元素下标
private Object[] array;

public ArrayQueue(int maxSize) {
this.maxSize = maxSize;
array = new Object[maxSize];
front = -1;
rear = -1;
}

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

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

public void add(Object obj) {
if (isFull())
throw new RuntimeException("队列已满");
array[++rear] = obj;
}

/**
* 查看并移除首个元素
*/
public Object poll() {
if (isEmpty())
throw new RuntimeException("队列为空");
return array[++front];
}

/**
* 查看但不移除首个元素
*/
public Object peek() {
if (isEmpty())
throw new RuntimeException("队列为空");
return array[front + 1];
}

@Override
public String toString() {
StringBuffer sb = new StringBuffer();
for (int i = front + 1; i < front + 1 + size(); i++) {
sb.append(array[i] + ",");
}
return sb.deleteCharAt(sb.length() - 1).toString();
}

}

由于出队操作,使得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
public class CircularQueue {

private int maxSize;
private int front; //首个元素的下标
private int rear; //最后一个元素的下标+1
private Object[] array;

public CircularQueue(int maxSize) {
this.maxSize = maxSize;
array = new Object[maxSize];
front = 0;
rear = 0;
}

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

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

public void add(Object obj) {
if (isFull())
throw new RuntimeException("队列已满");
array[rear] = obj;
rear = (rear + 1) % maxSize;
}

public int size() {
return (rear + maxSize - front) % maxSize;
}

public Object poll() {
if (isEmpty())
throw new RuntimeException("队列为空");
Object obj = array[front];
front = (front + 1) % maxSize;
return obj;
}

@Override
public String toString() {
StringBuffer sb = new StringBuffer();
for (int i = front; i < front + size(); i++) {
sb.append(array[i] + ",");
}
return sb.deleteCharAt(sb.length() - 1).toString();
}

}

测试代码

1
2
3
4
5
6
//约定:实际有效数据长度为maxSize-1
ArrayQueue queue = new ArrayQueue(4);
queue.add(1);
queue.add(2);
queue.add(3);
System.out.println(queue.isFull());