看看源码 -- Java集合(Queue接口篇)

Queue接口

JDK1.5新增的队列接口, 直接继承自顶级集合接口

public interface Queue<E> extends Collection<E> {
    
    // 往队列中添加一个元素, 若超过长度限制会抛异常
    boolean add(E e);
    
    // 往队列中添加一个元素, 若超过长度限制返回false
    boolean offer(E e);
    
    // 出队列, 空集合会抛异常
    E remove();

    // 出队列, 空集合返回null
    E poll();

    // 查看队首元素, 空集合抛异常
    E element();

    // 查看队首元素, 空集合返回null
    E peek();
}

除add是重写的Collection方法, 其余是新增的

AbstractQueue

AbstractQueue: 抽象队列, 实现了Queue同时继承了AbstractCollection抽象类

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();
    }

    public void clear() {
        while (poll() != null);
    }

   
    public boolean addAll(Collection<? extends E> c) {
        if (c == null)
            throw new NullPointerException();
        if (c == this)
            throw new IllegalArgumentException();
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
    }

}

可以看到AbstractQueue只是将会抛出异常的方法使用不会抛出异常的方法实现了

PriorityQueue

PriorityQueue: 优先级队列, 继承自AbstractQueue

引入的变量

// 使用数组来保存数据
transient Object[] queue;

int size;

// 比较器, 优先队列嘛, 需要不断比较优先级,
// 如果未指定比较器, 就按元素的自然顺序对优先级队列进行排序
private final Comparator<? super E> comparator;

// 见过很多次了, 记录集合结构变化的次数, 用于检测并发修改
transient int modCount;

注意到的是, queue 和modCount是非私有的, 这样做是为了嵌套类能直接访问, 主要就是迭代器可以直接访问, 还有就是他这里使用的是默认权限控制, 就是是同包下可以访问,但不同包下是不可以访问的

构造函数

public PriorityQueue(int initialCapacity,
                     Comparator<? super E> comparator) {
    if (initialCapacity < 1)
        throw new IllegalArgumentException();
    this.queue = new Object[initialCapacity];
    this.comparator = comparator;
}

这是主要的构造函数

扩容函数

private void grow(int minCapacity) {
    int oldCapacity = queue.length;
    // 小于64时每次增长2, 大于64时每次增长一半
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
                                     (oldCapacity + 2) :
                                     (oldCapacity >> 1));
    // 如果过最大尺寸了允许再继续扩容8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    queue = Arrays.copyOf(queue, newCapacity);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
    MAX_ARRAY_SIZE;
}

实现的函数

// 可以看到, 重写了AbstractQueue的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);
    siftUp(i, e);
    size = i + 1;
    return true;
}

// 直接返回堆顶元素, 并未重写element()函数,
// 若peek()返回null, element()还是会抛异常
public E peek() {
    return (E) queue[0];
}

// 同样未重写remove(), 调用remove()时,若poll返回null会抛异常
public E poll() {
    final Object[] es;
    final E result;

    if ((result = (E) ((es = queue)[0])) != null) {
        modCount++;
        final int n;
        final E x = (E) es[(n = --size)];
        es[n] = null;
        if (n > 0) {
            final Comparator<? super E> cmp;
            if ((cmp = comparator) == null)
                siftDownComparable(0, x, es, n);
            else
                siftDownUsingComparator(0, x, es, n, cmp);
        }
    }
    return result;
}

注意的是, offer函数不允许添加null元素, 也就是优先队列说不允许空元素

上滑函数

 private static <T> void siftUpComparable(int k, T x, Object[] es) {
     Comparable<? super T> key = (Comparable<? super T>) x;
     while (k > 0) {
         // 获得父节点下标
         int parent = (k - 1) >>> 1;
         Object e = es[parent];
         // 跟父节点比较
         if (key.compareTo((T) e) >= 0)
             break; // 如果大于等于父节点,则不再上滑
         es[k] = e; // 如果该节点小于父节点, 则父节点下滑
         k = parent; // 待调整节点上滑
     }
     es[k] = key; //最终将待调整节点放入上滑完毕后的位置
 }

从上面可以看出, 采用的是最小堆来实现的优先级队列, 也就是说优先级越高的其值应该越小, 下滑函数与上滑函数差不多, 就不贴代码了

Deque接口

Deque: 双端队列, 就是两端都可进可出, 继承自Queue接口

新增的方法

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();
    
    // 删除头尾元素, 未成功返回null
    E pollFirst();
    E pollLast();
    
    // 查看首尾元素, 未获取到抛异常
    E getFirst();
    E getLast();
    
    // 查看首尾元素, 未获取到返回null
    E peekFirst();
    E peekLast();
    
    // 可将双端队列用作栈
    void push(E e);
    E pop();
    
    // 删除第一次出现的某个元素
    boolean removeFirstOccurrence(Object o);
    
    // 删除最后一次出现的某个元素, 其实就是反向遍历第一次出现
    boolean removeLastOccurrence(Object o);
}

