什么是数据结构？
数据结构研究的是数据如何在计算机中进行组织和存储，使得我们可以更高效的获取数据或者修改数据。
数据结构的分类：
- 线性结构：数组、链表、栈、队列、哈希表。
- 树结构：二叉树、红黑树、B+树、堆、二分搜索树、Treap、线段树、Splay、K-D树、查并集、哈夫曼树、Trie。
- 图结构：邻接矩阵、邻接表、十字链表、边集数组、边集链表。
数组
数据是最基础的数据结构，说白了就是把数据码成一排存放，数组的关键在于可索引性。
下面展示如何在 Java 语言中使用数组：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
public class Main {
public static void main(String[] args) {
// 初始化数组（不赋值）
int[] arr = new int[10];
for(int i = 0 ; i < arr.length ; i ++)
arr[i] = i;
// 初始化数组（赋值）
int[] scores = new int[]{100, 99, 66};
for(int i = 0 ; i < scores.length ; i ++)
System.out.println(scores[i]);
// for each 写法
for(int score: scores)
System.out.println(score);
// 通过索引修改元素
scores[0] = 96;
for(int i = 0 ; i < scores.length ; i ++)
System.out.println(scores[i]);
}
}
|
索引可以“有语义”，也可以没有“语义”。比如在数组中存储学生成绩，索引就有语义，因为索引 0 代表第一个学生的成绩，索引 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
138
139
140
141
142
143
144
145
146
147
|
public class Array<E> {
private E[] data;
private int size;
// 构造函数，传入数组的容量capacity构造Array
public Array(int capacity){
data = (E[])new Object[capacity];
size = 0;
}
// 无参数的构造函数，默认数组的容量capacity=10
public Array(){
this(10);
}
// 获取数组的容量
public int getCapacity(){
return data.length;
}
// 获取数组中的元素个数
public int getSize(){
return size;
}
// 返回数组是否为空
public boolean isEmpty(){
return size == 0;
}
// 在index索引的位置插入一个新元素e
public void add(int index, E e){
if(index < 0 || index > size)
throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size.");
if(size == data.length)
resize(2 * data.length);
for(int i = size - 1; i >= index ; i --)
data[i + 1] = data[i];
data[index] = e;
size ++;
}
// 向所有元素后添加一个新元素
public void addLast(E e){
add(size, e);
}
// 在所有元素前添加一个新元素
public void addFirst(E e){
add(0, e);
}
// 获取index索引位置的元素
public E get(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Get failed. Index is illegal.");
return data[index];
}
// 修改index索引位置的元素为e
public void set(int index, E e){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Set failed. Index is illegal.");
data[index] = e;
}
// 查找数组中是否有元素e
public boolean contains(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e))
return true;
}
return false;
}
// 查找数组中元素e所在的索引，如果不存在元素e，则返回-1
public int find(E e){
for(int i = 0 ; i < size ; i ++){
if(data[i].equals(e))
return i;
}
return -1;
}
// 从数组中删除index位置的元素, 返回删除的元素
public E remove(int index){
if(index < 0 || index >= size)
throw new IllegalArgumentException("Remove failed. Index is illegal.");
E ret = data[index];
for(int i = index + 1 ; i < size ; i ++)
data[i - 1] = data[i];
size --;
data[size] = null; // loitering objects != memory leak
if(size == data.length / 4 && data.length / 2 != 0)
resize(data.length / 2);
return ret;
}
// 从数组中删除第一个元素, 返回删除的元素
public E removeFirst(){
return remove(0);
}
// 从数组中删除最后一个元素, 返回删除的元素
public E removeLast(){
return remove(size - 1);
}
// 从数组中删除元素e
public void removeElement(E e){
int index = find(e);
if(index != -1)
remove(index);
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append(String.format("Array: size = %d , capacity = %d\n", size, data.length));
res.append('[');
for(int i = 0 ; i < size ; i ++){
res.append(data[i]);
if(i != size - 1)
res.append(", ");
}
res.append(']');
return res.toString();
}
// 将数组空间的容量变成newCapacity大小
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity];
for(int i = 0 ; i < size ; i ++)
newData[i] = data[i];
data = newData;
}
}
|
计算各个操作的复杂度
均摊复杂度
复杂度的震荡
解决方案：Lazy
栈
栈实际就是一数组，只不过仅允许在数组的一段添加&删除元素。
应用
- IDE 的 UNDO 操作。
- 程序调用的系统栈。
- 函数的括号匹配
{}。
实现
可以用很多种数据结构实现队列，现在我们先用上文的动态数组实现队列：
队列
支付宝
微信