Program = Data Structure + Algorithm
所以，这篇系列博客，将从头记录数据结构从数组开始，到各种数据结构
Let’s start it!

何为数据结构

数据结构是数据在计算机中存储的形态，比如一个班的学生，是站成一排，还是站成两排，还是正方形等等。

那没有数据结构可不可以，如果没有数据结构，我们想想一下，还是这一个班的学生，我如果要找某个同学，假设我知道他叫什么，也知道他在哪，但我该怎么描述他的位置呢？

如果是有结构的，我们可以说，第一排第六个，或者[3,4]这个位置，又或者[1,4,7]这样的三维位置可以描述他的准确位置，可如果它们没有结构，每个人都随意在任意一个位置，假设我们知道位置，但怎么告诉程序该去哪找他？

所以，描述数据位置及组成的结构叫做数据结构。而选择合适的数据结构密切影响着我们程序运行的效率。

数据结构在内存中

大家都知道，计算机中的数据都在内存里，那么，数据结构在内存中是怎么样的？

在内存中数据结构有四种方式

  1. 顺序存储方法
    • 逻辑上相连的节点也存储在物理位置上也相邻的单元里，只存住节点的值，不存储节点的之间的关系
    • 遍历速度快
    • 不利于查找某个具体数据
  2. 链表存储方法
    • 不要求物理上单元相邻，节点之间的关系由附加的指针来描述
    • 更改方便
  3. 索引存储方法
    • 索引存储是在存储数据的同时，再建立一个附加的索引表，然后利用索引表中索引项的值来确定实际存储单元地址
    • 查找方便
  4. 散列存储方法
    • 根据存储的关键字直接计算出节点的存储地址

在Java中，数据结构的基本呈现

首先我们第一站，肯定要描述最基本的单元，利用最基本的结构，来向上做出适应更复杂场景的结构。

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
public final class Array<E> {
  //泛型类保存数据
	private E[] data;
  //一组数据中实际数据的下一个位置
	private int size;

  //扩容参数
	private final float limit;

	public Array() {
		this(10, 0.4f);
	}

	public Array(int capacity) {
		this(capacity, 0.4f);
	}

	public Array(int capacity, float limit) {
		data = (E[]) new Object[capacity];
		this.size = 0;
		this.limit = limit;
	}

	//O(1) 获取里面包含了多少数据
	public int getSize() {
		return size;
	}

	//O(1) 获取数组当前的容量
	public int getCapacity() {
		return data.length;
	}

	//O(1) 是否为空
	public boolean isEmpty() {
		return size == 0;
	}

	//O(1) 存入一个数据
	public void put(E e) {
		put(size, e);
	}

	//O(n) 在第一个位置添加数据
	public void addFirst(E e) {
		put(0, e);
	}

	//O(1) 获取最后一个位置的数据
	public E getLast() {
		return data[size - 1];
	}

	//O(1) 获取某个位置的数据
	public E get(int pos) {
		if (pos < 0 || pos >= size)
			throw new IllegalArgumentException("out of array, pos = " + pos + ", size= " + size);

		return data[pos];
	}

	//O(1) 设置某个位置上的数据
	public synchronized void set(int pos, E e) {
		if (pos < 0 || pos >= size)
			throw new IllegalArgumentException("set out of array, pos = " + pos + ", size= " + size);

		data[pos] = e;
	}

	//O(n) 放入一个数据，判断是否需要扩容，
	public synchronized void put(int pos, E e) {
		if (pos >= data.length)
			resize(data.length * 2);

		if (size == data.length || pos < 0)
			throw new IllegalArgumentException("add failed, array is already full pos = " + pos + " ,Size = " + size + " ,Capacity = " + data.length);

		for (int i = size - 1; i >= pos; i--)
			data[i + 1] = data[i];

		data[pos] = e;
		size++;
	}

	public synchronized E deleteLast() {
		return delete(size - 1);
	}

	//O(n)  删除某个位置元素，判断是否需要缩容
	public synchronized E delete(int pos) {
		if (pos < 0 || pos >= size)
			throw new IllegalArgumentException("delete failed, pos = " + pos + " ,Size = " + size + " ,Capacity = " + data.length);

		E e = data[pos];
		if (pos != size - 1) {
			for (int i = pos; i < size - 1; i++) {
				data[i] = data[i + 1];
			}
		}
		size--;
		data[size] = null;
		if (size < data.length * limit)
			resize(data.length / 2);

		return e;
	}

	//O(n) 重制容器的容积
	private synchronized void resize(int capacity) {
		if (capacity < 5) {
			return;
		}
		E[] newData = (E[]) new Object[capacity];
		for (int i = 0; i < size; i++) {
			newData[i] = data[i];
		}
		data = newData;
	}

	@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(']');
		System.out.println("内存中的数据{" + Arrays.toString(data) + "}");
		return res.toString();
	}

	public static void main(String[] args) {
		Array<Integer> array = new Array<>();
		for (int i = 0; i <= 20; i++)
			array.put(i);

		for (int i = 0; i < 15; i++) {
			array.delete(0);
			System.out.println(array + "\n>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>");
		}

	}
}

以上就是一个可以装任意数据的组数结构的Java版本，那么有了这个结构，自然就衍生出来，堆结构和栈结构。

第二篇数据结构就是堆栈结构的实战代码。