可以看到, 与Queue相比, Deque就是将原来的对首 / 尾的操作拓展为了对首尾的操作

ArrayDeque

ArrayDeque: 使用数组实现的双端队列, 实现了Deque接口, 继承了AbstractCollection抽象类

定义

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

新增的变量

// 不用说, 既然是数组实现的坑定用数组来保存数据
// 至于非私有跟PriorityQueue一样, 方便嵌套类直接访问而已
transient Object[] elements;

// 头指针,由数组的最后往前走
transient int head;

// 尾指针, 由数组的开始往后走, 指向的是下一个addLast()的位置
transient int tail;

扩容函数

private void grow(int needed) {
    final int oldCapacity = elements.length;
    int newCapacity;
    // 跟优先队列增长方式差不多
    int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
    if (jump < needed
        || (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
        newCapacity = newCapacity(needed, jump);
    final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
    // 异常情况下，tail == head需要消除歧义
    if (tail < head || (tail == head && es[head] != null)) {
        // 将原来头部数据整体向后移动
        int newSpace = newCapacity - oldCapacity;
        System.arraycopy(es, head,
                         es, head + newSpace,
                         oldCapacity - head);
        // 将新增位置清空
        for (int i = head, to = (head += newSpace);	 i < to; i++)
            es[i] = null;
    }
}

实现的方法

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    final Object[] es = elements;
    es[head = dec(head, es.length)] = e;
    if (head == tail)
        grow(1);
}

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}

// 这里遇到null还是会抛异常
public E removeFirst() {
    E e = pollFirst();
    if (e == null)
        throw new NoSuchElementException();
    return e;
}

public E pollFirst() {
    final Object[] es;
    final int h;
    E e = elementAt(es = elements, h = head);
    if (e != null) {
        es[h] = null;
        head = inc(h, es.length);
    }
    return e;
}

总结:

ArrayDeque: 使用数组实现的双端队列, 双端队列就是可以在头尾进行增删, ArrayDeque使用数组时逻辑上将数组分成了两段, 前半段表示尾部, 后半段表示头部, 这里的"半"并不是一半, 根据实际情况来, 如果一直从头部添加, 那后半段会越来越长, 每次扩容是先在数组尾部增加指定容量, 然后将后半段向后移动, 所以最终新增的容量会在"中间", 这样前后都能用

AbstractSequentialList抽象类

AbstractSequentialList: 抽象顺序表, 这个抽象类本来是List接口下的, 放到这里说是因为..., 不知道咋描述, 去看我整理的集合族谱就知道了

public abstract class AbstractSequentialList<E> extends AbstractList<E> {
   
    protected AbstractSequentialList() {
    }

    public E get(int index) {
        try {
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    public E set(int index, E element) {
        try {
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    public void add(int index, E element) {
        try {
            listIterator(index).add(element);
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    public E remove(int index) {
        try {
            ListIterator<E> e = listIterator(index);
            E outCast = e.next();
            e.remove();
            return outCast;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    public boolean addAll(int index, Collection<? extends E> c) {
        try {
            boolean modified = false;
            ListIterator<E> e1 = listIterator(index);
            for (E e : c) {
                e1.add(e);
                modified = true;
            }
            return modified;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    public Iterator<E> iterator() {
        return listIterator();
    }

    public abstract ListIterator<E> listIterator(int index);
}

比较简单, 就是使用迭代器实现了一些增删方法

LiskedList

LiskedList: 这个集合同时实现了List与Deque, 且使用的是链表的方式来实现, 接下来看源码

定义

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

新增的变量

// 见名知意, 集合的现有元素个数嘛
transient int size = 0;

// 头指针
transient Node<E> first;

// 尾指针
transient Node<E> last;

 private static class Node<E> {
     E item;
     Node<E> next;
     Node<E> prev;

     Node(Node<E> prev, E element, Node<E> next) {
         this.item = element;
         this.next = next;
         this.prev = prev;
     }
 }

可以看到每个节点都有前指针与后指针, 所以是双链表

实现的方法

由于实现了List和Deque连个接口, 实现的方法有点多, 我挑几个核心的看看

// 在头部添加一个节点
private void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

// 在尾部添加一个节点
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

// 在某个节点之前添加一个节点
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

// 删除头部节点
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

// 删除尾部节点
private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node<E> prev = l.prev;
    l.item = null;
    l.prev = null; // help GC
    last = prev;
    if (prev == null)
        first = null;
    else
        prev.next = null;
    size--;
    modCount++;
    return element;
}

// 删除某个节点
E unlink(Node<E> x) {
    // assert x != null;
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

这里将核心的增删操作方法列举了出来, 其他的什么add,remove, pop, push, poll, offer等方法都是用上面的核心方法来实现的