标签（空格分隔）： 数据结构 Java进阶

Java中的队列Queue

我们都知道队列(Queue)是一种先进先出(FIFO)的数据结构，Java中定义了java.util.Queue接口用来表示队列。Java中的Queue与List、Set属于同一个级别接口，它们都是继承于Collection接口。
Java中还定义了一种双端队列java.util.Deque，我们常用的LinkedList就是实现了Deque接口。

Queue & Deque

public interface Queue<E> extends Collection<E> {
    
    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();
}

public interface Deque<E> extends Queue<E> {

    void addFirst(E e);

    void addLast(E e);

    boolean offerFirst(E e);

    boolean offerLast(E e);

    E removeFirst();

    E removeLast();

    E pollFirst();

    E pollLast();

    E getFirst();

    E getLast();

    E peekFirst();

    E peekLast();

    boolean removeFirstOccurrence(Object o);

    boolean removeLastOccurrence(Object o);

    // *** Queue methods ***

    boolean add(E e);

    boolean offer(E e);

    E remove();

    E poll();

    E element();

    E peek();

    // *** Stack methods ***

    void push(E e);

    E pop();
    
    // *** Collection methods ***
    
    boolean remove(Object o);

    boolean contains(Object o);

    public int size();

    Iterator<E> iterator();

    Iterator<E> descendingIterator();

}

二、队列的实现

Java中对于队列的实现分为非阻塞和阻塞两种。

非阻塞队列分为如下

• LinkedList

• LinkedList是双相链表结构，在添加和删除元素的时具有比ArrayList更好的性能。但在Get和Set方面弱于ArrayList.当然，这些对比都是指数据量很大或者操作很频繁的情况下的对比。

• 当LinkedList作为队列使用时，尽量避免Collection的add()和remove()方法，而是要使用offer()来加入元素，使用poll()来获取并移出元素。它们的优点是通过返回值可以判断成功与否，add()和remove()方法在失败的时候会抛出异常。

• PriorityQueue

• PriorityQueue维护一个有序列表，存储到队列中的元素会按照自然顺序排列。当然，我们也可以给它指定一个实现了 java.util.Comparator 接口的排序类来指定元素排列的顺序。

• ConcurrentLinkedQueue

• ConcurrentLinkedQueue看名思义，ConcurrentLinkedQueue是一个基于链接节点的无界线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素并删除。

<font color = "red">注:PriorityQueue 和 ConcurrentLinkedQueue 类在 Collection Framework中加入两个具体集合实现。</font>

阻塞队列分为如下

阻塞队列定义在了java.util.concurrent包中，java.util.concurrent.BlockingQueue 继承了Queue接口，它有 5 个实现类，分别是

• ArrayBlockingQueue

• ArrayBlockingQueue一个内部由数组支持的有界队列。初始化时必须指定队列的容量，还可以设置内部的ReentrantLock是否使用公平锁。但是公平性会使你在性能上付出代价，只有在的确非常需要的时候再使用它。它是基于数组的阻塞循环队列，此队列按FIFO（先进先出）原则对元素进行排序。

• 它的思想就是如果BlockingQueue是空的，那么从BlockingQueue取东西的操作将会被阻断进入等待状态，直到BlockingQueue进了东西才会被唤醒。同样,如果BlockingQueue是满的，任何试图往里存东西的操作也会被阻断进入等待状态，直到BlockingQueue里有空间才会被唤醒继续操作。

• LinkedBlockingQueue

• LinkedBlockingQueue一个内部由链接节点支持的可选有界队列。初始化时不需要指定队列的容量，默认是Integer.MAX_VALUE，也可以看成容量无限大。此队列按 FIFO（先进先出）排序元素 。

• PriorityBlockingQueue

• PriorityBlockingQueue一个内部由优先级堆支持的无界优先级队列。队列中的元素按优先级顺序被移除。PriorityBlockingQueue就是PriorityQueue的加锁线程安全版。

• DelayQueue

• DelayQueue一个内部由优先级堆支持的、基于时间的调度队列。队列中存放Delayed元素，只有在延迟期满后才能从队列中提取元素。当一个元素的getDelay()方法返回值小于等于0时才能从队列中poll中元素，否则poll()方法会返回null。

• DelayQueue是一个无界阻塞队列，只有在延迟期满时才能从中提取元素。该队列的头部是延迟期满后保存时间最长的Delayed 元素。

• 缓存系统的设计，缓存中的对象，超过了空闲时间，需要从缓存中移出；任务调度系统，能够准确的把握任务的执行时间。我们可能需要通过线程处理很多时间上要求很严格的数据。可以考虑DelayQueue。

• SynchronousQueue

• SynchronousQueue它模拟的功能类似于生活中一手交钱一手交货这种情形，像那种货到付款或者先付款后发货模型不适合使用SynchronousQueue。

• SynchronousQueue 也是一个队列来的，但它的特别之处在于它内部没有容器，一个生产线程，当它生产产品（即put的时候），如果当前没有人想要消费产品(即当前没有线程执行take)，此生产线程必须阻塞，等待一个消费线程调用take操作，take操作将会唤醒该生产线程，同时消费线程会获取生产线程的产品（即数据传递），这样的一个过程称为一次配对过程(当然也可以先take后put,原理是一样的)。

下面简单介绍一下其中常用的方法：