数据结构笔记

哈希表

目的

提供一个存储结构, 其中存储的是Key-Value对, Key和Value可以是任意的类型
类似于数组: 可以使用数组的下标索引(数字!!!!)去访问存储的数据!

Key可以是任何类型的! arr[名字] = 人的身份对象

; test = abc["fff"] xxxx

类似于f(x) = y这样的函数, 我们可以设置任意的f(x1) = y1, 或者f(x2) = y2.

或者访问: a = f(x1)

也就是支持四种操作: 增删改查!

增加, 查询,修改和删除操作的时间复杂度都近似于 O(1) , 也不依赖于插入的顺序. 也就是随机访问(想访问哪个数据就马上访问哪个数据!)

存储在哈希表里的数据没有顺序!!! 不可以对哈希表进行排序

有什么样的属性!
支持什么样的操作!

    HashMap<String, String> genderMap = new HashMap<String, String>();
    // 增
    genderMap.put("alex", "male");
    genderMap.put("CC", "female");

    // 查
    if (genderMap.containsKey("alex")) {
      System.out.println(genderMap.get("alex"));
    }

    // 改
    genderMap.put("CC", "male"); // 覆盖掉

    // 删
    genderMap.remove("CC");

数组和哈希表不一样的点

数组的key只支持数字的, 但是哈希表支持更多的数据类型

数组在中间插入数据操作, 时间复杂度一般不是O(1)

基本实现原理

把任意的Key值转换成数字, 然后作为数组的下标, 然后把Value存储在数组下标对应位置上

ValueClass[] array = new ValueClass[size

比如:

修改操作

String key = someString();
int index = hash(key);
array[index] = value;

访问操作

int index = hash(key);
ValueClass value = array[index];

栈

一个数据结构, 用于存储数据. 支持两种操作:

• 插入数据 (push);
• 取出数据 (pop); 获得数据, 同时把数据从栈中删除

所有操作的时间复杂度度为O(1)

最重要的是, 哈希表可以随机访问. 但是栈对数据的访问顺序有规定. 遵循一个规则: 先进后出, 后进先出. 也就是只能访问当最近放进到栈里面的那个数据!

    Stack<Number> stack = new Stack<Number>();

    stack.push(3);
    stack.push(5);
    stack.push(7);
    System.out.println(stack.pop());  // 5
    System.out.println(stack.pop());  // 3

    // 只看顶部数据，但是不删除
    stack.peek();

    // 检查是否为空
    stack.empty();

实例

• 函数调用栈

function f1() {
    f2()
    code...
}
function f2() {
    f3()
    code....
}

f1(); -> f2(); -> f3
// 调用f1中, 会把f1的状态,装入栈中, 调用f2

• 深度优先搜索, 汉诺塔, 括号平衡检查, 表达式求值...

队列

一个类似于栈的数据结构, 用于存储数据, 同样支持两种操作:

• 插入数据 (push);
• 取出数据 (pop); 获得数据, 同时从队列中删除
  所有操作的时间复杂度为O(1)

队列遵循一个规则: 先进先出, 后进后出. 也就是从队列中取出数据的顺序和放进去的顺序是一样的!

实例

• 消息队列
• 广度优先搜索

 // 队列
    Queue<Integer> queue = new LinkedList<>();
    queue.add(3);
    queue.add(5);

    System.out.println("queue, " + queue.poll());  // 3
    System.out.println("queue, " + queue.poll());  // 5

    Integer first_of_queue = queue.peek();

    queue.isEmpty();