java-集合的补充

常见基础集合汇总

数据结构：栈

数据结构分为：

（1）逻辑结构 ：--》思想上的结构--》卧室，厨房，卫生间 ---》线性表（数组，链表），图，树，栈，队列

（2）物理结构 ：--》真实结构--》钢筋混凝土+牛顿力学------》紧密结构（顺序结构），跳转结构（链式结构）?

栈：

特点：后进先出（LIFO - last in first out）：

实际应用：

（1）内存分析：形参，局部变量放入栈中。放入的那个区域的数据结构就是按照栈来做的。

（堆：利用完全二叉树的结构来维护一组数据）

1.package com.msb.test01;
2.
3.import java.util.Stack;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class Test {
9.    //这是main方法，程序的入口
10.    public static void main(String[] args) {
11.        /*
12.        Stack是Vector的子类，Vector里面两个重要的属性：
13.        Object[] elementData;底层依然是一个数组
14.        int elementCount;数组中的容量
15.         */
16.        Stack s = new Stack();
17.        s.add("A");
18.        s.add("B");
19.        s.add("C");
20.        s.add("D");
21.        System.out.println(s);//[A, B, C, D]
22.        System.out.println("栈是否为空：" + s.empty());
23.
24.        System.out.println("查看栈顶的数据，但是不移除：" + s.peek());
25.        System.out.println(s);
26.
27.        System.out.println("查看栈顶的数据，并且不移除：" + s.pop());
28.        System.out.println(s);
29.
30.        s.push("D");//和add方法执行的功能一样，就是返回值不同
31.        System.out.println(s);
32.
33.    }
34.}

（2）网络浏览器多会将用户最近访问过的网址组织为一个栈。这样，用户每访问一个新页面，其地址就会被存放至栈顶；而用户每按下一次“后退”按钮，即可沿相反的次序访问此前刚访问过的页面。

（3）主流的文本编辑器也大都支持编辑操作的历史记录功能（ctrl + z：撤销，ctrl + y：恢复），用户的编辑操作被依次记录在一个栈中。一旦出现误操作，用户只需按下“撤销”按钮，即可取消最近一次操作并回到此前的编辑状态。

Stack

1.package com.msb.test01;
2.
3.import java.util.Stack;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class Test {
9.    //这是main方法，程序的入口
10.    public static void main(String[] args) {
11.        /*
12.        Stack是Vector的子类，Vector里面两个重要的属性：
13.        Object[] elementData;底层依然是一个数组
14.        int elementCount;数组中的容量
15.         */
16.        Stack s = new Stack();
17.        s.add("A");
18.        s.add("B");
19.        s.add("C");
20.        s.add("D");
21.        System.out.println(s);//[A, B, C, D]
22.        System.out.println("栈是否为空：" + s.empty());
23.
24.        System.out.println("查看栈顶的数据，但是不移除：" + s.peek());
25.        System.out.println(s);
26.
27.        System.out.println("查看栈顶的数据，并且不移除：" + s.pop());
28.        System.out.println(s);
29.
30.        s.push("D");//和add方法执行的功能一样，就是返回值不同
31.        System.out.println(s);
32.
33.    }
34.}

同步类容器

比如ArrayList，HashMap，线程不安全，现在想把线程不安全的集合转换为线程安全的集合：

1.public class Test01 {
2.    //这是main方法，程序的入口
3.    public static void main(String[] args) {
4.        //ArrayList为案例：从线程不安全  转为线程安全：
5.        List list = Collections.synchronizedList(new ArrayList());
6.    }
7.}

试试ArrayList的线程不安全：

1.package com.msb.test02;
2.
3.import java.util.ArrayList;
4.import java.util.concurrent.ExecutorService;
5.import java.util.concurrent.Executors;
6.
7./**
8. * @author : msb-zhaoss
9. */
10.public class Demo {
11.    //这是main方法，程序的入口
12.    public static void main(String[] args) {
13.        //创建一个ArrayList集合：
14.        ArrayList list = new ArrayList();
15.
16.        //创建一个线程池：线程池定长100
17.        ExecutorService es = Executors.newFixedThreadPool(100);
18.
19.        //并发向集合中添加10000个数据：
20.        for (int i = 0; i < 10000; i++) {
21.            //每个线程处理任务：run方法中的内容就是线程单元，任务，实际线程执行的部分
22.            es.execute(new Runnable() {
23.                @Override
24.                public void run() {
25.                    list.add("aaa");
26.                }
27.            });
28.        }
29.
30.        //关闭线程池：
31.        es.shutdown();
32.
33.        //监控线程是否执行完毕：
34.        while(true){
35.            //线程都执行完以后返回true
36.            if(es.isTerminated()){
37.                System.out.println("所有的子线程都执行完毕了！");
38.                //执行完毕以后看一下集合中元素的数量：
39.                System.out.println(list.size());
40.                if(list.size() == 10000){
41.                    System.out.println("线程安全！");
42.                }else{
43.                    System.out.println("线程不安全！");
44.                }
45.
46.                //线程执行完以后，while循环可以停止：
47.                break;
48.            }
49.        }
50.    }
51.}

结果：

利用同步类容器解决：

