学习Queue看这篇就够了

2019-12-09

字数统计: 2k字 | 阅读时长≈ 8分

Queue

Queue是Java集合框架中的一员，继承于Collection接口。
与List、Set相同的是，Queue也实现了一种数据结构，这就是队列。

队列是计算机中的一种数据结构，保存在其中的数据具有“先进先出（FIFO,First In First Out）”的特性。
在数据结构中，队列不支持从队伍的中间插入和离开，只能从头尾进行。

队列的两种形式

在Java中，队列分为2种形式，一种是单队列，一种是循环队列；
通常，都是使用数组来实现队列。假定数组的长度为6，也就是队列的长度为6；

单队列：
第一步，创建一个空数组，有两个变量，分别为front、rear，代表着头指针、尾指针；

第二步，向队列中插入数据；

第三步，移除队头中的数据；

第四步，再次向队列中插数据（此时rear指针指向了一个不存在的角标）；

此时，单队列发生了“假溢出”情况，尾指针指向了一个不存在的数组角标。
如果，要解决该情况的发生，有两种方式—–一，无限扩充数组大小；二，引入循环队列；
- 循环队列：
  当尾指针超过了数组角标大小，此时我们会判断队列的头部是否有剩余的空间，如果有就把尾指针指向队列的头部；
  
  此时，循环队列就产生了。
  其实，循环队列就是将单队列的首位进行相连，形成了一个圆圈，这样就不会发生角标越界的情况了。
  在Java中，ArrayDeque、LinkedList、PriorityQueue等类实现了Queue接口，模拟了队列的数据结构。
  其中，PriorityQueue是Queue直接子类实现，在原有基础上实现了元素的排序功能。
  除此之外，Queue还有一个子接口–Deque，对Queue进行了扩展，定义了头尾操作功能，既可在队头添加(删除)元素，也可在队尾添加(删除)元素，俗称“双端队列”。
  Queue源码

//接口Queue：
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();
}

PriorityQueue源码

作为Queue的直接子类，PriorityQueue实现了Queue定义的方法。
不过，又与传统的队列不相。传统队列实现了“先进先出”数据模型，而PriorityQueue则实现了最小的元素优先出队，剩余元素依次按照大小顺序出队。
这就是所谓的“优先级队列”—元素按照任意的顺序插入，却总是按照顺序进行输出；每次从优先队列中取出来的元素要么是最大值，要么是最小值。接下来，我们来看下PriorityQueue具体是如何实现的：

PriorityQueue成员变量和构造方法：

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

    private static final long serialVersionUID = -7720805057305804111L;

    //默认初始化数组大小：
    private static final int DEFAULT_INITIAL_CAPACITY = 11;

    //队列底层数据结构：数组
    private transient Object[] queue;

    //队列长度：
    private int size = 0;

    //实现元素排序的比较器：
    private final Comparator<? super E> comparator;

    //对queue的操作次数：
    private transient int modCount = 0;

    //默认构造函数：
    public PriorityQueue() {
        this(DEFAULT_INITIAL_CAPACITY, null);
    }

    //可设置队列长度的构造函数：
    public PriorityQueue(int initialCapacity) {
        this(initialCapacity, null);
    }

    //可设置队列长度、元素比较器的构造函数：
    public PriorityQueue(int initialCapacity,
                         Comparator<? super E> comparator) {
        if (initialCapacity < 1)
            throw new IllegalArgumentException();
        this.queue = new Object[initialCapacity];
        this.comparator = comparator;
    }

    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}

PriorityQueue新增元素：

//队列添加元素，底层调用offer:插入失败抛出异常
public boolean add(E e) {
    return offer(e);
}

//队列添加元素: 插入失败返回false
public boolean offer(E e) {
    //不支持添加为null的元素：
    if (e == null)
        throw new NullPointerException();

    //队列操作数+1：
    modCount++;
    int i = size;

    //队列长度 >= 数组长度时，扩容：
    if (i >= queue.length)
        grow(i + 1);

    //队列长度+1
    size = i + 1;

    //i==0，在数组角标为0处插入第一个元素：
    if (i == 0)
        queue[0] = e;
    else
        //插入的不是第一个元素：
        siftUp(i, e);
    return true;
}

