队列

1、简介

队列是一种特殊的线性表，它只允许在表的前端进行删除操作（队首），而在表的后端进行插入操作（队尾）（FIFO—first in first out）。

2、队列（Queue）用法

LinkedList类实现了Queue接口，因此我们可以把LinkedList当成Queue来用。
以下实例演示了队列（Queue）的用法：

import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    public static void main(String[] args) {
        //add()和remove()方法在失败的时候会抛出异常(不推荐)
        Queue<String> queue = new LinkedList<String>();
        //添加元素
        queue.offer("a");
        queue.offer("b");
        queue.offer("c");
        queue.offer("d");
        queue.offer("e");
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("poll="+queue.poll()); //返回第一个元素，并在队列中删除
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("element="+queue.element()); //返回第一个元素 
        for(String q : queue){
            System.out.println(q);
        }
        System.out.println("===");
        System.out.println("peek="+queue.peek()); //返回第一个元素 
        for(String q : queue){
            System.out.println(q);
        }
    }
}

a
b
c
d
e
===
poll=a
b
c
d
e
===
element=b
b
c
d
e
===
peek=b
b
c
d
e

offer，add 区别：
一些队列有大小限制，因此如果想在一个满的队列中加入一个新项，多出的项就会被拒绝。
这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常，而只是得到由 offer() 返回的 false。
poll，remove 区别：
remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似， 但是新的 poll() 方法在用空集合调用时不是抛出异常，只是返回 null。因此新的方法更适合容易出现异常条件的情况。
peek，element区别：
element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似，在队列为空时， element() 抛出一个异常，而 peek() 返回 null。

3、分类

3.1、ArrayBlockingQueue基于数组实现的阻塞队列

ArrayBlockingQueue 是一个有界队列，有界也就意味着，它不能够存储无限多数量的对象。所以在创建 ArrayBlockingQueue 时，必须要给它指定一个队列的大小。
我们先来熟悉一下 ArrayBlockingQueue 中的几个重要的方法。

• add(E e)：把 e 加到 BlockingQueue 里，即如果 BlockingQueue 可以容纳，则返回 true，否则报异常
• offer(E e)：表示如果可能的话，将 e 加到 BlockingQueue 里，即如果 BlockingQueue 可以容纳，则返回 true，否则返回 false，不会报异常
• put(E e)：把 e 加到 BlockingQueue 里，如果 BlockQueue 没有空间，则调用此方法的线程被阻断直到 BlockingQueue 里面有空间再继续
• poll(time)：取走 BlockingQueue 里排在首位的对象，若不能立即取出，则可以等 time 参数规定的时间,取不到时返回 null
• take()：取走 BlockingQueue 里排在首位的对象，若 BlockingQueue 为空，阻断进入等待状态直到 Blocking 有新的对象被加入为止
• remainingCapacity()：剩余可用的大小。等于初始容量减去当前的 size
• drainTo(Collection<? super E> c, int maxElements): 次性从BlockingQueue获取所有可用的数据对象（还可以指定获取数据的个数），通过该方法，可以提升获取数据效率；不需要多次分批加锁或释放锁

我们再来看一下 ArrayBlockingQueue 使用场景。