1.package com.msb.test02;
2.
3.import java.util.ArrayList;
4.import java.util.Collections;
5.import java.util.List;
6.import java.util.concurrent.ExecutorService;
7.import java.util.concurrent.Executors;
8.
9./**
10. * @author : msb-zhaoss
11. */
12.public class Demo {
13.    //这是main方法，程序的入口
14.    public static void main(String[] args) {
15.        //创建一个ArrayList集合：
16.        ArrayList oldlist = new ArrayList();
17.        List list = Collections.synchronizedList(oldlist);
18.
19.        //创建一个线程池：线程池定长100
20.        ExecutorService es = Executors.newFixedThreadPool(100);
21.
22.        //并发向集合中添加10000个数据：
23.        for (int i = 0; i < 10000; i++) {
24.            //每个线程处理任务：run方法中的内容就是线程单元，任务，实际线程执行的部分
25.            es.execute(new Runnable() {
26.                @Override
27.                public void run() {
28.                    list.add("aaa");
29.                }
30.            });
31.        }
32.
33.        //关闭线程池：
34.        es.shutdown();
35.
36.        //监控线程是否执行完毕：
37.        while(true){
38.            //线程都执行完以后返回true
39.            if(es.isTerminated()){
40.                System.out.println("所有的子线程都执行完毕了！");
41.                //执行完毕以后看一下集合中元素的数量：
42.                System.out.println(list.size());
43.                if(list.size() == 10000){
44.                    System.out.println("线程安全！");
45.                }else{
46.                    System.out.println("线程不安全！");
47.                }
48.
49.                //线程执行完以后，while循环可以停止：
50.                break;
51.            }
52.        }
53.    }
54.}

结果：

源码解析：

ConcurrentMap并发容器

JDK5.0之后提供了多种并发类容器可以替代同步类容器，提升性能、吞吐量

ConcurrentHashMap替代HashMap、HashTable

ConcurrentSkipListMap替代TreeMap?

简单原理：

并发情况下，验证提高性能：

ConcunrrentHashMap :

1.public class Test {
2.    //这是main方法，程序的入口
3.    public static void main(String[] args) {
4.        //选择一个容器：
5.        ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
6.        
7.        //创建10个线程：
8.        for (int i = 0; i < 10; i++) {
9.            new Thread(new Runnable() {
10.                @Override
11.                public void run() {
12.                    long startTime = System.currentTimeMillis();
13.                    for (int j = 0; j < 1000000; j++) {
14.                        map.put("test" + j , j);
15.                    }
16.                    long endTime = System.currentTimeMillis();
17.                    System.out.println("一共需要的时间：" + (endTime - startTime));
18.                }
19.            }).start();
20.        }
21.    }
22.}

结果：

Hashtable：

1.package com.msb.test03;
2.
3.import java.util.Hashtable;
4.import java.util.concurrent.ConcurrentHashMap;
5.
6./**
7. * @author : msb-zhaoss
8. */
9.public class Test {
10.    //这是main方法，程序的入口
11.    public static void main(String[] args) {
12.        //选择一个容器：
13.        //ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
14.        Hashtable map = new Hashtable();
15.        //创建10个线程：
16.        for (int i = 0; i < 10; i++) {
17.            new Thread(new Runnable() {
18.                @Override
19.                public void run() {
20.                    long startTime = System.currentTimeMillis();
21.                    for (int j = 0; j < 1000000; j++) {
22.                        map.put("test" + j , j);
23.                    }
24.                    long endTime = System.currentTimeMillis();
25.                    System.out.println("一共需要的时间：" + (endTime - startTime));
26.                }
27.            }).start();
28.        }
29.    }
30.}

结果：

HashMap：

1.package com.msb.test03;
2.
3.import java.util.HashMap;
4.import java.util.Hashtable;
5.import java.util.concurrent.ConcurrentHashMap;
6.
7./**
8. * @author : msb-zhaoss
9. */
10.public class Test {
11.    //这是main方法，程序的入口
12.    public static void main(String[] args) {
13.        //选择一个容器：
14.        //ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
15.        //Hashtable map = new Hashtable();
16.        HashMap map = new HashMap();
17.        //创建10个线程：
18.        for (int i = 0; i < 10; i++) {
19.            new Thread(new Runnable() {
20.                @Override
21.                public void run() {
22.                    long startTime = System.currentTimeMillis();
23.                    for (int j = 0; j < 1000000; j++) {
24.                        map.put("test" + j , j);
25.                    }
26.                    long endTime = System.currentTimeMillis();
27.                    System.out.println("一共需要的时间：" + (endTime - startTime));
28.                }
29.            }).start();
30.        }
31.    }
32.}

线程安全的HashMap：

1.package com.msb.test03;
2.
3.import java.util.Collections;
4.import java.util.HashMap;
5.import java.util.Hashtable;
6.import java.util.Map;
7.import java.util.concurrent.ConcurrentHashMap;
8.
9./**
10. * @author : msb-zhaoss
11. */
12.public class Test {
13.    //这是main方法，程序的入口
14.    public static void main(String[] args) {
15.        //选择一个容器：
16.        //ConcurrentHashMap<String,Integer> map = new ConcurrentHashMap<>();
17.        //Hashtable map = new Hashtable();
18.        HashMap oldmap = new HashMap();
19.        Map map = Collections.synchronizedMap(oldmap);
20.        //创建10个线程：
21.        for (int i = 0; i < 10; i++) {
22.            new Thread(new Runnable() {
23.                @Override
24.                public void run() {
25.                    long startTime = System.currentTimeMillis();
26.                    for (int j = 0; j < 1000000; j++) {
27.                        map.put("test" + j , j);
28.                    }
29.                    long endTime = System.currentTimeMillis();
30.                    System.out.println("一共需要的时间：" + (endTime - startTime));
31.                }
32.            }).start();
33.        }
34.    }
35.}
36.