//对队列底层数组扩容：
private void grow(int minCapacity) {
    //现阶段数组长度：
    int oldCapacity = queue.length;
    
    //计算新数组的长度：
    // 如果 现阶段数组长度<64，则扩容为现阶段长度的2倍+2；
    // 如果 现阶段数组>=64，则扩容为现阶段长度的2倍+5；
    int newCapacity = oldCapacity + ((oldCapacity < 64) ?
            (oldCapacity + 2) :
            (oldCapacity >> 1));
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    
    //数组复制：得到新数组
    queue = Arrays.copyOf(queue, newCapacity);
}

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

PriorityQueue获取队列头部元素：

//返回队列头部的元素，不删除该元素(如果队列为空，则返回null)
public E peek() {
    if (size == 0)
        return null;
    return (E) queue[0];
}

//返回队列头部的元素，并删除该元素(如果队列为空，则返回null)
public E poll() {
    if (size == 0)
        return null;
    int s = --size;
    modCount++;
    E result = (E) queue[0];
    E x = (E) queue[s];
    queue[s] = null;
    if (s != 0)
        siftDown(0, x);
    return result;
}

PriorityQueue中核心方法：使用了比较器进行元素比较，当插入或者删除的元素后，对PriorityQueue中树的结构进行调整；

    private void siftUp(int k, E x) {
        //元素比较器不为null：
        if (comparator != null)
            siftUpUsingComparator(k, x);
        else
            //元素比较器为null：
            siftUpComparable(k, x);
    }

    //进行堆结构的siftUp运算：使用元素比较器
    private void siftUpComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>) x;
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (key.compareTo((E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = key;
    }

    //进行堆结构的siftUp运算：使用自定义元素比较器
    private void siftUpUsingComparator(int k, E x) {
        while (k > 0) {
            int parent = (k - 1) >>> 1;
            Object e = queue[parent];
            if (comparator.compare(x, (E) e) >= 0)
                break;
            queue[k] = e;
            k = parent;
        }
        queue[k] = x;
    }

    private void siftDown(int k, E x) {
        //元素比较器不为null:
        if (comparator != null)
            siftDownUsingComparator(k, x);
        else
            //元素比较器为null：
            siftDownComparable(k, x);
    }

    //进行堆结构的siftDown运算：使用元素比较器
    private void siftDownComparable(int k, E x) {
        Comparable<? super E> key = (Comparable<? super E>)x;
        int half = size >>> 1; 
        while (k < half) {
            int child = (k << 1) + 1; 
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                    ((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
                c = queue[child = right];
            if (key.compareTo((E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = key;
    }

    //进行堆结构的siftDown运算：使用自定义元素比较器
    private void siftDownUsingComparator(int k, E x) {
        int half = size >>> 1;
        while (k < half) {
            int child = (k << 1) + 1;
            Object c = queue[child];
            int right = child + 1;
            if (right < size &&
                    comparator.compare((E) c, (E) queue[right]) > 0)
                c = queue[child = right];
            if (comparator.compare(x, (E) c) <= 0)
                break;
            queue[k] = c;
            k = child;
        }
        queue[k] = x;
    }

    //返回队列中的比较器：
    public Comparator<? super E> comparator() {
        return comparator;
    }
}

从上面的源码中，可以看出，PriorityQueue是由“堆结构”来实现的队列。而“堆结构”又是通过数组形成的一颗完全二叉树。所以，我们在代码中可以看到PriorityQueue最底层数据结构就是数组。
经过上面的源码的分析，对PriorityQueue的总结如下：
1、PriorityQueue是线程不安全的队列；
2、PriorityQueue中不允许插入null元素；
3、PriorityQueue是一个用“堆结构”来实现的队列；

本文作者： 生活,生活?
本文链接： ayjcsgm.github.io/2019/12/09/学习Queue看这篇就够了/
版权声明： 本博客所有文章除特别声明外，均采用 Apache License 2.0 许可协议。转载请注明出处！