1.1 數據結構介紹 數據結構：數據用什麼樣的方式組合在一起。 1.2 常見的數據結構 數據存儲的常用結構有：棧、隊列、數組、鏈表和紅黑樹。 棧： 棧：stack，又稱為堆棧，它是運算受限的線性表，其限制是僅允許在標的一端進行插入和刪除操作，不允許在其他任何位置進行添加、查找、刪除等操作。 簡單來說 ...
1.1 數據結構介紹
數據結構：數據用什麼樣的方式組合在一起。
1.2 常見的數據結構
數據存儲的常用結構有：棧、隊列、數組、鏈表和紅黑樹。
棧：
- 棧：stack，又稱為堆棧，它是運算受限的線性表，其限制是僅允許在標的一端進行插入和刪除操作，不允許在其他任何位置進行添加、查找、刪除等操作。
簡單來說：採用該結構的集合，對元素的存取有如下的特點。
- 先進後出（即，存進去的元素，要在它後面的元素依次取出後，才能取出該元素）。例如，子彈壓進彈夾，先壓進去的子彈在下麵，後壓進去的子彈在上面，
當開槍的時候，先彈出上面的子彈，然後才彈出下麵的子彈。
- 棧是允許在同一端進行插入和刪除操作的特殊線性表。允許進行插入和刪除操作的一端稱為棧頂(top)，另一端為棧底(bottom)；棧底固定，而棧頂浮動；棧中元素個數為零時稱為空棧。插入一般稱為壓棧（PUSH），刪除則稱為彈棧（POP）
這裡需要理解兩個名詞：
- 壓棧：就是存元素。即，把元素存儲到棧的頂端位置，棧中已有元素依次向棧底方向移動一個位置。
public class MyStack {
private int[] array;
private int size;
private int top;
public MyStack(int size){
this.size = size;
array = new int[size];
top = -1;
}
//壓棧
public void push(int value){
if(top < size-1){
array[++top] = value;
}
}
//彈棧
public int pop(){
return array[top--];
}
//獲取棧頂數據
public int getTop(){
return array[top];
}
//判斷棧是否為空
public boolean isEmpty(){
return (top == -1);
}
//判斷棧是否滿了
public boolean isFull(){
return (top == size-1);
}
}
代碼測試：
public class Test {
public static void main(String[] args) {
MyStack stack = new MyStack(3);
stack.push(3);
stack.push(2);
stack.push(1);
System.out.println(stack.getTop());
while(!stack.isEmpty()){
System.out.println(stack.pop());
}
}
}
結果：
- 鏈表：linked list，由一系列結點node（鏈表中每一個元素稱為結點）組成，結點可以在運行時動態生成。每個結點包括兩個部分：一個多個接地
我們
紅黑樹可以通過紅色節點和黑色節點儘可能的保證二叉樹的平衡，從而來提高效率。
2.1 HashSet集合存儲數據的結構（哈希表）
什麼是哈希表？
在JDK1.8之前，哈希表底層採用數組+鏈表實現，即使用數組處理衝突，同意hash值的鏈表都存儲在一個數組內。但是當位於一個桶中的元素較多，即hash值相等的元素較多時，通過key值依次查找的效率較低。而JDK1.8中，哈希表存儲採用數組+鏈表+紅黑樹實現，當鏈表長度超過閾值（8）時，將鏈表轉換為紅黑樹，這樣大大減少了查找時間。
簡單的來說，哈希表是由數組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現的，如下圖所示。
為了方便理解可以結合一個存儲流程圖來說明一下：
// 創建自定義學生類
public class Student {
private int age;
private String name;
private double score;
public Student() {
}
public Student(int age, String name, double score) {
this.age = age;
this.name = name;
this.score = score;
}
// 重寫equal和hashCode方法，
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (!(o instanceof Student)) return false;
Student student = (Student) o;
return getAge() == student.getAge() &&
Double.compare(student.getScore(), getScore()) == 0 &&
Objects.equals(getName(), student.getName());
}
@Override
public int hashCode() {
return Objects.hash(getAge(), getName(), getScore());
}
// 重寫toString方法
@Override
public String toString() {
return "Student{" +
"age=" + age +
", name='" + name + '\'' +
", score=" + score +
'}'+"\n";
}
// get， set 方法省略。
創建測試類：
public class Demo15 {
public static void main(String[] args) {
// 創建HashSet集合，接收自定義類型數據。
HashSet<Student> hs = new HashSet<>();
Student s1 = new Student(19,"王小石",99.2);
Student s2 = new Student(20,"雷純",99.4);
Student s6 = new Student(23,"戚少商",99.8);
Student s3 = new Student(21,"溫柔",99.6);
Student s4 = new Student(22,"白愁飛",99.1);
Student s5 = new Student(23,"戚少商",99.8);
// 將數據添加到HashSet集合當中。
hs.add(s1);
hs.add(s2);
hs.add(s3);
hs.add(s4);
hs.add(s5);
hs.add(s6);
System.out.println(hs);
結果：