结果：

总结：

ConcurrentHashMap：性能高，线程安全

Hashtable: 线程安全，性能低

HashMap:线程不安全，性能高

线程安全的HashMap：线程安全，性能低

COW并发容器

【1】COW类并发容器，全称：Copy ?On ?Write容器，写时复制容器。（读写分离容器） ? ??

【2】原理：

向容器中添加元素时，先将容器进行Copy复制出一个新容器，然后将元素添加到新容器中，再将原容器的引用指向新容器。

并发读的时候不需要锁定容器，因为原容器没有变化，所以可以读取原容器中的值，使用的是一种读写分离的思想。

3】这种设计的好处是什么呢？

注意上面的操作arr数组本身是无锁的，没有锁，在添加数据的时候，做了额外的复制，

此时如果有线程来读数据，那么读取的是老arr的数据，此时arr的地址还没有改呢，在我添加元素的过程中，

无论有多少个线程来读数据，都是读的原来的arr，不是新的arr

所以性能很高，读写分离。提高了并发的性能。如果再读再复制...

【4】注意：

CopyOnWrite容器只能保证数据的最终一致性，不能保证数据实时一致性。

所以如果你希望写入的的数据，马上能读到，请不要使用CopyOnWrite容器。

【5】适合特定场合：

这个应用场景显而易见，适合读多写少的情况。如果一万个线程都添加操作，都在集合中添加数据，那数组不断复制，长度不断+1，

那JVM肯定一直往上飙升，你用的时候肯定要评估使用场景的。

由于每次更新都会复制新容器，所以如果数据量较大并且更新操作频繁则对内存消耗很高，建议在高并发读的场景下使用。

【6】主要讲解：

COW容器有两种一种是CopyonWriteArrayList，一种是CopyOnWriteArraySet

一个是替代ArrayList，一个是代替Set ?

CopyOnWriteArrayList

【1】代码：

1.package com.msb.test04;
2.
3.import java.util.concurrent.CopyOnWriteArrayList;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class Test {
9.    //这是main方法，程序的入口
10.    public static void main(String[] args) {
11.        CopyOnWriteArrayList<Integer> list = new CopyOnWriteArrayList<>();
12.        //添加方法：
13.        list.add(1);
14.        list.add(2);
15.        list.add(3);
16.        list.add(4);
17.        System.out.println(list);//[1, 2, 3, 4]
18.        list.add(3);//add方法无论元素是否存在，都可以添加进去--》添加重复的元素
19.        System.out.println(list);//[1, 2, 3, 4, 3]
20.        //adj. 缺席的；缺少的；心不在焉的；茫然的
21.        list.addIfAbsent(33);//添加不存在的元素--》不可以添加重复的数据
22.        System.out.println(list);//[1, 2, 3, 4, 3, 33]
23.    }
24.}
25.

【2】源码分析：

1.public class CopyOnWriteArrayList<E>{
2.        //底层基于数组实现的
3.        private transient volatile Object[] array;
4.        
5.        public CopyOnWriteArrayList() {
6.        setArray(new Object[0]);
7.    }
8.        
9.        final void setArray(Object[] a) {
10.        array = a; // array = new Object[0]
11.    }
12.        //add方法：
13.        public boolean add(E e) {
14.        final ReentrantLock lock = this.lock;
15.        lock.lock();
16.        try {
17.                        //返回底层array数组,给了elements
18.            Object[] elements = getArray();
19.                        //获取elements的长度---》获取老数组的长度
20.            int len = elements.length;
21.                        //完成数组的复制，将老数组中的元素复制到新数组中，并且新数组的长度加1操作
22.            Object[] newElements = Arrays.copyOf(elements, len + 1);
23.                        //将e元素放入新数组最后位置
24.            newElements[len] = e;
25.                        //array数组的指向从老数组变为新数组
26.            setArray(newElements);
27.            return true;
28.        } finally {
29.            lock.unlock();
30.        }
31.    }
32.        
33.        
34.        final Object[] getArray() {
35.        return array;//返回底层数组
36.    }
37.        
38.        
39.        private boolean addIfAbsent(E e, Object[] snapshot) {
40.        final ReentrantLock lock = this.lock;
41.        lock.lock();
42.        try {
43.                        //取出array数组给current
44.            Object[] current = getArray();
45.            int len = current.length;
46.            if (snapshot != current) {
47.                // Optimize for lost race to another addXXX operation
48.                int common = Math.min(snapshot.length, len);
49.                                //遍历老数组：
50.                for (int i = 0; i < common; i++)
51.                                        //eq(e, current[i])将放入的元素和老数组的每一个元素进行比较，如果有重复的元素，就返回false，不添加了
52.                    if (current[i] != snapshot[i] && eq(e, current[i]))
53.                        return false;
54.                if (indexOf(e, current, common, len) >= 0)
55.                        return false;
56.            }
57.                        //完成数组的复制，将老数组中的元素复制到新数组中，并且新数组的长度加1操作
58.            Object[] newElements = Arrays.copyOf(current, len + 1);
59.                        //将e元素放入新数组最后位置
60.            newElements[len] = e;
61.                        //array数组的指向从老数组变为新数组
62.            setArray(newElements);
63.            return true;
64.        } finally {
65.            lock.unlock();
66.        }
67.    }
68.        
69.        
70.}

