MyBlog

《算法》
第一章
第三节
学习记录
—笔者
—— 魏静崎
2020年08月27日

1.3背包、队列和栈

1.3.1.1 泛型

集合类的抽象数据类型的一个关键特性是可以存储任意的数据类型

1.3.1.2 自动装箱

自动将一个原始数据类型转化为一个封装类型被称为自动装箱，自动将一个封装类型转化为一个原始数据类型被称为自动拆箱。

1
2
3

Stack<Integer> stack = new Stack<>();
stack.push(17);	// 自动拆箱 int -> Integer
int i = stack.pop();	//自动装箱 Integer -> int

1.3.1.4 背包

背包是一种不支持从中删除元素的集合数据类型
目的：帮助用例收集元素并迭代遍历所有收集到的元素，且迭代的顺序不确定且与用例无关。

1.3.2.2 泛型

我们需要通过泛型来使一个集合类支持不同的数据类型，因此我们希望在初始化的过程中创建一个支持泛型的数组

1	a = new Item[cap];

但是直接创建泛型数组在java中是不被允许的，我们需要进行强制类型转换。

1	a = (Item[]) new Object[cap];

1.3.2.3 调整数组的大小

集合类的最大容量在初始化是被确定是十分不友好的，因此我们需要动态调整数组的大小，使得它既足以保存所有元素，又不会浪费太多空间。
再次之前我们需要首先实现一个方法将数组元素移动到另一个不同大小的元素中。
如果没有多余的空间我们将数组的长度加倍。
如果数组太大我们则将它的长度减半。而数组太大的正确检测条件是实际元素数量是否小于数组大小的四分之一，这样减半后的容量约为半满，可以支持多次操作。

1.3.2.4 对象游离

Java的垃圾回收机制是回收所有无法被访问的对象的内存。
避免一个对象游离(有一个不需要的对象的引用)，只需要将被弹出的元素的值设为null即可，这样覆盖无效的引用并使系统可以在元素被弹出后回收内存。

1.3.2.5 迭代

迭代遍历并处理集合的每个元素是集合类数据类型的基本操作之一。

在集合数据类型中我们需要实现:

1.集合数据类型必须实现一个==iterator()== 方法并返回一个==Iterator== 对象
2.Iterator类必须包含两个方法:hasNext()和next()

迭代器就是一个实现了hasNext()方法和next方法的类的对象。
拥有迭代器才能使用forEach方法。

在这里我们应该知道任意集合数据类型的实现的最佳性能:

每项操作的用时都与集合大小无关
空间需求总是不超过集合大小乘以一个常数

1.3.3 链表

链表是一个Java非直接支持的数据结构
在结构化存储数据集中，链表是数组的一种重要的代替方案。

1.3.3.1 节点记录

在面向对象编程中我们可以使用一个嵌套类来定义节点的抽象数据类型。

private class Node{
 Item item;	//Item只是一占位符，我们将会使用泛型使之表示任意引用类型
 Node next;
 }

答疑部分

Java不允许使用泛型数组的原因: 共变数组(covariant array)和类型擦除(type erasure)。 — 看不懂QAQ
创建一个字符串栈的数组
1
Stack<String>[] a = (Stack<String>[]) new Stack[N];
! 警告，Java会在编译时检查类型的安全性，运行时会抛弃这些信息，因此若不强制转换则右侧会变为 Stack<Object>[] 或者只剩下 Stack[]，因此必须强转。

本文作者： 魏静崎
本文链接： https://slightwjq.github.io/2023/10/17/算法阅读笔记1-3/
版权声明： 该文章来源及最终解释权归作者所有

《算法》

第 一章

第三节

学习记录

—笔者