Java集合-Queue

Queue接口定义如下：

	public interface Queue<E> extends Collection<E> {}

插入

    boolean add(E e);

	boolean offer(E e);

删除

    E remove();

    E poll();

检索

    E element();

    E peek();

AbstractQueue抽象类

AbstractQueue类提供Queue接口的核心实现，抽象类定义如下：

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {}

新增

    public boolean add(E e) {
        if (offer(e))
            return true;
        else
            throw new IllegalStateException("Queue full");
    }

删除

    public E remove() {
        E x = poll();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

检索

    public E element() {
        E x = peek();
        if (x != null)
            return x;
        else
            throw new NoSuchElementException();
    }

Deque接口

支持在两端插入和删除元素的线性集合。Deque接口定义了访问deque两端元素的方法。提供了插入、删除和检查元素的方法。

尾部插入

    void addLast(E e);

	boolean offerLast(E e);

尾部删除

    E removeLast();

	E pollLast();

尾部检索

    E getLast();

    E peekLast();

BlockingQueue接口

BlockingQueue实现是线程安全的，是一个可阻塞的队列。

	// 将指定的元素插入到此队列中，如果需要，则等待到指定的等待时间，以便空间可用。 
	boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException;
	
	// 检索并删除此队列的头，在必要时等待指定的等待时间，以使元素可用。
    E poll(long timeout, TimeUnit unit) throws InterruptedException;

简单的消费者生产者模式：

ArrayDeque类

ArrayDeque类中Deque接口是通过可调整数组实现。数组deque没有容量限制;它们根据需要增长以支持使用。

ArrayDeque定义如下：

    public class ArrayDeque<E> extends AbstractCollection<E>
                               implements Deque<E>, Cloneable, Serializable

核心属性

	// 存储deque元素的数组。deque的容量是这个数组的长度，它总是2的幂。数组永远不允许被填满，除非在addX方法中，它会在填满后立即调整大小
	transient Object[] elements;

	// deque头的元素的索引(这是将被remove()或pop()删除的元素);或者如果deque为空，则使用等于tail的任意数字。
    transient int head;

	// 将下一个元素添加到deque尾部的索引(通过addLast(E)、add(E)或push(E))。
    transient int tail;

扩容函数

	private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

构造函数

    public ArrayDeque() {
        elements = new Object[16];
    }

    public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

    public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

PriorityQueue类

基于优先级堆的无界优先级队列。优先级队列的元素根据它们的自然顺序排序，或者根据队列构造时提供的Comparator排序，这取决于使用的构造函数。优先队列不允许空元素。

PriorityQueue类定义如下：

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {}

构造函数

    // 创建一个具有默认初始容量(11)的PriorityQueue，根据元素的自然顺序对其进行排序。
	public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

	// 创建具有指定初始容量的PriorityQueue，根据元素的自然顺序对其排序
	public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

	// 创建一个具有默认初始容量的PriorityQueue，其元素根据指定的比较器排序。
    public PriorityQueue(Comparator<? super E> comparator) {
        this(DEFAULT_INITIAL_CAPACITY, comparator);
    }

扩容

    private void grow(int minCapacity) {
        int oldCapacity = queue.length;
        // Double size if small; else grow by 50%
        int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                         (oldCapacity + 2) :
                                         (oldCapacity >> 1));
        // overflow-conscious code
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        queue = Arrays.copyOf(queue, newCapacity);
    }

参考

Java容器之Queue (opens new window)