CopyOnWriteArraySet

【1】代码：

1./**
2. * @author : msb-zhaoss
3. */
4.public class Test02 {
5.    //这是main方法，程序的入口
6.    public static void main(String[] args) {
7.        //创建一个集合：
8.        CopyOnWriteArraySet<Integer> set = new CopyOnWriteArraySet<>();
9.        //在这里也体现出Set和List的本质区别，就在于是否重复
10.        //所以add方法直接不可以添加重复数据进去
11.        set.add(1);
12.        set.add(2);
13.        set.add(2);
14.        set.add(7);
15.        System.out.println(set);//[1, 2, 7]
16.        
17.    }
18.}

【2】源码：

1.public class CopyOnWriteArraySet<E>{
2.        //CopyOnWriteArraySet底层基于CopyOnWriteArrayList
3.        private final CopyOnWriteArrayList<E> al;
4.        
5.        public CopyOnWriteArraySet() {
6.        al = new CopyOnWriteArrayList<E>();
7.    }
8.        
9.        //添加方法：
10.        public boolean add(E e) {
11.        return al.addIfAbsent(e);//底层调用的还是CopyOnWriteArrayList的addIfAbsent
12.    }
13.}

总结：

由上面的源码看出，每次调用CopyOnWriteArraySet的add方法时候，其实底层是基于CopyOnWriteArrayList的addIfAbsent，

每次在addIfAbsent方法中每次都要对数组进行遍历，所以CopyOnWriteArraySet的性能低于CopyOnWriteArrayList

数据结构：队列

数据结构分为：

（1）逻辑结构 ：--》思想上的结构--》卧室，厨房，卫生间 ---》线性表（数组，链表），图，树，栈，队列

（2）物理结构 ：--》真实结构--》钢筋混凝土+牛顿力学------》紧密结构（顺序结构），跳转结构（链式结构）?

? 队列：特点：先进先出 （FIFO）（first in first out）

他有两端，一端是让新元素进去，一端是让老元素出去

在需要公平且经济地对各种自然或社会资源做管理或分配的场合，无论是调度银行和医院的服务窗口，还是管理轮耕的田地和轮伐的森林，队列都可大显身手。?

甚至计算机及其网络自身内部的各种计算资源，无论是多进程共享的 CPU 时间，还是多用户共享的打印机，也都需要借助队列结构实现合理和优化的分配。

双端队列：两端都可以进行进队，出队的队列：

（1）前端，后端都可以进出：

（2）进行限制：

（3）特殊情况，双端队列实现栈操作:

栈和队列的物理结构实现 可以用线性表的数组，链表都可以

队列Queue

阻塞队列

BlockingQueue介绍

总结：BlockingQueue继承Queue，Queue继承自Collection

所以Collection最基础的增删改查操作是有的，在这个基础上，多了Queue的特点，在这个基础上又多了阻塞的特点，最终形成了BlockingQueue

什么叫阻塞？

常用的API：

添加：?

put是阻塞的

查询：

take是阻塞的

删除：

BlockingQueue常见子类

ArrayBlockingQueue

源码中的注释的解释说明：

【1】添加元素：

1.package com.msb.test05;
2.
3.import java.util.concurrent.ArrayBlockingQueue;
4.import java.util.concurrent.TimeUnit;
5.
6./**
7. * @author : msb-zhaoss
8. */
9.public class Test01 {
10.    //这是main方法，程序的入口
11.    public static void main(String[] args) throws InterruptedException {
12.        //创建一个队列，队列可以指定容量指定长度3：
13.        ArrayBlockingQueue aq = new ArrayBlockingQueue(3);
14.        //添加元素：
15.        //【1】添加null元素：不可以添加null元素，会报空指针异常：NullPointerException
16.        //aq.add(null);
17.        //aq.offer(null);
18.        //aq.put(null);
19.        //【2】正常添加元素：
20.        aq.add("aaa");
21.        aq.offer("bbb");
22.        aq.put("ccc");
23.        System.out.println(aq);//[aaa, bbb, ccc]
24.
25.        //【3】在队列满的情况下，再添加元素：
26.        //aq.add("ddd");//在队列满的情况下，添加元素 出现异常：Queue full
27.        //System.out.println(aq.offer("ddd"));//没有添加成功，返回false
28.        //设置最大阻塞时间，如果时间到了，队列还是满的，就不再阻塞了
29.        //aq.offer("ddd",2, TimeUnit.SECONDS);
30.        //真正阻塞的方法： put ,如果队列满，就永远阻塞 
31.        aq.put("ddd");
32.        System.out.println(aq);
33.    }
34.}

【2】获取元素：

1.package com.msb.test05;
2.
3.import javax.sound.midi.Soundbank;
4.import java.util.concurrent.ArrayBlockingQueue;
5.import java.util.concurrent.TimeUnit;
6.
7./**
8. * @author : msb-zhaoss
9. */
10.public class Test02 {
11.    //这是main方法，程序的入口
12.    public static void main(String[] args) throws InterruptedException {
13.        //创建一个队列，队列可以指定容量指定长度3：
14.        ArrayBlockingQueue aq = new ArrayBlockingQueue(3);
15.        aq.add("aaa");
16.        aq.add("bbb");
17.        aq.add("ccc");
18.        //得到头元素但是不移除
19.        System.out.println(aq.peek());
20.        System.out.println(aq);
21.        //得到头元素并且移除
22.        System.out.println(aq.poll());
23.        System.out.println(aq);
24.        //得到头元素并且移除
25.        System.out.println(aq.take());
26.        System.out.println(aq);
27.
28.        //清空元素：
29.        aq.clear();
30.        System.out.println(aq);
31.
32.        System.out.println(aq.peek());//null
33.        System.out.println(aq.poll());//null
34.        //设置阻塞事件，如果队列为空，返回null，时间到了以后就不阻塞了
35.        //System.out.println(aq.poll(2, TimeUnit.SECONDS));
36.        //真正阻塞：队列为空，永远阻塞
37.        System.out.println(aq.take());
38.
39.
40.    }
41.}

