Java学习笔记（五）——Java集合
一、Java集合简介
（一）集合的概念
集合（Collection）就是指一堆事物，而集合里的事物被称为元素（Element）。例如，编程语言就是一个集合，这个集合中的元素就包含：C语言，C++语言，Java语言，Python语言等等
在数学的概念中的集合，分为两种：
（1）有限集合：
①班级内所有成员构成的集合
②网站内所有商品构成的集合
（2）第二种是无限集合：
①全体自然数集合
②有理数集合
③实数集合
（二）集合的作用
那么我们在计算机中利用集合可以做什么呢？
我们可以用来处理一组数据，比如：
①计算总成绩或平均成绩
②列举所有商品
（三）Java集合
如果一个Java对象可以在内部持有若干其他Java对象，并对外提供访问接口，我们把这种Java对象称为集合。
1 . Java的数组可以看做是一种集合：
String[] ss = new String[10];//定义一个可以持有10个元素的String数组
ss[0] = "Hello";//可以放入String对象
String first = ss[0];//可以获取String对象2 . 其他集合类
那么我们已经拥有了数组，为什么还需要拥有其他集合类呢？
首先，数组初始化后大小不可变；其次，数组只能按索引顺序存取。也就是说，数组在使用过程中并不是很灵活。
所以我们需要其他各种集合类来处理一些其他功能：
①可变大小的顺序链表
②保证无重复元素的集合
JDK提供的Java.util包提供了所有集合类
（1）Collection
Collection是所有集合类的根接口，主要分为两类：
①List：一种有序列表
②Set：一种保证没有重复元素的集合
（2）Map
Map是一种通过Key查找value的映射表集合
3 . Java集合设计的特点
（1）接口和实现相分离
例如：一个List接口，它的实现类包括ArrayList，LinkedList等等
（2）支持泛型
例如：使用List< Student > list = new ArraysList<>()定义一个泛型接口
（3）访问集合有统一的方法
使用迭代器Iterator模式
4 . 遗留类
JDK中部分集合类是遗留类，我们不应该继续使用。例如：
（1）Hashtable：一种线程安全的Map实现
（2）Vector：一种线程安全的List实现
（3）Stack：基于Vector实现的LIFO的栈
这些集合类都是在JDK早期版本中引入的，从JDK 1.2版本开始就已经作废
5 . 遗留接口
JDK中部分集合类是遗留接口，我们不应该继续使用。例如：
Enumeration< E >：已经被新的接口Iterator< E >取代
二、List
（一）使用List
1 . List< E >是一种有序链表
（1）List内部按照放入元素的先后顺序存放
（2）每个元素都可以通过索引确定自己的位置
（3）类似于数组，但大小可变
2 . List是一种泛型接口
（1）void add(E e)：在末尾添加一个元素
（2）void add(int index , E e)：在指定索引添加一个元素
（3）int remove(int index)：删除指定索引的元素
（4）int remove(Object e)：删除某个元素
（5）E get(int index)：获取指定索引的元素
（6）int size()：获取链表的大小（包括元素的数量）
3 . ArrayList< E >
数组也是一个有序结构，但是其大小固定，且删除元素时需要移动后续元素，使用数组在添加和删除元素时十分不便。
ArrayList< E >：在内部使用数组存储所有元素
当添加一个元素到ArrayList< E >的时候，ArrayList< E >在内部的空闲位置添加一个元素。如果我们的数组内部空间已经满了该怎么办呢？
ArrayList< E >会创建一个更大的数组，之后将旧数组的所有元素复制到新数组，之后用新数组取代旧数组，这样我们就可以添加新的元素了。
4 . LinkedList< E >
LinkedList< E >：内部每个元素都指向下一个元素
当我们向LinkedList< E >中添加元素时，只需要添加一个新的节点，然后将末尾元素的指针指向新的节点，就可以完成元素的添加。
5 . ArrayList< E >与LinkedList< E >的区别
比较 ArrayList LinkedList
获取指定元素 速度很快 需要从头开始查找元素
添加元素到末尾 速度很快 速度很快
在指定位置添加/删除 需要移动元素 不需要移动元素
内存占用 少 较大
List中的元素时可以重复的
List的元素可以是null
6 . 遍历List< E >
（1）使用get(int index)：
通过get()方法传入一个索引，通过调用for循环，不断地调用get()方法，就变成了类似于用遍历数组的方式遍历List< E >
List<String> list = ...
for(int i = 0; i < list; i++) {
String s = list.get(i);
}这种方法对于ArrayList< E >效率较高，但是对于LinkedList< E >效率较低。
（2）使用Iterator< E >：
Iterator是一个对象，它由List对象本身通过Iterator方法创建。Iterator对象知道如何去遍历一个List。
如果我们要使用Iterator遍历一个List，可以使用for循环，循环的初始条件是获取List对象的Iterator对象，循环的结束条件是hasNext()返回false，在循环体中不断的调用next()方法就可以获得List的下一个元素：
List<String> list = ...
for(Iterator<String> it = list.iterator());it.hasNext();) {
String s = it.next();
}（3）使用foreach循环：
这种方法可以简单的遍历List
List<String> list = ...
for(String s : list) {
}注意：除了数组以外，所有实现了Iterable接口的类都可以使用foreach循环进行遍历，由于List接口实现了一个Iterable接口，所以它可以使用foreach进行遍历。
编译器本身是不知道如何遍历一个Iterator对象的，但是它会自动的把foreach循环变为Iterator调用
7 . List和Array转换
（1）把List< E >转换为Array
List接口提供了一个Object[] toArray()方法，可以直接返回一个Object[]：
List< Integer > list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Object[] Array = list.toArray();
//{1,2,3}List还提供了一个重载的< T >T[] toArray(T[] a)方法，可以传入一个指定类型的T数组，然后返回T类型的数组：
List< Integer > list = new ArrayList<>();
list.add(1);
list.add(2);
list.add(3);
Integer[] Array = list.toArray(new Integer[2]);
//{1,2,3}（2）把Array变为List< E >
< T > List< T > Arrays.asList(T…a)
Integer array = {1,2,3};
List< Integer > list = Arrays.asList(array);
//注意这里返回的是List而不是ArrayList如果我们希望把一个Array变成ArrayList：
Integer array = {1,2,3};
List<Integer> arrayList = new ArrayList<>(Arrays.asList(array));import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<String> list = new ArrayList<>();
list.add("Zero");
list.add("One");
list.add("Two");
for(String s : list) {
System.out.println(s);
}
}
}
//打印结果：
//Zero
//One
//Two（二）编写equals方法
在List中我们可以使用contains()和indexOf()方法来判断某些元素是否存在，例如：
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");
list.contains("C");//true
list.contains("X");//false
list.indexOf("C");//2
list.indexOf("X");//-1那么在上面这段代码中，我们传入的字符串”C”和contains()方法调用的字符串”C”是否是同一个实例呢？如果调用的不是同一个实例，那么这段代码能否得到正确的结果呢？
我们可以改写一下字符串”C”，以确保调用的一定不是相同实例：
List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add(new String("C"));
list.contains(new String("C"));//结果依然为true
list.contains("X");//false
list.indexOf("C");//2
list.indexOf("X");//-1这时我们发现其判断结果依然为true。
因为在List内部，判断两个元素是否相等是使用equals()方法来判断的，而不是“==”操作符来进行比较。所以如果我们要正确调用contains()和indexOf()方法，放入的实例就要正确实现equals()方法。我们之所以能够传入String和Integer类，是因为JDK在定义时已经正确定义了equals()方法
下面我们编写一个例子，用来演示如何编写equals()方法：
首先定义一个Person类：
public class Person {
private final String name;
private final int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "(Person: " + name + ", " + age + ")";
}
}然后定义一个Main方法：
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
List<Person> list = new ArrayList<>();
list.add(new Person("Ming", 12));
list.add(new Person("Hong", 15));
list.add(new Person("Jun", 18));
System.out.println(list);
System.out.println(list.contains(new Person("Jun", 18)));
}
}在Main方法中，我们首先打印出list方法的值，然后对list调用contains()方法来判断一个Person类型是否存在。
我们运行这段代码之后，会发现打印结果是false。这是因为我们在定义Person类的时候并没有覆写Object的equals()方法，所以实际上这里的contains()方法是使用“==”操作符进行了实例的比较，所以其结果才显示为false。
如果我们需要修复这个代码逻辑，让contains()方法的结果返回true，我们就需要编写equals()方法。
private final String name;
private final int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "(Person: " + name + ", " + age + ")";
}
public boolean equals(Object o) {
//首先判断传入的对象o是否是当前对象this
if(this==o) {
return true;
}
//之后判断传入的对象o是否是Person类型
if(o instanceof Person) {
//如果是Person类型就强制转换为Person对象
Person p = (Person) o;
//通过Person变量p来比较当前对象this的字段是否相等
//return (p.name == this.name || p.name != null && p.name.equals(this.name)) && p.age == this.age;
//但是上面这段代码比较麻烦，因此我们可以改写为Object提供的方法：
return Object.equals(p.name, this.name) && p.age == this.age;
}
return false;//如果不是Person类型就返回false
}
}
//打印结果变为falseequals()编写方法：
（1）判断this==o
（2）判断o instanceof Class
（3）强制转型，并比较每个对应的字段
（4）基本类型字段用==直接比较
（5）引用类型字段借助Objects.equals()判断
三、Map
（一）使用Map
1 . Map映射表的概念
如果要在List中根据name查找某个指定的Student实例，我们可以使用遍历List并判断name是否相等来获取指定的元素：
public class Student {
public String name;
public String address;
public int score;
public int grade;
}
List<Student> list = new List<>();
Student target = null;
for(Student s : list) {
if("Zero".equals(s.name)) {
target = s;
break;
}
}上面这种方法比较麻烦，我们需要编写大量的代码去完成这个功能。
我们可以使用Map这种键-值（Key-Value）映射表，通过Key来快速的查找Value（元素）：
public class Student {
public String name;
public String address;
public int score;
public int grade;
}
Map<String, Student> map = ...;
Student target = map.get("Zero");Map是一种通过Key（键值）快速查找Value（元素）的数据类型
2 . Map的常用方法
（1）V put(K key, V value)：把Key-Value放入Map
（2）V get(K key)：通过Key获取Value
（3）boolean containsKey(K key)：判断Key是否存在
3 . 如何遍历Map
（1）遍历Key可以使用foreach循环来遍历keySet()：
Map<String, Integer> map = ...
//map对象的keySet()方法会返回一个Set集合
for(String key : map.keySet()) {
Integer value = map.get(key);
}（2）使用foreach循环遍历entrySet()同时遍历Key和Value：
Map<String, Integer> map = ...
for(Map.Entry<String, Integer> entry : map.entrySet()) {
String key = entry.getKey();
Integer Value = entry.getValue();
}4 . Map的常用实现类
（1）HashMap
①Map接口最常用的实现类是HashMap
②HashMap内部存储不保证有序
HashMap在遍历时的顺序不一定是put放入的顺序，也不一定是Key的排序顺序。
（2）SortedMap
①SortMap可以保证遍历时以Key的顺序排序
②SortedMap的实现类是TreeMap类
遍历TreeMap：
Map<String, Integer> map = new TreeMap<>();
map.put("Zero", 1);
map.put("One", 2);
map.put("Two", 3);
for(String key : mapkeySet()) {
System.out.println(key);
}
//One, Two, Zero
//遍历后得到的结果顺序是按照字母排序的注意：排序只能作用于Key，与Value没有任何关系
（二）equals和hashCode
1 . 作为Key的对象必须正确覆写equals()方法
在Map内部对Key做比较是通过equals方法实现的，这一特性与List查找元素需要正确覆写Object的equals方法的原理是相同的，所以在使用Map时必须保证作为Key的对象必须正确覆写equals()方法
2 . 作为Key的对象必须正确覆写hashCode()方法
HashMap通过计算Key的hashCode()定位Key的存储位置，继而获得Value，任何一个对象都拥有一个hashCode()方法，它是从Object对象继承下来的。
hashCode实际上是一个int值，HashMap通过对hashCode进行计算，最后映射到某一位置，然后得到Value的值。所以，作为Key的对象必须正确覆写hashCode()方法。
如果两个对象相等，则两个对象的hashCode()必须相等
如果两个对象不相等，则两个对象的hashCode()不必相等
如果一个对象覆写了equals()方法，就必须正确覆写hashCode()方法：
如果a.equals(b) == true，则a.hashCode() == b.hashCode()
如果a.equals(b) == false，则a和b的hashCode()尽量不要相等（可以相等，会造成效率下降）
（三）Properties
Properties用于读取配置文件：
编写一个setting.properties文件用来表示Key = Value
# setting.properties;//#开头表示注释
url = https://www.feiyangedu.com/language=JavaProperties文件只支持ACSII编码，如果需要使用中文，就只能使用16进制字符的形式。
1 . 从文件系统读取.Properties文件
String f = "C:\\conf\\setting.properties";
Properties props = new Properties();
props.load(new FileInputSteam(f));//调用load()方法获取指定文件
String url = props.getProperty("url");//获取指定的Key对应的Value，如果Key不存在会返回null
String desc = props.getProperty("description", "default description");//当Key不存在时会返回默认值2 . 从classpath读取.Properties文件
Properties props = new Properties();
props.load(getClass().getResourceAsSteam("/common/setting.properties"));//调用getClass()方法获取指定文件
String url = props.getProperty("url");//获取指定的Key对应的Value，如果Key不存在会返回null
String desc = props.getProperty("description", "default description");//当Key不存在时会返回默认值3 . 读取多个.Properties文件
如果两个.Properties文件包含有相同的Key，后读取的Key-Value会覆盖前面读取的Key-Value，这个特性可以让我们将默认的配置文件放在classpath中，然后根据计算机的环境编写另外的配置文件，然后就可以覆盖某些默认的配置。
注意：Properties实际上是从Hashtable派生，但只需调用getProperty和setProperty
四、Set
1 . Set< E >用于存储不重复元素的集合
它提供了几个方法：
（1）boolean add(E e)：添加元素
（2）boolean remove(Object o)：删除元素
（3）boolean contains(Object o)：判断元素是否存在
（4）int size()：返回size集合的当前元素个数
Set<String> set = ...
set.add("Zero");//true
set.add("One");//true
set.size();//2
set.add("Zero");//false（添加失败，元素重复）
set.size();//2
set.contains("Zero");//true（判断一个元素是否存在）
set.remove("Zero");//true（调用remove()方法移除一个元素）
set.size();//1（删除了一个元素）
set.remove("Two");//false（不存在"Two"这个元素）
set.size();//1所以：
（1）Set相当于一个不存储Value的Map
（2）可以用来去除重复元素
（3）放入Set的元素需要正确实现equals()和hashCode()
2 . Set不保证有序
（1）HashSet是无序的
（2）TreeSet是有序的
（3）实现了SortedSet接口的Set是有序的
Set<String> set = new HashSet<>();
set.add("Zero");
set.add("One");
set.add("Two");
for(String s : set) {
System.out.println(s);
}
//"One", "Zero", "Two"TreeSet可以按照字母顺序进行排序：
Set<String> set = new TreeSet<>();
set.add("Zero");
set.add("One");
set.add("Two");
for(String s : set) {
System.out.println(s);
}
//"One", "Two", "Zero"
//注意：这里的顺序是元素排序的顺序而不是添加时的顺序TreeSet按元素顺序进行排序，可以进行自定义排序算法
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
public class Main {
public static void main(String[] args) {
//定义一个List，其中包含一些重复元素
List<String> list1 = Arrays.asList("pear", "apple", "banana", "orange", "apple", "banana");
//调用removeDuolicate()方法去除重复元素
List<String> list2 = removeDuplicate(list1);
System.out.println(list2);
}
//通过定义removeDuplicate()方法去除重复的元素
static List<String> removeDuplicate(List<String> list) {
//创建Set用来存储不重复的元素
//然后在创建HashSet时传入list，此时存储的是无序的元素
Set<String> set = new HashSet<>(list);
//将set转化为ArrayList就可以得到不包含重复元素的List
return new ArrayList<String>(set);
}
}
//运行结果为：banana, orange, apple, pear下面我们做一个练习：
将List的元素去重，但保留元素在List中的原始顺序
即由：[“abc”, “xyz”, “abc”, “www”, “edu”, “www”, “abc”]
变为：[“abc”, “xyz”, “www”, “edu”]
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class Main {
public static void main(String[] args) {
//定义list包含若干元素，其中包含部分重复元素
List<String> list1 = Arrays.asList("abc", "xyz", "abc", "www", "edu", "www", "abc");
//调用removeDuplicate()方法去除重复元素
List<String> list2 = removeDuplicate(list1);
//打印list2的运行结果
System.out.println(list2);
}
//定义removeDuplicate()方法
private static List<String> removeDuplicate(List<String> list1) {
//创建Set用来存储不重复的元素集合，将list1传入LinkedHashSet从而让元素按照元素放入顺序进行排序
Set<String> set = new LinkedHashSet<>(list1);
//将set转化为ArrayList，得到不包含重复元素的list
return new ArrayList<String>(set);
}
}
//运行结果：[abc, xyz, www, edu]五、Queue
（一）什么是Queue
1 . Queue的概念
Queue< E >实现了先进先出（FIFO——First In First Out）队列：
什么是先进先出队列呢？
假设我们在超市的购物结算窗口，先进入结算通道的购物者总是最先出去，这样的队列就是一个先进先出队列。
在Java中，LinkedList实现了Queue< E >接口，可以直接将LinkedList作为Queue< E >来使用。
2 . Queue的常用操作
（1）获取队列长度：size()
（2）添加元素到队尾：boolean add(E e)/boolean offer(E e)
（3）获取队列头部元素并删除：E remove()/E poll()
（4）获取队列头部元素但不删除：E element()/E peek()
我们可以看到，添加或获取元素都提供了两种操作方法，这是因为：
在添加或获取元素失败时：
那么什么情况下添加元素会失败呢？
比如，如果一个队列拥有最大长度限制，那么添加就有可能失败
获取队首元素失败的情况，可能是由于这个队列是一个空队列
如何添加Queue：
Queue<String> q = ...
if(q.offer("Zero")) {
//add ok
} else {
//add failed
}如何获取队首元素并删除：
Queue<String> q = ...
if(q.isEmpty()) {//调用isEmpty()方法判断队列是否为空
//cannot poll
} else {
String first = q.poll();
}如何获取队首元素但不删除：
Queue<String> q = ...
if(q.isEmpty()) {//调用isEmpty()方法判断队列是否为空
//cannot peek
} else {
String first = q.peek();
}下面是一个例子：
首先定义一个Person类：
public class Person {
private final String name;
private final int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "(Person: " + name + ", " + age + ")";
}
}然后定义Main方法：
import java.util.LinkedList;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
//定义一个Queue对象，由LinkedList向上转型为Queue
Queue<Person> queue = new LinkedList<>();
//调用offer()方法放入对象
queue.offer(new Person("Ming", 12));
queue.offer(new Person("Hong", 15));
queue.offer(new Person("Jun", 17));
//调用poll()方法从queue中取出对象
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
//运行结果为：
//(Person: Ming, 12)
//(Person: Hong, 15)
//(Person: Jun, 17)
//null
//第四次调用poll()方法，由于queue为空，所以返回值为null
//所以要避免将null添加至队列中
}
}（二）使用PriorityQueue
1 . PriorityQueue< E >的优先队列
使用remove()/poll()方法时总是取优先级最高的元素
PriorityQueue< E >所实现的优先队列，就好比在银行业务中，所有人都是按照顺序排队，但是很可能不会按照顺序进行业务办理，而优先给VIP客户提供业务办理服务，这种队列就称为优先队列
2 . PriorityQueue< E >的常用操作方法
PriorityQueue< E >具有Queue< E >的接口，所以可以使用Queue< E >的常用操作方法：
（1）添加元素到队尾：boolean add(E e)/boolean offer(E e)
（2）获取队列头部元素并删除：E remove()/E poll()
（3）获取队列头部元素但不删除：E element()/E peek()
注意：默认按元素比较的顺序排序（必须实现Comparable接口）
可以通过Comparator自定义排序算法（不必实现Comparable接口）
下面是一个例子：
定义Person类，并添加comparable接口：
public class Person implements Comparable<Person> {
private final String name;
private final int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
@Override
public String toString() {
return "(Person: " + name + ", " + age + ")";
}
public int compareTo(Person o) {
return this.name.compareTo(o.name);
}
}定义Main方法：
import java.util.PriorityQueue;
import java.util.Queue;
public class Main {
public static void main(String[] args) {
Queue<Person> queue = new PriorityQueue<>();
queue.offer(new Person("Ming", 12));
queue.offer(new Person("Hong", 15));
queue.offer(new Person("Jun", 17));
System.out.println(queue.poll());
System.out.println(queue.poll());
System.out.println(queue.poll());
}
}
//输出结果：
//(Person: Hong, 15)
//(Person: Jun, 17)
//(Person: Ming, 12)（三）使用Deque
1 . Deque的作用
Deque< E >实现了一个双端队列（Double Ended Queue）
（1）既可以添加元素到队尾，也可以添加元素到队首
（2）既可以从队首获取元素，也可以从队尾获取元素
2 . Queue与Deque的方法差异
为了避免Queue与Deque的方法使用混淆，调用Deque< E >时我们总是使用xxxFirst()/xxxLast()方法
3 . Deque的实现类
（1）ArrayDeque
（2）LinkedList
下面是一个例子：
import java.util.Deque;
import java.util.LinkedList;
public class Main {
public static void main(String[] args) {
//定义LinkedList并向上转型为Deque<>接口
Deque<String> deque = new LinkedList<>();
deque.offerLast("end"); // "end"
deque.offerFirst("C"); // "C", "end"
deque.offerFirst("B"); // "B", "C", "end"
deque.offerFirst("A"); // "A", "B", "C", "end"
System.out.println(deque.pollLast());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
System.out.println(deque.pollFirst());
}
}
//运行结果：
//end
//A
//B
//C
//null六、栈Stack
1 . Stack的概念
Stack（栈）是一种后进先出（LIFO-Last In First Out）的数据结构
我们可以看作是一端封闭另一端开放的队列，先放入的元素永远置于栈的底部，所以只能最后取出
2 . Stack的常用方法
（1）push(E e)：把元素压栈
（2）pop()：弹出栈顶元素
3 . Deque接口
使用Deque可以实现Stack的功能：
（1）push(E e)：addFirst(E e)
（2）pop()：removeFirst()
（3）peek()：peekFirst()
注意：Java没有单独的去定义一个Stack接口，是由于Java中存在一个遗留类Class的名字就是Stack，处于兼容性方面的考虑，就不能去创建Stack接口
4 . Stack的作用
（1）方法（函数）的嵌套调用：
static void main(String[] args) {
foo(123);
}
Static String foo(x) {
return "F-" + bar(x + 1);
}
static int bar(int x) {
return x << 2;
}注意：嵌套调用过多会造成栈溢出（*Error）
（2）进行不同进制的转换
将整数转换为十六进制表示的String
例如十进制整数12500转化为十六进制表示的String（0x30d4）
转化步骤：
①首先，准备一个空栈
②然后计算 12500 / 16 = 781…4
③然后对余数4进行压栈操作
④然后计算781 / 16 = 48…d
⑤然后对余数d进行压栈操作
⑥然后计算48 / 16 = 3…0
⑦然后对余数0进行压栈操作
⑧然后计算3 / 16 = 0…3
⑨然后对余数3进行压栈操作
⑩当计算结果的商为0时，计算结束
然后将栈内的所有元素依次弹出：30d4
这样就将十进制数12500转换为十六进制0x30d4表示
（3）将中缀表达式编译为后缀表达式
我们日常使用的数学四则运算使用的是中缀表达式编写
例如：
中缀表达式：1 + 2 * ( 9 - 5 )
在计算机中是无法直接计算中缀表达式的，编译器会自动将中缀表达式转换为后缀表达式：1 2 9 5 - * + ，而计算机在计算后缀表达式时也是使用栈来进行操作的
计算步骤：
①首先，准备一个空栈
②然后，依次将遇到的数字放入栈中
③当遇到“-”时，弹出栈顶的两个元素，计算9 - 5 = 4，将计算结果压栈
④当遇到“”时，弹出栈顶的两个元素，计算2 4 = 8，将计算结果压栈
⑤当遇到“+”时，弹出栈顶的两个元素，计算1 + 8 = 9，将计算结果压栈
⑥最后计算结束时，弹出栈中唯一的元素，得到计算结果：9
下面我们演示一个复杂的例子：
定义Main方法：
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
//字符串表示一个中缀表达式
String s = "1 + 2 * (9 - 5)";
Calculator calc = new Calculator();
//通过compile()方法将中缀表达式编译为后缀表达式
Object[] exp = calc.compile(s);
//通过calculate()方法计算后缀表达式并得到结果
int result = calc.calculate(exp);
System.out.println("[calculate] " + s + " => " + expressionToString(exp) + " => " + result);
}
//运行程序后可以看到结果：
//[calculate] 1 + 2 * (9 - 5) => 1 2 9 5 - * + => 9
//中缀表达式先编译为后缀表达式，然后计算出后缀表达式的值
static String expressionToString(Object[] exp) {
List<String> list = new ArrayList<>(exp.length);
for (Object e : exp) {
list.add(e.toString());
}
return String.join(" ", list);
}
}下面是compile()方法的源码：
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;
public class Calculator {
public Object[] compile(String s) {
Object[] parsed = parseAsExpression(s);
List<Object> output = new LinkedList<>();
//使用LinkedList<>转换为Deque<>，使用Deque接口作为栈
Deque<Character> stack = new LinkedList<>();
//编译中缀表达式的主要思想是：
for (Object e : parsed) {
//当我们遇到一个数字的时候就直接输出这个数字
if (e instanceof Integer) {
output.add(e);
} else {
char ch = (Character) e;
switch (ch) {
//当我们遇到一个符号时：
//如果是右括号，需要从栈中寻找到其对应的左括号
//并且在寻找过程中，把遇到的符号输出
case ')':
// find '(' in stack:
for (;;) {
if (stack.isEmpty()) {
throw new IllegalStateException("Compile error: " + s);
}
char top = stack.pop();
if (top == '(') {
break;
} else {
output.add(top);
}
}
break;
//当遇到一个左括号时，直接入栈：
case '(':
stack.push(ch);
break;
//当遇到四则运算符号时，从栈底找到优先级更高的符号进行输出，然后将符号入栈
case '+':
case '-':
case '*':
case '/':
// find all operators that >= ch:
//最后，把栈内的所有元素输出，就得到了后缀表达式：
while (!stack.isEmpty()) {
char first = stack.peek();
if (priority(first) >= priority(ch)) {
stack.pop();
output.add(first);
} else {
break;
}
}
stack.push(ch);
break;
default:
throw new IllegalStateException("Compile error: " + s);
}
}
}
while (!stack.isEmpty()) {
output.add(stack.pop());
}
return output.toArray();
}
public int calculate(Object[] expression) {
//使用Deque<>来表示一个栈：
Deque<Integer> stack = new LinkedList<>();
for (Object e : expression) {
//如果遇到数字，将数字直接入栈：
if (e instanceof Integer) {
stack.push((Integer) e);
} else {
//如果遇到符号，就弹出栈底的两个元素，计算并得到结果，再将结果入栈：
char op = (Character) e;
int n1 = stack.pop();
int n2 = stack.pop();
int r = operate(op, n2, n1);
stack.push(r);
}
}
//最后入栈的数字就是计算的结果：
return stack.pop();
}
Object[] parseAsExpression(String s) {
List<Object> list = new ArrayList<>();
for (char ch : s.toCharArray()) {
if (ch >= '0' && ch <= '9') {
int n = Integer.parseInt(String.valueOf(ch));
list.add(n);
} else if ("+-*/()".indexOf(ch) != (-1)) {
list.add(ch);
} else if (ch == ' ') {
// ignore white space
} else {
throw new IllegalArgumentException("Compile error: invalid char \'" + ch + "\'");
}
}
return list.toArray();
}
// priority from high to low: '*', '/' > '+', '-' > '('
int priority(char op) {
switch (op) {
case '*':
case '/':
return 2;
case '+':
case '-':
return 1;
case '(':
return 0;
default:
throw new IllegalArgumentException("bad operator: " + op);
}
}
int operate(char operator, int a, int b) {
switch (operator) {
case '+':
return a + b;
case '-':
return a - b;
case '*':
return a * b;
case '/':
return a / b;
default:
throw new UnsupportedOperationException();
}
}
}5 . Stack练习
使用Stack将整数转换为十六进制字符串表示
toHex(12500) => “30d4”
进制转换算法：
①不断对整数除以16，得到商和余数，余数压栈
②用得到的商重复步骤1
③当商为0时，计算结束。将栈中的数依次弹出并组成String
七、Iterator和Collections
（一）Iterator迭代模式
我们发现Java的许多集合类都可以使用for…each循环：
例如List，Set，Queue，Deque等等
我们以List为例：
实际上Java的编译器并不知道如何遍历一个List，编译器只是将for…each循环通过Iterator改写为普通的for循环
List<String> list = ...
for(String s : list) {
}
//上面的代码会被编译器改写为下面这段代码的形式：
List<String> list = ...
for(Iterator<String> it = list.iterator();
it.hasNext();) {
String s = it.next();
}那么我们如何让自己编写的集合类使用for…each循环呢？
可以通过一下步骤：
（1）实现Iterator接口
（2）返回Iterator对象
（3）用Iterator迭代对象
下面是一段代码实践：
首先定义Main方法：
public class Main {
public static void main(String[] args) throws Exception {
ReadOnlyList<String> list = new ReadOnlyList<>("apple", "pear", "orange");
for (String s : list) {
System.out.println(s);
}
}
}
//运行结果为：
//apple
//pear
//orange定义ReadOnlyList方法：
import java.util.Iterator;
//首先实现Iterator<>接口
public class ReadOnlyList<E> implements Iterable<E> {
//在ReadOnlyList内部使用数组来存储需要存储的元素
E[] array;
@SafeVarargs
public ReadOnlyList(E... array) {
this.array = array;
}
//实现一个Iterator()方法，用来返回一个Iterator对象
@Override
public Iterator<E> iterator() {
return new ReadOnlyIterator();
}
class ReadOnlyIterator implements Iterator<E> {
//通过索引判断是否拥有下一个元素，以及如何获取下一个元素
int index = 0;
//正确实现hasNext()方法
@Override
public boolean hasNext() {
return index < ReadOnlyList.this.array.length;
}
//正确实现next()方法
@Override
public E next() {
E e = array[index];
index++;
return e;
}
}
}使用Iterator模式进行迭代的好处：
（1）对任何集合都使用同一种访问模型
①可以通过Iterator对象实现
②也可以通过for…each循环编译成让编译器把代码编译成使用Iterator
（2）调用者对集合内部结构一无所知
在使用List时，并不关心ArrayList使用数组来存储，还是LinkedList使用链表来存储
（3）集合类返回的Iterator对象知道如何迭代
（4）Iterator是一种抽象的数据访问模型
调用者无需知道在集合内部是如何具体存储这些元素的，便可以直接进行迭代
（二）使用Collections
1 . Collections的作用
Collections是JDK提供的集合工具类
注意区分Collection（接口）与Collections（工具类）的区别
Collections提供了各种静态方法能够更方便的操作各种集合，一般通过方法的参数就能够确认该方法实现的功能
例如：boolean addAll(Collections< ? super T > c, T…elements)
可以给一个Collections类型的集合添加若干元素
2 . 创建空集合
（1）emptyList ：List< T > emptyList()
（2）emptySet ：Set< T > emptySet()
（3）emptyMap ：Map< K, V > emptyMap()
注意：创建的集合是不可变更的，也就是说，无法向该集合添加元素
3 . 创建单元素集合
（1）singleton：Set< T > singleton(T o)
（2）singletonList ：List< T > singletonList(T o)
（3）singletonMap ：Map< K, V > singletonMap(K Key, V Value)
注意：创建的集合是不可变更的，也就是说，无法向该集合添加元素
4 . 对List排序
sort()方法可以对List进行排序，这时必须传入可变的List
sort()拥有两个重载方法：
（1）void sort(List< T > list)：元素必须实现comparable接口
（2）void sort(List< T > list, Comparator< ? super T > C)：传入指定的Comparator类来指定排序算法，元素不必实现comparable接口
5 . 对元素洗牌
如果我们需要随机重置List元素，可以使用suffle进行洗牌：
void suffle(List < ? > list)
如果我们选定的List是有序的List，通过suffle方法可以在内部随机打乱List的元素的顺序
6 . 创建不可变集合
将可变集合变为不可变集合：
（1）unmodifiableList：List< T > unmodifiableList(List < ? extends T > list)
（2）unmodifiableSet：Set< T > unmodifiableSet(Set < ? extends T > set)
（3）unmodifiableMap：Map< K, V > unmodifiableMap(Map < ? extends K, ? extends V > map)
7 . 创建线程安全的集合
将线程不安全的集合变为安全的集合：
（1）synchronizedList：List< T > synchronizedList(List< T > list)
（2）synchronizedSet：Set< T > synchronizedSet(Set< T > set)
（3）synchronizedMap：Map< K, V > synchronizedMap(Map< K, V > map)
注意：由于从JDK5.0版本开始Java引入了更高效的迸发集合类，所以此方法不推荐使用
上一篇： JAVA自定义注解
推荐阅读
-
Java学习笔记（五）——Java集合
-
java底层学习 博客分类： javaweb
-
mongo-java-driver -3.2.2学习笔记-02-MongoDB Driver Admin Quick Tour
-
自学Java基础知识总结个人笔记
-
JAVA List（或者数据库数据集合）导出为CSV
-
sina sae 部署 java ssh 项目 博客分类： 学习笔记 saejavassh
-
Java 自定义运行时异常抓取用法笔记
-
Java的第十六周学习
-
寒假宅喵java学习
-
eclipse 之 scrapbook 博客分类： JAVA开发工具web开发学习笔记 eclipsescrapbook