1.队列介绍

今天要来讲一下java里的队列，队列，顾名思义，排队的列，既然按排队形来做的话，生活中的银行排队啊，上车排队啊，都是先到先办理或者先上车，队列存取数据列也一样，这就是先进先出，使用队列的规则是：使用队素时，数据元素只能从表的一端进入队列，另一端出队列。

称进入队列的一端为“队尾”，出队列的一端为“队头”。数据元素全部从队尾陆续进队列，由对头陆续出队列。

特点：先进先出

效率：插入数据项和移除数据项的时间复杂度都是O(1)，因为插入是一个一个而且只能在一端插入，取出也只能一个一个从一头取，这样不用循环一次取一次存就可以得到复杂度就是O(1)。

2.java的阻塞队列

2.1 ArrayBlockingQueue

基于数组实现的一个有界的阻塞队列，在创建ArrayBlockingQueue对象时必须指定容器大小。并且可以指定公平性和非公平性，默认情况下为非公平的，即不保证等待时间最长的队列最优先能够访问队列。

为什么是有界的?

看下图不指定容量会报错，那么指定了容量就是有界的。

为什么可以支持公平锁和非公平锁？

我随便拿个示例调用一个队列里的一个方法点进去

用的是ReentrantLock，ReentrantLock本身的功能是有支持公平锁和非公平锁的

下面代码示例下ArrayBlockingQueue怎么使用？

因为ArrayBlockingQueue存储和移除数据有三种情况，异常，阻塞，非阻塞

异常示例

先演示存储满了再进行存储异常的情况

public class BlockingQueueDemo {
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);
    //生产者
    class Producer extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < queueSize + 1; i++) {
                queue.add(i);
                System.out.println("向队列中添加元素，队列剩余空间：" + (queueSize - queue.size()));

            }
        }
    }
    
    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        Producer producer = blockingQueueDemo.new Producer();
        producer.start();
    }
}

​

我指定了存储10个数字，然后我要存储11个，那么就会报错，可以看出add()方法是存储满了就抛异常的方式

再来一个取元素，元素没有了，抛异常的代码情况

public class BlockingQueueDemo {
    
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);


    class costormer extends Thread {
        @Override
        public void run() {
            queue.remove();
            System.out.println("向队列中取出一个元素，队列剩余：" + queue.size() + "个元素");
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        costormer costormer = blockingQueueDemo.new costormer();
        costormer.start();
    }
}

队列里一个数据都没有，获取元素抛出没有元素异常,由此可见remove()是获取数据抛异常的方式

以上是异常的情况。

阻塞示例

public class BlockingQueueDemo {

    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    //生产者
    class Producer extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < queueSize + 1; i++) {

                try {
                    queue.put(i);
                    System.out.println("向队列中添加元素，队列剩余空间：" + (queueSize - queue.size()));
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        Producer producer = blockingQueueDemo.new Producer();
        producer.start();
    }
}

可以看到存储满了就会一直阻塞等待，直到队列元素被取出才会停止阻塞，由此可见存储数据的put()是有阻塞功能的。

取元素阻塞示例