【3】源码：

1.public class ArrayBlockingQueue<E> {
2.        //底层就是一个数组：
3.        final Object[] items;
4.        //取元素用到的索引，初始结果为0
5.        int takeIndex;
6.        //放元素用到的索引，初始结果为0
7.        int putIndex;
8.        //数组中元素的个数：
9.        int count;
10.        
11.        //一把锁：这个锁肯定很多方法中用到了，所以定义为属性，初始化以后可以随时使用
12.    final ReentrantLock lock;
13.
14.    //锁伴随的一个等待吃：notEmpty
15.    private final Condition notEmpty;
16.
17.    //锁伴随的一个等待吃：notFull
18.    private final Condition notFull;
19.        
20.        //构造器：
21.        public ArrayBlockingQueue(int capacity) {//传入队列指定的容量
22.        this(capacity, false);
23.    }
24.        
25.        public ArrayBlockingQueue(int capacity, boolean fair) {//传入队列指定的容量
26.                //健壮性考虑
27.        if (capacity <= 0)
28.            throw new IllegalArgumentException();
29.                //初始化底层数组
30.        this.items = new Object[capacity];
31.                //初始化锁 和  等待队列
32.        lock = new ReentrantLock(fair);
33.        notEmpty = lock.newCondition();
34.        notFull =  lock.newCondition();
35.    }
36.        
37.        //两个基本方法：一个是入队，一个是出队  ，是其他方法的基础：
38.        //入队：
39.        private void enqueue(E x) {
40.        // assert lock.getHoldCount() == 1;
41.        // assert items[putIndex] == null;
42.        final Object[] items = this.items;//底层数组赋给items
43.                //在对应的下标位置放入元素
44.        items[putIndex] = x;
45.        if (++putIndex == items.length) //++putIndex putIndex 索引 加1 
46.            putIndex = 0;
47.                //每放入一个元素，count加1操作
48.        count++;
49.        notEmpty.signal();
50.    }
51.        
52.        
53.        //出队：
54.        private E dequeue() {
55.        // assert lock.getHoldCount() == 1;
56.        // assert items[takeIndex] != null;
57.        final Object[] items = this.items;//底层数组赋给items
58.        @SuppressWarnings("unchecked")
59.        E x = (E) items[takeIndex];//在对应的位置取出元素
60.        items[takeIndex] = null;//对应位置元素取出后就置为null
61.        if (++takeIndex == items.length)//++takeIndex 加1操作
62.            takeIndex = 0;
63.        count--;//每取出一个元素，count减1操作
64.        if (itrs != null)
65.            itrs.elementDequeued();
66.        notFull.signal();
67.        return x;//将取出的元素作为方法的返回值
68.    }
69.        
70.        
71.        
72.        
73.}

takeIndex和putIndex置为0的原因：

【4】其他的添加或者获取的方法都是依托与这个入队和出队的基础方法

【5】感受一下put和take的阻塞：

上面的while不可以换为if，因为如果notFull中的线程被激活的瞬间，有其他线程放入元素，那么队列就又满了

那么沿着await后面继续执行就不可以，所以一定要反复确定队列是否满的，才能放入元素

LinkedBlockingQueue

一个可选择的有边界的队列：意思就是队列的长度可以指定，也可以不指定

【1】添加元素：

1.package com.msb.test05;
2.
3.import java.util.concurrent.ArrayBlockingQueue;
4.import java.util.concurrent.LinkedBlockingQueue;
5.import java.util.concurrent.TimeUnit;
6.
7./**
8. * @author : msb-zhaoss
9. */
10.public class Test01 {
11.    //这是main方法，程序的入口
12.    public static void main(String[] args) throws InterruptedException {
13.        //创建一个队列，队列可以指定容量指定长度3：
14.        LinkedBlockingQueue aq = new LinkedBlockingQueue(3);
15.        //添加元素：
16.        //【1】添加null元素：不可以添加null元素，会报空指针异常：NullPointerException
17.        //aq.add(null);
18.        //aq.offer(null);
19.        aq.put(null);
20.        //【2】正常添加元素：
21.        aq.add("aaa");
22.        aq.offer("bbb");
23.        aq.put("ccc");
24.        System.out.println(aq);//[aaa, bbb, ccc]
25.
26.        //【3】在队列满的情况下，再添加元素：
27.        //aq.add("ddd");//在队列满的情况下，添加元素 出现异常：Queue full
28.        //System.out.println(aq.offer("ddd"));//没有添加成功，返回false
29.        //设置最大阻塞时间，如果时间到了，队列还是满的，就不再阻塞了
30.        //aq.offer("ddd",2, TimeUnit.SECONDS);
31.        //真正阻塞的方法： put ,如果队列满，就永远阻塞
32.        aq.put("ddd");
33.        System.out.println(aq);
34.    }
35.}
36.

