集合类Queue（ArrayDequePriortyQueue）总结

一、ArrayDeque

简介

ArrayDeque类是双端队列的实现类，继承自AbastractCollection其实现的接口Deque接口中定义了双端队列的主要的方法，不允许null元素存在，实现了Cloneable、Serializable 接口，支持复制、序列化的。

成员变量

transient Object[] elements; transient int head; transient int tail; private static final int MIN_INITIAL_CAPACITY = 8;

head指向第一个有效元素位置，tail指向尾部第一个可以插入元素的空闲位置。

构造函数

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

无参构造函数，构造了一个大小为16的ArrayDeque。

public ArrayDeque(int numElements) { allocateElements(numElements); } private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; // Find the best power of two to hold elements. // Tests "<=" because arrays aren't kept full. if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } elements = new Object[initialCapacity]; }

有参构造调用allocateElements(numElements)，当用户要求分配的数组大小小于8时，分配8个空间。当用户要求分配的数组大小大于8时则分配大于用户需要内存的2的最小幂，最大分配2 ^ 30 大小的数组。

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

传入容器的构造函数。

操作方法

addFirst

public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); }

判断传入参数是否合法，不合法抛出空指针异常。head值先减1，然后将元素放到head位置， 如果head == tail 将数组大小扩大一倍。(head - 1) & (elements.length - 1) 使head的值在【0， elements.length - 1】范围之内，head一直围着数组转圈。head=tail时，数组中的元素已经满了，所以会将数组的扩大一倍。

addLast

public void addLast(E e) { if (e == null) throw new NullPointerException(); elements[tail] = e; if ( (tail = (tail + 1) & (elements.length - 1)) == head) doubleCapacity(); }

如果传入元素为null，抛出空指针异常。将传入值赋给tail位置。

removeFirst

public E removeFirst() { E x = pollFirst(); if (x == null) throw new NoSuchElementException(); return x; }

removeFirst方法调用了pollFirst方法，当容器为空时，removeFirst方法会抛出异常。下面给出pollFirst方法代码。

public E pollFirst() { int h = head; @SuppressWarnings("unchecked") E result = (E) elements[h]; // Element is null if deque empty if (result == null) return null; elements[h] = null; // Must null out slot head = (h + 1) & (elements.length - 1); return result; }

如果deque是空的，elment是null,调用elementAt方法。该方法其实就是在内部数组中根据下标，获取了一下元素。

removeLast

public E removeLast() { E x = pollLast(); if (x == null) throw new NoSuchElementException(); return x; } public E pollLast() { int t = (tail - 1) & (elements.length - 1); @SuppressWarnings("unchecked") E result = (E) elements[t]; if (result == null) return null; elements[t] = null; tail = t; return result; }

removeLast方法调用了pollLast方法，删除并返回当前末端的元素。当容器为空时，抛出异常。

二、PriortyQueue

简介

PriorityQueue是优先级队列，其底层通过堆实现，具体说是通过完全二叉树实现的小顶堆，排序采用自然排序或者通过提供的Comparator比较器去进行排序。不允许放入null元素。

成员变量

private static final int DEFAULT_INITIAL_CAPACITY = 11; transient Object[] queue; private int size = 0; private final Comparator<? super E> comparator; transient int modCount = 0; private static final long serialVersionUID = -7720805057305804111L;

PriorityQueue 使用数组 queue 来存储元素，默认初始容量是 11，最大容量是 Integer.MAX_VALUE - 8。comparator 若为 null，则按照元素的自然序来排列。modCount 用来提供 fail-fast 机制。

构造函数

public PriorityQueue() { this(DEFAULT_INITIAL_CAPACITY, null); } public PriorityQueue(int initialCapacity) { this(initialCapacity, null); } public PriorityQueue(Comparator<? super E> comparator) { this(DEFAULT_INITIAL_CAPACITY, comparator); } public PriorityQueue(int initialCapacity, Comparator<? super E> comparator) { // Note: This restriction of at least one is not actually needed, // but continues for 1.5 compatibility if (initialCapacity < 1) throw new IllegalArgumentException(); this.queue = new Object[initialCapacity]; this.comparator = comparator; } public PriorityQueue(Collection<? extends E> c) { if (c instanceof SortedSet<?>) { SortedSet<? extends E> ss = (SortedSet<? extends E>) c; this.comparator = (Comparator<? super E>) ss.comparator(); initElementsFromCollection(ss); } else if (c instanceof PriorityQueue<?>) { PriorityQueue<? extends E> pq = (PriorityQueue<? extends E>) c; this.comparator = (Comparator<? super E>) pq.comparator(); initFromPriorityQueue(pq); } else { this.comparator = null; initFromCollection(c); } } public PriorityQueue(PriorityQueue<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initFromPriorityQueue(c); } public PriorityQueue(SortedSet<? extends E> c) { this.comparator = (Comparator<? super E>) c.comparator(); initElementsFromCollection(c); }

PriorityQueue 的构造函数有 7 个，可以分为两类，提供初始元素和不提供初始元素，有比较器和没有比较器。PriorityQueue中的对象要么有自己单独的比较器，要么对象所在类实现Comparable接口，需要保证当前对象可比较。

add

public boolean add(E e) { return offer(e); } public boolean offer(E e) { if (e == null) throw new NullPointerException(); modCount++; int i = size; if (i >= queue.length) grow(i + 1); size = i + 1; if (i == 0) queue[0] = e; else siftUp(i, e); return true; }

先看传入参数是否合法，然后判断是否需要扩容，需要扩容调用grow方法来进行扩容。如果队列为空，直接添加进队列，如果队列不为空，调用siftUp函数，代码如下：

private void siftUp(int k, E x) { if (comparator != null) siftUpUsingComparator(k, x); else siftUpComparable(k, x); }

传入i为size，e为添加的值。如果传入比较器，按比较器比较进行添加，否则按自然顺序进行排序。

remove

public boolean remove(Object o) { int i = indexOf(o); if (i == -1) return false; else { removeAt(i); return true; } } private int indexOf(Object o) { if (o != null) { for (int i = 0; i < size; i++) if (o.equals(queue[i])) return i; } return -1; }

首先调用IndexOf（）找这个元素在数组中的位置，保证元素不为空， 调用removeAt（i）函数删除指定位置元素。

private E removeAt(int i) { // assert i >= 0 && i < size; modCount++; int s = --size; if (s == i) // removed last element queue[i] = null; else { E moved = (E) queue[s]; queue[s] = null; siftDown(i, moved); if (queue[i] == moved) { siftUp(i, moved); if (queue[i] != moved) return moved; } } return null; }

先size–，赋值给s，如果s等于i，删除的就是最后一个位置，直接置为空就删除掉了，反之要进行调整，将s位置置为空，然后用siftDown从上往下进行调整。如果所要删除的一个元素等于size-1的一个值，在进行从下往上siftUp。如果调整了以后不等于size-1的值，直接返回回去size-1的值。

private void siftDown(int k, E x) { if (comparator != null) siftDownUsingComparator(k, x); else siftDownComparable(k, x); }

该方法的作用是从k指定的位置开始，将x逐层向下与当前点的左右孩子中较小的那个交换，直到x小于或等于左右孩子中的任何一个为止。