public class BlockingQueueDemo {

    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    class costormer extends Thread {
        @Override
        public void run() {
            try {
                queue.take();
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            System.out.println("向队列中取出一个元素，队列剩余：" + queue.size() + "个元素");
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        costormer costormer = blockingQueueDemo.new costormer();
        costormer.start();
    }

当前队列一个元素没有，取数据的时候就被阻塞一直等待了，程序一直没有退出操作，由此可见take()是取出阻塞操作的

非阻塞示例

public class BlockingQueueDemo {
    
    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    //生产者
    class Producer extends Thread {
        @Override
        public void run() {
            for (int i = 0; i < queueSize + 1; i++) {
                Boolean issuccess = queue.offer(i);
                if (issuccess) {
                    System.out.println("向队列中添加元素，队列剩余空间：" + (queueSize - queue.size()));
                } else {
                    System.out.println("队列已满！");
                }
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        Producer producer = blockingQueueDemo.new Producer();
        producer.start();
    }
}

区别相信大家也看出来了，满了的情况不会抛出异常，也不会阻塞，这种就是成功存储就返回true，队列满了不能存储就返回false了。

取数据非阻塞示例

public class BlockingQueueDemo {

    private int queueSize = 10;
    private ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(queueSize);

    class costormer extends Thread {
        @Override
        public void run() {
            Object obj = queue.poll();
            if (obj == null) {
                System.out.println("队列无数据！");
            } else {
                System.out.println("向队列中取出一个元素，队列剩余：" + queue.size() + "个元素");
            }
        }
    }

    public static void main(String[] args) {
        BlockingQueueDemo blockingQueueDemo = new BlockingQueueDemo();
        costormer costormer = blockingQueueDemo.new costormer();
        costormer.start();
    }
}

由此可见poll()方法是队列没有数据获取时不阻塞，不抛异常返回null的一种方式。

总结一下：

ArrayBlockingQueue异常：

 1.1 插入->队列满时再进行添加数据会抛出IllegalStateException异常。

      代表方法：add()

 1.2 移除->队列null时会抛出NoSuchElementException异常。

       代表方法：remove(),element()

ArrayBlockingQueue阻塞：

  1.1 插入->队列满再添加数据会堵塞

        代表方法：put()

  1.2 移除并获取->队列null时会堵塞

        代表方法：take()

ArrayBlockingQueue非阻塞：

  1.1 插入->队列满时再进行添加，就返回false

       代表方法：offer()

  1.2 移除并获取->队列为null,返回null

        代表方法：poll()，peek()

2.2 LinkedBlockingQueue

基于链表实现的一个可选有界阻塞队列，在创建LinkedBlockingQueue对象时如果不指定容量大小，则默认大小为Integer.MAX_VALUE。

数据结构从源码中看是单链表结构

阻塞、不阻塞、异常都是和ArrayBlockingQueue是一致的，这里就不在演示了

2.3 PriorityBlockingQueue

PriorityBlockingQueue的实现使用了基于数组的平衡二叉堆（小的在上，大的在下方，即最小堆）优先级阻塞队列，可选有界队列，它会按照元素的优先级对元素进行排序，按照优先级顺序出队，每次出队的元素都是优先级最高的元素。

在阻塞和不阻塞和异常都是跟上述方法一样，唯一不同的是优先级排序的实现方式上。大家可以自行学习，这里就不再介绍了

2.4 DelayQueue

DelayQueue比较特殊，它是一个BlockingQueue+PriorityQueue+Delayed的实现方式，可以这样说DelayQueue是使用了优先队列实现的BlockingQueue

一种延时阻塞队列，DelayQueue中的元素只有当其指定的延迟时间到了，才能够从队列中获取该元素。DelayQueue是一个无界队列，因此往队列插入数据的操作（生产者）永远不会被阻塞，而只有获取数据的操作（消费者）才会被阻塞。

虽然DelayQueue中也有put这样的堵塞方法，但是put里调用的是没有进行阻塞offer的方法。

2.5 SynchronousQueue

SynchronousQueue的特点是只能容纳一个元素，同时SynchronousQueue使用了两种模式来管理元素，一种是使用先进先出的队列，一种是使用后进先出的栈，选用哪种模式可以通过构造函数来指定。(不常用)

3.java非阻塞队列

非阻塞队列实现方式是使用循环CAS,非阻塞队列和阻塞队列的区别就只是方法不同，阻塞id会有take等一些存储或获取阻塞的方法，非阻塞则没有阻塞的方法。

3.1 ArrayDeque

数组结构队列，底层数组实现，且双向操作，既可以向头添加数据也可以向尾添加数据，既可以头部取数据也可以尾部取数据。使用方式都和阻塞队列都一样

3.2  PriorityQueue

优先级非阻塞队列，方法都是类似的不多说了。

3.3 ConcurrentLinkedQueue

是基于链表的非阻塞队列，底层是通过链表来实现的，非阻塞方法和ArrayDeque类似，只是它只能向队列尾部添加数据，所以没有Last和First方法。

阻塞队列与非阻塞队列区别

1. 阻塞队列可以阻塞，非阻塞队列不可以阻塞
2. 阻塞队列当队列为空的时候从队列中获取元素的操作将会被阻塞，非阻塞队列为空的话，再从队列取出数据就直接返回null
3. 阻塞队列当队列满了的话再插入数据就会被阻塞，直到队列不满
4. 支持阻塞的插入方法：意思是当队列满时，队列会阻塞插入元素的线程，直到队列不满。
   支持阻塞的移除方法：意思是在队列为空时，获取元素的线程会等待队列变为非空。
5. 非阻塞队列想要阻塞只能手动使用wait()和Notify()

其实大家自己代码测试的时候就可以发现，非阻塞的队列是没有阻塞的那些方法的

4.使用方法