欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

学习Queue看这篇就够了(源码分析)

程序员文章站 2022-05-23 16:21:35
...

Queue

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

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

队列的两种形式

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

  • 单队列:
    第一步,创建一个空数组,有两个变量,分别为front、rear,代表着头指针、尾指针;
    学习Queue看这篇就够了(源码分析)
    第二步,向队列中插入数据;
    学习Queue看这篇就够了(源码分析)
    第三步,移除队头中的数据;
    学习Queue看这篇就够了(源码分析)
    第四步,再次向队列中插数据(此时rear指针指向了一个不存在的角标);
    学习Queue看这篇就够了(源码分析)
    此时,单队列发生了“假溢出”情况,尾指针指向了一个不存在的数组角标。
    如果,要解决该情况的发生,有两种方式-----一,无限扩充数组大小;二,引入循环队列;

  • 循环队列:
    当尾指针超过了数组角标大小,此时我们会判断队列的头部是否有剩余的空间,如果有就把尾指针指向队列的头部;
    学习Queue看这篇就够了(源码分析)
    此时,循环队列就产生了。
    其实,循环队列就是将单队列的首位进行相连,形成了一个圆圈,这样就不会发生角标越界的情况了。
    在Java中,ArrayDeque、LinkedList、PriorityQueue等类实现了Queue接口,模拟了队列的数据结构。
    其中,PriorityQueue是Queue直接子类实现,在原有基础上实现了元素的排序功能。
    除此之外,Queue还有一个子接口–Deque,对Queue进行了扩展,定义了头尾操作功能,既可在队头添加(删除)元素,也可在队尾添加(删除)元素,俗称“双端队列”。
    学习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是一个用“堆结构”来实现的队列

相关标签: 集合