【2】取出元素：

1.package com.msb.test05;
2.
3.import javax.sound.midi.Soundbank;
4.import java.util.concurrent.ArrayBlockingQueue;
5.import java.util.concurrent.LinkedBlockingQueue;
6.import java.util.concurrent.TimeUnit;
7.
8./**
9. * @author : msb-zhaoss
10. */
11.public class Test02 {
12.    //这是main方法，程序的入口
13.    public static void main(String[] args) throws InterruptedException {
14.        //创建一个队列，队列可以指定容量指定长度3：
15.        LinkedBlockingQueue aq = new LinkedBlockingQueue();
16.        aq.add("aaa");
17.        aq.add("bbb");
18.        aq.add("ccc");
19.        //得到头元素但是不移除
20.        System.out.println(aq.peek());
21.        System.out.println(aq);
22.        //得到头元素并且移除
23.        System.out.println(aq.poll());
24.        System.out.println(aq);
25.        //得到头元素并且移除
26.        System.out.println(aq.take());
27.        System.out.println(aq);
28.
29.        //清空元素：
30.        aq.clear();
31.        System.out.println(aq);
32.
33.        System.out.println(aq.peek());//null
34.        System.out.println(aq.poll());//null
35.        //设置阻塞事件，如果队列为空，返回null，时间到了以后就不阻塞了
36.        //System.out.println(aq.poll(2, TimeUnit.SECONDS));
37.        //真正阻塞：队列为空，永远阻塞
38.        System.out.println(aq.take());
39.
40.
41.    }
42.}
43.

【3】特点：

ArrayBlockingQueue ： 不支持读写同时操作，底层基于数组的。

LinkedBlockingQueue：支持读写同时操作，并发情况下，效率高。底层基于链表。

【4】源码：

入队操作：

出队操作：

1.public class LinkedBlockingQueue<E>{
2.        //内部类Node就是链表的节点的对象对应的类：
3.        static class Node<E> {
4.        E item;//封装你要装的那个元素
5.        
6.        Node<E> next;//下一个Node节点的地址
7.
8.        Node(E x) { item = x; }//构造器
9.    }
10.        //链表的长度
11.        private final int capacity;
12.        //计数器：
13.        private final AtomicInteger count = new AtomicInteger();
14.        //链表的头结点
15.        transient Node<E> head;
16.        //链表的尾结点
17.        private transient Node<E> last;
18.        //取元素用的锁
19.        private final ReentrantLock takeLock = new ReentrantLock();
20.        //等待池
21.    private final Condition notEmpty = takeLock.newCondition();
22.    //放元素用的锁
23.    private final ReentrantLock putLock = new ReentrantLock();
24.    //等待池
25.    private final Condition notFull = putLock.newCondition();
26.        
27.        public LinkedBlockingQueue() {
28.        this(Integer.MAX_VALUE);//调用类本类的空构造器，传入正21亿
29.    }
30.        
31.        public LinkedBlockingQueue(int capacity) {
32.                //健壮性考虑
33.        if (capacity <= 0) throw new IllegalArgumentException();
34.                //给队列指定长度  
35.        this.capacity = capacity;
36.                //last，head指向一个新的节点，新的节点中 元素为null 
37.        last = head = new Node<E>(null);
38.    }
39.        
40.        
41.        //入队：
42.        private void enqueue(Node<E> node) {
43.        last = last.next = node;
44.    }
45.        
46.        //出队：
47.        private E dequeue() {
48.        Node<E> h = head;//h指向了head
49.        Node<E> first = h.next;//first 指向head的next
50.        h.next = h; // help GC   h.next指向自己，更容易被GC发现 被GC
51.        head = first;//head的指向指为first
52.        E x = first.item;//取出链中第一个元素，给了x
53.        first.item = null;
54.        return x;//把x作为方法的返回值
55.    }
56.}

【5】put的阻塞：

阻塞的前提是 ?队列是固定长度的?

SynchronousQueue

这个特殊的队列设计的意义：

测试1：先添加元素：

1.public class Test01 {
2.    //这是main方法，程序的入口
3.    public static void main(String[] args) {
4.        SynchronousQueue sq = new SynchronousQueue();
5.        sq.add("aaa");
6.    }
7.}

直接报错：说队列满了，因为队列没有容量，理解为满也是正常的

测试2：put方法 ?阻塞：队列是空的，可以理解为队列满了，满的话放入元素 put 一定会阻塞：

1.public class Test01 {
2.    //这是main方法，程序的入口
3.    public static void main(String[] args) throws InterruptedException {
4.        SynchronousQueue sq = new SynchronousQueue();
5.        sq.put("aaa");
6.    }
7.}

测试3：先取 ?再放：

1.package com.msb.test06;
2.
3.import java.util.concurrent.SynchronousQueue;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class Test02 {
9.    //这是main方法，程序的入口
10.    public static void main(String[] args) {
11.        SynchronousQueue sq = new SynchronousQueue();
12.
13.        //创建一个线程，取数据：
14.        new Thread(new Runnable() {
15.            @Override
16.            public void run() {
17.                while(true){
18.                    try {
19.                        System.out.println(sq.take());
20.                    } catch (InterruptedException e) {
21.                        e.printStackTrace();
22.                    }
23.                }
24.            }
25.        }).start();
26.
27.        //搞一个线程，往里面放数据：
28.        new Thread(new Runnable() {
29.            @Override
30.            public void run() {
31.                try {
32.                    sq.put("aaa");
33.                    sq.put("bbb");
34.                    sq.put("ccc");
35.                    sq.put("ddd");
36.                } catch (InterruptedException e) {
37.                    e.printStackTrace();
38.                }
39.
40.            }
41.        }).start();
42.    }
43.}

