03.并发编程之wait_notify模拟Queue

1、BlockingQueue

顾名思义，首先它是一个队列，并且支持阻塞的机制，阻塞地放入和得到数据。
实现LinkedBlockingQueue两个简单的方法put与take
put(an Object)：把Object加到BlockingQueue里，如果BlockingQueue没有空间，则调用此方法的线程被阻断，直接有空间再继续。
take(an Object)：取走BlockingQueue里排在首位的对象，BlockingQueue为空，阻断进入等待状态直到BlockingQueue有新的数据被加入。

2、Java中的ArrayList的初始容量和容量分配

List接口的大小可变数组的实现。实现了所有可选列表操作，并允许包括 null在内的所有元素。
ArrayList继承于List接口，除继承过来的方法外，还提供一些方法来操作内部用来存储列表的数组的大小。
每个ArrayList实例都有一个容量。该容量是指用来存储列表元素的数组的大小。它总是至少等于列表的大小。随着向ArrayList中不断添加元素，其容量也自动增长。
并未指定增长策略的细节，因为这不只是添加元素会带来分摊固定时间开销那样简单。
ArrayList是经常会被用到的，一般情况下，使用的时候会像这样进行声明：

List arrayList = new ArrayList();

如果像上面这样使用默认的构造方法，初始容量被设置为10。当ArrayList中的元素超过10个以后，会重新分配内存空间，使数组的大小增长到16。
可以通过调试看到动态增长的数量变化：10->16->25->38->58->88->...
也可以使用下面的方式进行声明：

List arrayList = new ArrayList(4);

将ArrayList的默认容量设置为4。当ArrayList中的元素超过4个以后，会重新分配内存空间，使数组的大小增长到7。
可以通过调试看到动态增长的数量变化：4->7->11->17->26->...
那么容量变化的规则是什么呢？请看下面的公式：
((旧容量 * 3) / 2) + 1
注：这点与C#语言是不同的，C#当中的算法很简单，是翻倍。
一旦容量发生变化，就要带来额外的内存开销，和时间上的开销。
所以，在已经知道容量大小的情况下，推荐使用下面方式进行声明：

List arrayList = new ArrayList(CAPACITY_SIZE);

即指定默认容量大小的方式。

package demo2;

import java.util.LinkedList;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.atomic.AtomicInteger;

public class MyQueue {
    // 1.需要一个盛装元素的集合
    private LinkedList<Object>  list    = new LinkedList<Object>();

    // 2.有满的时候，是有界队列，需要计数器，统计加入list的个数
    private AtomicInteger       count   = new AtomicInteger(0);

    // 3.需要指定上限与下限
    private final int           minSize = 0;
    private final int           maxSize;

    // 4.构造方法
    public MyQueue(int size) {
        this.maxSize = size;
    }

    // 5.初始化一个对象，用于加锁
    private final Object lock = new Object();

    // put：把Object加到BlockingQueue里，如果BlockingQueue没有空间，则调用此方法的线程被阻断，直接有空间再继续。
    public void put(Object obj) {
        synchronized (lock) {
            while (count.get() == this.maxSize) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            // 1.加入元素
            list.add(obj);
            // 2.计数器累加
            count.incrementAndGet();
            // 3.唤醒另外一个线程
            lock.notify();

            System.out.println("新加入的元素为：" + obj);
        }
    }

    // take：取走BlockingQueue里排在首位的对象，若BlockingQueue为空，阻断进入等待状态直到BlockingQueue有新的数据被加入。
    public Object take() {
        Object ret = null;
        synchronized (lock) {
            while (count.get() == this.minSize) {
                try {
                    lock.wait();
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
            // 1.移除元素操作
            ret = list.removeFirst();
            // 2.计数器递减
            count.decrementAndGet();
            // 3.唤醒另外一个线程
            lock.notify();
        }
        return ret;
    }

    public int getSize() {
        return this.count.get();
    }

    public static void main(String[] args) {
        MyQueue mq = new MyQueue(5);
        mq.put("a");
        mq.put("b");
        mq.put("c");
        mq.put("d");
        mq.put("e");

        System.out.println("当前容器的长度为：" + mq.getSize());
        Thread t1 = new Thread(new Runnable() {

            @Override
            public void run() {
                mq.put("f");
                mq.put("g");

            }
        }, "t1");
        t1.start();

        Thread t2 = new Thread(new Runnable() {

            @Override
            public void run() {
                Object o1 = mq.take();
                System.out.println("移除的元素为：" + o1);
                Object o2 = mq.take();
                System.out.println("移除的元素为：" + o2);

            }
        }, "t2");
        try {
            TimeUnit.SECONDS.sleep(2);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        t2.start();
    }
}