• 先进先出队列（队列头的是最先进队的元素；队列尾的是最后进队的元素）
• 有界队列（即初始化时指定的容量，就是队列最大的容量，不会出现扩容，容量满，则阻塞进队操作；容量空，则阻塞出队操作）
• 队列不支持空元素

        //必须指定队列长度
        ArrayBlockingQueue<String> abq=new ArrayBlockingQueue<String>(2);
        abq.add("a");
        //add :添加元素,如果BlockingQueue可以容纳,则返回true,否则抛异常,支持添加集合
        System.out.println(abq.offer("b"));//容量如果不够,返回false
        //offer: 如果可能的话,添加元素,即如果BlockingQueue可以容纳,则返回true,否则返回false,支持设置超时时间
        //设置超时,如果超过时间就不添加,返回false,
        // System.out.println(abq.offer("d", 2, TimeUnit.SECONDS));// 添加的元素,时长,单位
        //put 添加元素,如果BlockQueue没有空间,则调用此方法的线程被阻断直到BlockingQueue里面有空间再继续.
        abq.put("d");//会一直等待
        //poll 取走头部元素,若不能立即取出,则可以等time参数规定的时间,取不到时返回null,支持设置超时时间
        abq.poll();
        abq.poll(2,TimeUnit.SECONDS);//两秒取不到返回null
        //take()  取走头部元素,若BlockingQueue为空,阻断进入等待状态直到Blocking有新的对象被加入为止
        abq.take();
        //取出头部元素,但不删除
        abq.element();
        //drainTo()
        //一次性从BlockingQueue获取所有可用的数据对象（还可以指定获取数据的个数），通过该方法，可以提升获取数据效率；不需要多次分批加锁或释放锁。
        List list=new ArrayList();
        abq.drainTo(list,2);//将队列中两个元素取到list中，取走后队列中就没有取走的元素
        System.out.println(list); //[a,b]
        System.out.println(abq);  //[]

3.2、LinkedBlockingQueue基于链表实现的阻塞队列

它的容量是没有上限的（在不指定时容量为Integer.MAX_VALUE，不要然的话在put时怎么会受阻呢），但是也可以选择指定其最大容量，此队列按 FIFO（先进先出）排序元素。

3.3、PriorityBlockingQueue基于堆实现的带有优先级的阻塞队列

PriorityBlockingQueue是一个带优先级的队列，而不是先进先出队列。元素按优先级顺序被移除，这个队列在逻辑上是无界的，但是如果队列为空，那么取元素的操作take就会阻塞，所以它的检索操作take是受阻的。

实现原理：PriorityBlockingQueue通过使用堆这种数据结构实现将队列中的元素按照某种排序规则进行排序，从而改变先进先出的队列顺序，提供开发者改变队列中元素的顺序的能力。队列中的元素必须是可比较的，即实现Comparable接口，或者在构建函数时提供可对队列元素进行比较的Comparator对象。不可以放null，会报空指针异常，也不可放置无法比较的元素；add方法添加元素时，是自下而上的调整堆，取出元素时，是自上而下的调整堆顺序；

        PriorityBlockingQueue<Task> q = new PriorityBlockingQueue<Task>();
        Task t1 = new Task();
        t1.setId(1);
        t1.setName("id为1");
        Task t2 = new Task();
        t2.setId(2);
        t2.setName("id为2");
        Task t3 = new Task();
        t3.setId(3);
        t3.setName("id为3");
        Task t4 = new Task();
        t4.setId(4);
        t4.setName("id为4");
        q.add(t3);    //3
        q.add(t2);  //2
        q.add(t4);  //4
        q.add(t1);  //1
        System.out.println("容器：" + q);
        System.out.println(q.take().getId());
        System.out.println("容器：" + q);
        System.out.println(q.take().getId());
        System.out.println("容器：" + q);

class Task implements Comparable<Task> {
    private int id;
    private String name;

    @Override
    public int compareTo(Task task) {
        return this.id > task.id ? 1 : (this.id < task.id ? -1 : 0);
    }

   // get set方法略...
}

运行结果

3.4、SynchronousQueue同步阻塞队列

SynchronousQueue，实际上它不是一个真正的队列，因为它不会为队列中元素维护存储空间。与其他队列不同的是，它维护一组线程，这些线程在等待着把元素加入或移出队列。
因为SynchronousQueue没有存储功能，因此put和take会一直阻塞，直到有另一个线程已经准备好参与到交付过程中。仅当有足够多的消费者，并且总是有一个消费者准备好获取交付的工作时，才适合使用同步队列。

public class test {
     static class Producer implements Runnable {
        SynchronousQueue queue;