结果：

测试4：poll方法：?

1.package com.msb.test06;
2.
3.import java.util.concurrent.SynchronousQueue;
4.import java.util.concurrent.TimeUnit;
5.
6./**
7. * @author : msb-zhaoss
8. */
9.public class Test02 {
10.    //这是main方法，程序的入口
11.    public static void main(String[] args) {
12.        SynchronousQueue sq = new SynchronousQueue();
13.
14.        //创建一个线程，取数据：
15.        new Thread(new Runnable() {
16.            @Override
17.            public void run() {
18.                while(true){
19.                    try {
20.                        //设置一个阻塞事件：超出事件就不阻塞了
21.                        Object result = sq.poll(5, TimeUnit.SECONDS);
22.                        System.out.println(result);
23.                        if(result == null){
24.                            break;
25.                        }
26.                    } catch (InterruptedException e) {
27.                        e.printStackTrace();
28.                    }
29.                }
30.            }
31.        }).start();
32.
33.        //搞一个线程，往里面放数据：
34.        new Thread(new Runnable() {
35.            @Override
36.            public void run() {
37.                try {
38.                    sq.put("aaa");
39.                    sq.put("bbb");
40.                    sq.put("ccc");
41.                    sq.put("ddd");
42.                } catch (InterruptedException e) {
43.                    e.printStackTrace();
44.                }
45.
46.            }
47.        }).start();
48.    }
49.}

注意：取出元素 不能用peek，因为peek不会将元素从队列中拿走，只是查看的效果；

PriorityBlockingQueue

带有优先级的阻塞队列。

优先级队列，意味着队列有先后顺序的，数据有不同的权重。?

无界的队列，没有长度限制，但是在你不指定长度的时候，默认初始长度为11，也可以手动指定，

当然随着数据不断的加入，底层（底层是数组Object[]）会自动扩容，直到内存全部消耗殆尽了，导致 OutOfMemoryError内存溢出 程序才会结束。

不可以放入null元素的，不允许放入不可比较的对象（导致抛出ClassCastException），对象必须实现内部比较器或者外部比较器。?

测试1：添加null数据：

1.public class Test {
2.    //这是main方法，程序的入口
3.    public static void main(String[] args) {
4.        PriorityBlockingQueue pq = new PriorityBlockingQueue();
5.        pq.put(null);
6.    }
7.}

测试2：添加四个数据：

1.package com.msb.test07;
2.
3./**
4. * @author : msb-zhaoss
5. */
6.public class Student implements Comparable<Student> {
7.    String name;
8.    int age;
9.
10.    public Student() {
11.    }
12.
13.    public Student(String name, int age) {
14.        this.name = name;
15.        this.age = age;
16.    }
17.
18.    @Override
19.    public String toString() {
20.        return "Student{" +
21.                "name='" + name + '\'' +
22.                ", age=" + age +
23.                '}';
24.    }
25.
26.    @Override
27.    public int compareTo(Student o) {
28.        return this.age - o.age;
29.    }
30.}

1.package com.msb.test07;
2.
3.import java.util.concurrent.PriorityBlockingQueue;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class Test02 {
9.    //这是main方法，程序的入口
10.    public static void main(String[] args) {
11.        PriorityBlockingQueue<Student> pq = new PriorityBlockingQueue<>();
12.        pq.put(new Student("nana",18));
13.        pq.put(new Student("lulu",11));
14.        pq.put(new Student("feifei",6));
15.        pq.put(new Student("mingming",21));
16.        System.out.println(pq);
17.    }
18.}

结果：

发现结果并没有按照优先级顺序排列

测试3：取出数据：

1.package com.msb.test07;
2.
3.import java.util.concurrent.PriorityBlockingQueue;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class Test02 {
9.    //这是main方法，程序的入口
10.    public static void main(String[] args) throws InterruptedException {
11.        PriorityBlockingQueue<Student> pq = new PriorityBlockingQueue<>();
12.        pq.put(new Student("nana",18));
13.        pq.put(new Student("lulu",11));
14.        pq.put(new Student("feifei",6));
15.        pq.put(new Student("mingming",21));
16.        System.out.println("------------------------------------------");
17.        System.out.println(pq.take());
18.        System.out.println(pq.take());
19.        System.out.println(pq.take());
20.        System.out.println(pq.take());
21.    }
22.}
23.

从结果证明，这个优先级队列，并不是在put数据的时候计算谁在前谁在后

而是取数据的时候，才真正判断谁在前 谁在后

优先级 --》取数据的优先级

DelayQueue

一、DelayQueue是什么

DelayQueue是一个无界的BlockingQueue，用于放置实现了Delayed接口的对象，其中的对象只能在其到期时才能从队列中取走。

当生产者线程调用put之类的方法加入元素时，会触发Delayed接口中的compareTo方法进行排序，也就是说队列中元素的顺序是按到期时间排序的，而非它们进入队列的顺序。排在队列头部的元素是最早到期的，越往后到期时间赿晚。

