欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Java学习笔记(五)——Java集合

程序员文章站 2024-03-21 16:54:16
...

一、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
    }
}
//打印结果变为false

equals()编写方法:

(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=Java

Properties文件只支持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()
我们可以看到,添加或获取元素都提供了两种操作方法,这是因为:
在添加或获取元素失败时:
Java学习笔记(五)——Java集合
那么什么情况下添加元素会失败呢?
比如,如果一个队列拥有最大长度限制,那么添加就有可能失败
获取队首元素失败的情况,可能是由于这个队列是一个空队列
如何添加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的方法差异

Java学习笔记(五)——Java集合
为了避免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 学习心得