        Producer(SynchronousQueue queue){
            this.queue = queue;
        }

        @Override
        public void run() {
            try {
                // 加入队列
                queue.put(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    static class Consumer implements Runnable {
        SynchronousQueue queue;

        Consumer(SynchronousQueue queue){
            this.queue = queue;
        }

        @Override
        public void run() {
            try {
                // 移除队列
                System.out.println(queue.take());
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }

    public static void main(String[] args) throws InterruptedException {
        SynchronousQueue queue = new SynchronousQueue();
        // isEmpty() 总是返回true
        //  size() 总是返回0
        //  offer(E e) 如果另一个线程正在等待接收到该队列，则将指定的元素插入到该队列中。
        Producer producer = new Producer(queue);
        new Thread(producer).start();

        Consumer consumer = new Consumer(queue);
        new Thread(consumer).start();

    }
}

3.5、DelayQueue带有延时功能的阻塞队列

DelayQueue是一个没有边界BlockingQueue实现，加入其中的元素必需实现Delayed接口。当生产者线程调用put之类的方法加入元素时，会触发Delayed接口中的compareTo方法进行排序，也就是说队列中元素的顺序是按到期时间排序的，而非它们进入队列的顺序。排在队列头部的元素是最早到期的，越往后到期时间赿晚。
只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的 Delayed 元素。如果延迟都还没有期满，则队列没有头部，并且poll将返回null。当一个元素的 getDelay(TimeUnit.NANOSECONDS) 方法返回一个小于或等于零的值时，则出现期满，poll就以移除这个元素了。此队列不允许使用 null 元素。

最后说一下DelayQueue ,这里用个网上很经典的例子,网吧上网计时：

/**
 * 延时队列
 */
public class InternetBar implements Runnable {
    //网民队列,使用延时队列
    private DelayQueue<Netizen> dq = new DelayQueue<Netizen>();

    //上网
    public void startPlay(String id, String name, Integer money) {
        //截止时间= 钱数*时间+当前时间(1块钱1秒)
        Netizen netizen = new Netizen(id, name, 1000 * money + System.currentTimeMillis());
        System.out.println(name + "开始上网计费,剩余时间："+money+"s," + "当前时间" + new Date().getMinutes()
                + ":" + new Date().getSeconds());
        dq.add(netizen);
    }

    //时间到下机
    public void endTime(Netizen netizen) throws InterruptedException {
        System.out.println(netizen.getName() + "余额用完,下机时间：" + new Date().getMinutes()
                + ":" + new Date().getSeconds());
    }

    @Override
    public void run() {
        //线程,监控每个网民上网时长
        while (true) {
            try {
                // 除非时间到.否则会一直等待,直到取出这个元素为止
                Netizen netizen = dq.take();
                endTime(netizen);
                if("003".equals(netizen.getID())){
                    // 如果某一线程处理时间过长，队列后边的元素延期处理的时间会越来越长。
                    Thread.sleep(10000);
                    System.out.println("处理时间延长10s," + + new Date().getMinutes()
                            + ":" + new Date().getSeconds());
                }

            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

    }

    public static void main(String[] args) {
        //新建一个网吧
        InternetBar internetBar = new InternetBar();
        //来了几个个网民上网
        internetBar.startPlay("001", "张三", 3);
        internetBar.startPlay("002", "李四", 7);
        internetBar.startPlay("003", "王五", 5);
        internetBar.startPlay("004", "赵六", 8);
        internetBar.startPlay("005", "钱七", 9);
        Thread t1 = new Thread(internetBar);
        t1.start();
    }
}


class Netizen implements Delayed {
    //身份证
    private String ID;
    //名字
    private String name;
    //上网截止时间
    private long playTime;

    public Netizen(String iD, String name, long playTime) {
        ID = iD;
        this.name = name;
        this.playTime = playTime;
    }

    @Override
    public int compareTo(Delayed o) {
        Netizen netizen = (Netizen) o;
        return this.getDelay(TimeUnit.SECONDS) - o.getDelay(TimeUnit.SECONDS) > 0 ? 1 : 0;
    }

    //获取上网时长,即延时时长
    @Override
    public long getDelay(TimeUnit unit) {
        //上网截止时间减去现在当前时间=时长
        // 剩余延迟时间；零或负值指示延迟时间已经用尽
        return this.playTime - System.currentTimeMillis();
    }

    // get set方法略...

}

3.6、PriorityQueue基于堆实现的带有优先级的非阻塞队列

PriorityQueue 一个基于优先级的无界优先级队列。优先级队列的元素按照其自然顺序进行排序，或者根据构造队列时提供的 Comparator 进行排序，具体取决于所使用的构造方法。该队列不允许使用 null 元素也不允许插入不可比较的对象(没有实现Comparable接口的对象)。

对比 PriorityQueue 和 PriorityBlockingQueue

• PriorityQueue是非线程安全的，PriorityBlockingQueue是线程安全的
• PriorityBlockingQueue使用重入锁，每一个操作都需要加锁
• PriorityBlockingQueue扩容时使用了CAS操作
• 两者都使用了堆，算法原理相同
• PriorityBlockingQueue可以在queue为空时阻塞take操作

3.7、ConcurrentLinkedQueue基于链表无界线非阻塞队列

一个基于链接节点的无界线程安全队列。此队列按照 FIFO（先进先出）原则对元素进行排序。队列的头部 是队列中时间最长的元素。队列的尾部 是队列中时间最短的元素。
新的元素插入到队列的尾部，队列获取操作从队列头部获得元素。
【当多个线程共享访问一个公共 collection 时，ConcurrentLinkedQueue 是一个恰当的选择。】此队列不允许使用 null 元素。

ConcurrentLinkedQueue与LinkedBlockingQueue两者的区别在于

• ConcurrentLinkedQueue基于CAS的无锁技术，不需要在每个操作时使用锁，所以扩展性表现要更加优异，在常见的多线程访问场景，一般可以提供较高吞吐量。
• LinkedBlockingQueue内部则是基于锁，并提供了BlockingQueue的等待性方法。

3.8、Deque双端队列

一个线性 collection，支持在两端插入和移除元素。名称 deque 是“double ended queue（双端队列）”的缩写，通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制，但此接口既支持有容量限制的双端队列，也支持没有固定大小限制的双端队列。

双向队列操作
插入元素
addFirst(): 向队头插入元素，如果元素为null，则发生空指针异常
addLast(): 向队尾插入元素，如果为空，则发生空指针异常
offerFirst(): 向队头插入元素，如果插入成功返回true，否则返回false
offerLast(): 向队尾插入元素，如果插入成功返回true，否则返回false
移除元素
removeFirst(): 返回并移除队头元素，如果该元素是null，则发生NoSuchElementException
removeLast(): 返回并移除队尾元素，如果该元素是null，则发生NoSuchElementException
pollFirst(): 返回并移除队头元素，如果队列无元素，则返回null
pollLast(): 返回并移除队尾元素，如果队列无元素，则返回null
获取元素
getFirst(): 获取队头元素但不移除，如果队列无元素，则发生NoSuchElementException
getLast(): 获取队尾元素但不移除，如果队列无元素，则发生NoSuchElementException
peekFirst(): 获取队头元素但不移除，如果队列无元素，则返回null
peekLast(): 获取队尾元素但不移除，如果队列无元素，则返回null
栈操作
pop(): 弹出栈中元素，也就是返回并移除队头元素，等价于removeFirst()，如果队列无元素，则发生NoSuchElementException
push(): 向栈中压入元素，也就是向队头增加元素，等价于addFirst()，如果元素为null，则发生NoSuchElementException，如果栈空间受到限制，则发生IllegalStateException