消费者线程查看队列头部的元素，注意是查看不是取出。然后调用元素的getDelay方法，如果此方法返回的值小０或者等于０，则消费者线程会从队列中取出此元素，并进行处理。如果getDelay方法返回的值大于0，则消费者线程wait返回的时间值后，再从队列头部取出元素，此时元素应该已经到期。

注意：不能将null元素放置到这种队列中。

二、DelayQueue能做什么

1. 淘宝订单业务:下单之后如果三十分钟之内没有付款就自动取消订单。?
2. 饿了吗订餐通知:下单成功后60s之后给用户发送短信通知。

3. 关闭空闲连接。服务器中，有很多客户端的连接，空闲一段时间之后需要关闭之。

4. 缓存。缓存中的对象，超过了空闲时间，需要从缓存中移出。

5. 任务超时处理。在网络协议滑动窗口请求应答式交互时，处理超时未响应的请求等。??

案例：

1.package com.msb.test08;
2.
3.import java.util.concurrent.Delayed;
4.import java.util.concurrent.TimeUnit;
5.
6./**
7. * @author : msb-zhaoss
8. */
9.public class User implements Delayed {
10.    private int id;//用户id
11.    private String name;//用户名字
12.    private long endTime;//结束时间
13.
14.    public int getId() {
15.        return id;
16.    }
17.
18.    public void setId(int id) {
19.        this.id = id;
20.    }
21.
22.    public String getName() {
23.        return name;
24.    }
25.
26.    public void setName(String name) {
27.        this.name = name;
28.    }
29.
30.    public long getEndTime() {
31.        return endTime;
32.    }
33.
34.    public void setEndTime(long endTime) {
35.        this.endTime = endTime;
36.    }
37.
38.    public User(int id, String name, long endTime) {
39.        this.id = id;
40.        this.name = name;
41.        this.endTime = endTime;
42.    }
43.
44.    //只包装用户名字就可以
45.    @Override
46.    public String toString() {
47.        return "User{" +
48.                "name='" + name + '\'' +
49.                '}';
50.    }
51.
52.    @Override
53.    public long getDelay(TimeUnit unit) {
54.        //计算剩余时间 剩余时间小于0 <=0  证明已经到期
55.        return this.getEndTime() - System.currentTimeMillis();
56.    }
57.
58.    @Override
59.    public int compareTo(Delayed o) {
60.        //队列中数据 到期时间的比较
61.        User other = (User)o;
62.        return ((Long)(this.getEndTime())).compareTo((Long)(other.getEndTime()));
63.    }
64.}

compareTo：看谁先被移除?

getDelay ：看剩余时间?

1.package com.msb.test08;
2.
3.import java.util.concurrent.DelayQueue;
4.
5./**
6. * @author : msb-zhaoss
7. */
8.public class TestDelayQueue {
9.    //创建一个队列：
10.    DelayQueue<User> dq = new DelayQueue<>();
11.
12.    //登录游戏：
13.    public void login(User user){
14.        dq.add(user);
15.        System.out.println("用户：[" + user.getId() +"],[" + user.getName() + "]已经登录，预计下机时间为：" + user.getEndTime() );
16.    }
17.
18.    //时间到，退出游戏，队列中移除：
19.    public void logout(){
20.        //打印队列中剩余的人：
21.        System.out.println(dq);
22.        try {
23.            User user = dq.take();
24.            System.out.println("用户：[" + user.getId() +"],[" + user.getName() + "]上机时间到，自动退出游戏");
25.        } catch (InterruptedException e) {
26.            e.printStackTrace();
27.        }
28.    }
29.
30.    //获取在线人数：
31.    public int onlineSize(){
32.        return dq.size();
33.    }
34.
35.    //这是main方法，程序的入口
36.    public static void main(String[] args) {
37.        //创建测试类对象：
38.        TestDelayQueue test = new TestDelayQueue();
39.
40.        //添加登录的用户：
41.        test.login(new User(1,"张三",System.currentTimeMillis()+5000));
42.        test.login(new User(2,"李四",System.currentTimeMillis()+2000));
43.        test.login(new User(3,"王五",System.currentTimeMillis()+10000));
44.        //一直监控
45.        while(true){
46.            //到期的话，就自动下线：
47.            test.logout();
48.            //队列中元素都被移除了的话，那么停止监控，停止程序即可
49.            if(test.onlineSize() == 0){
50.                break;
51.            }
52.        }
53.    }
54.}

双端队列Deque

1.package com.msb.test08;
2.
3.import java.util.Collection;
4.import java.util.Deque;
5.import java.util.Iterator;
6.import java.util.LinkedList;
7.
8./**
9. * @author : msb-zhaoss
10. */
11.public class Test03 {
12.    //这是main方法，程序的入口
13.    public static void main(String[] args) {
14.        /*
15.        双端队列：
16.        Deque<E> extends Queue
17.        Queue一端放 一端取的基本方法  Deque是具备的
18.        在此基础上 又扩展了 一些 头尾操作（添加，删除，获取）的方法
19.         */
20.        Deque<String> d = new LinkedList<>() ;
21.        d.offer("A");
22.        d.offer("B");
23.        d.offer("C");
24.        System.out.println(d);//[A, B, C]
25.
26.        d.offerFirst("D");
27.        d.offerLast("E");
28.        System.out.println(d);//[D, A, B, C, E]
29.
30.        System.out.println(d.poll());
31.        System.out.println(d);//[A, B, C, E]
32.
33.        System.out.println(d.pollFirst());
34.        System.out.println(d.pollLast());
35.        System.out.println(d);
36.    }
37.}