Java集合--Queue(Java中实现1)

1.2 Java中的实现

上一篇,阐述了队列的实现结构,通过图片的形式让大家有了更进一步的了解。

接下来,我,我们来看看队列在Java具体是如何成仙了,来看下Queue的代码!!!

在Java中,ArrayDeque、LinkedList、PriorityQueue等类实现了Queue接口,模拟了队列的数据结构。

其中,PriorityQueue是Queue直接子类实现,在原有基础上实现了元素的排序功能。

除此之外,Queue还有一个子接口--Deque,对Queue进行了扩展,定义了头尾操作功能,既可在队头添加(删除)元素,也可在队尾添加(删除)元素,俗称“双端队列”。

接下来,我们来具体介绍下这几个实现类。

1.2.1 Queue源码(基于JDK1.7.0_45)

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

在Queue源码中,定义了队列的基本操作--在队尾插入元素,在队头获取(删除)元素;

1.2.2 PriorityQueue源码(基于JDK1.7.0_45)

作为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的总结如下:

PriorityQueue是线程不安全的队列;

PriorityQueue中不允许插入null元素;

PriorityQueue是一个用“堆结构”来实现的队列;

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏coding for love

JS入门难点解析10-创建对象

(注1:如果有问题欢迎留言探讨,一起学习!转载请注明出处,喜欢可以点个赞哦!) (注2:更多内容请查看我的目录。)

13630
来自专栏向治洪

SparseArray到底哪点比HashMap好

SparseArray是android里为<Interger,Object>这样的Hashmap而专门写的class,目的是提高效率,其核心是折半查找函数(bi...

22370
来自专栏大数据钻研

Java 集合框架 HashSet 和 HashMap 源码剖析

总体介绍 之所以把HashSet和HashMap放在一起讲解,是因为二者在Java里有着相同的实现,前者仅仅是对后者做了一层包装,也就是说HashSet里面有一...

30960
来自专栏来自地球男人的部落格

Comparison method violates its general contract!

今天在刷LeetCode题目的时候,问题使用HashMap按照value排序来解决,自定义比较器,但是报错:java.lang.IllegalArgumentE...

36480
来自专栏一枝花算不算浪漫

Java中常见数据结构Map之LinkedHashMap

34830
来自专栏大闲人柴毛毛

图的遍历(BFS+DFS)

图的遍历与树的遍历基本类似,但要注意两个不同: 1. 图中可能有环路,因此可能会导致死循环; 2. 一个图可能由多个独立的子图构成,因此一条路径走到头...

463110
来自专栏mukekeheart的iOS之旅

Java基础——集合框架

  Java的集合框架是Java中很重要的一环,Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。不同接口描述一组不同数据类型...

28260
来自专栏郭耀华‘s Blog

Java集合框架(五)—— Map、HashMap、Hashtable、Properties、SortedMap、TreeMap、WeakHashMap、IdentityHashMap、EnumMap

Map Map用于保存具有映射关系的数据,因此Map集合里保存着两组值,一组值用于保存Map里的key,另一组值用于保存Map里的value,key和v...

30780
来自专栏Java 源码分析

HashSet 源码分析

HashSet 源码分析 1. 在阅读源码时做了大量的注释,并且做了一些测试分析源码内的执行流程,由于博客篇幅有限,并且代码阅读起来没有 IDE 方便,所以在...

32740
来自专栏老马说编程

(55) 容器类总结 / 计算机程序的思维逻辑

从38节到54节,我们介绍了多种容器类,本节进行简要总结,我们主要从三个角度进行总结: 用法和特点 数据结构和算法 设计思维和模式 用法和特点 我们在52节...

22970

扫码关注云+社区

领取腾讯云代金券