Java中的集合(三)继承Collection的Queue接口

时间:2023-04-14 14:33:14

Java中的集合(三)继承Collection的Queue接口

一、Queue介绍

Queue接口继承自Collection接口,是Java中定义的一种队列数据结构,元素是有序的(按插入顺序排序),先进先出(FIFO)原则。不支持随机访问数据,新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。

队列:是计算机中的一种数据结构,保存在其中的数据具有“先进先出(FIFO,First In First Out)”的特性,新元素插入(offer)到队列的尾部,访问元素(poll)操作会返回队列头部的元素。通常,队列不允许随机访问队列中的元素。

在Java中,队列分为2种形式,一种是单队列,一种是循环队列;

  通常,都是使用数组来实现队列,假定数组的长度为5,也就是队列的长度为5;

  (一)、单队列:

1、创建一个长度为5的空数组,定义两个属性front、rear,分别代表着头指针和尾指针。

Java中的集合(三)继承Collection的Queue接口

2、向数组中插入数据

Java中的集合(三)继承Collection的Queue接口

3、移除头部元素:元素1、元素2

Java中的集合(三)继承Collection的Queue接口

4、再向数组中插入数据,此时rear指向一个不存在的下标

Java中的集合(三)继承Collection的Queue接口

此时,数组就会出现“假溢出”的现象,尾指针指向了一个不存在的下标,如果要解决这种情况,一般有两种方法:

1、无限扩充数组容量;

2、使用循环队列。

(二)、循环队列

当尾指针指向了一个不存在的下标时,即超过数组大小时,此时我们判断数组头部是否有空余的空间,如果有就把尾指针指向头部空余的空间,如下图:

Java中的集合(三)继承Collection的Queue接口

循环队列就是将单队列的头尾相连,形成一个圆形,这样就不会出现下标溢出的现象(distruptor实现)。

二、Queue类图

Java中的集合(三)继承Collection的Queue接口

1、Queue接口继承自Collection接口;

2、Queue接口分别有Deque子接口和AbstractQueue抽象类;

3、Deque子接口分别有LinkedList类和ArrayDeque类;

4、AbstractQueue抽象类有PriorityQueue实现类

三、Deque(Double-ended queue)接口

Deque接口是Queue接口的子接口,创建了双端队列结构,灵活性更强,可以前向或后向迭代,在队头队尾均可插入或删除元素的线性集合。它的两个主要实现类是ArrayDeque和LinkedList。

Deque接口支持容量固定的双端队列,也支持容量不固定的双端队列,一般情况下,双端队列的容量是不固定的。

(一)、特点

1、插入、删除、获取操作支持两种形式:快速失败和返回nulltrue/false;

2、既具有FIFO(First in, First out,先进先出)特性,又具有LIFO(Last in, First out,后进先出)特性;

3、不推荐插入null,因为null作为返回值表示队列为空;

4、未定义基于元素的equals和hashCode;

5、不支持索引访问元素;

6、Deque不仅是双端队列,还可以当做栈来使用,因为该类定义了pop(出站),push(入栈)等方法。

(二)、Deque接口与Queue接口、Stack的关系

从上面描述可以知道,Deque不仅可以当做双端队列使用,还可以当做栈来使用。

1、Deque当做双端队列使用时,Deque接口与Queue接口的关系

当 Deque 当做 Queue队列使用时(FIFO),添加元素是添加到队尾,删除时删除的是头部元素。从 Queue 接口继承的方法对应Deque 的方法如图所示:

Java中的集合(三)继承Collection的Queue接口

2、Deque当做栈使用时,Deque接口与Stack的关系

当Deque 当做Stack栈用(LIFO)。这时入栈、出栈元素都是在 双端队列的头部 进行。Deque 中和Stack对应的方法如图所示:

Java中的集合(三)继承Collection的Queue接口

注意:由于Stack比较古老,功能实现非常不友好,现在已经基本不适用程序开发,因此可以选择Deque接口代替Stack进行栈操作。

四、ArrayDeque实现类

Deque接口下分别有两个实现类,分别为ArrayDeque和LinkedList,LinkedList在本节暂不讲述,这节主要讲述ArrayDeque。

(一)、ArrayDeque:基于循环数组实现的线性双端队列,大小可变,不允许null。

1、底层是通过数组实现的,数组大小默认是16,可以指定长度,也可不指定,根据添加元素的个数,动态扩容数组容量。可以为了满足可以同时插入和删除元素,需要该数组必须是循环数组,也就是数组中的每一个点都可以看成是起点或者终点。

2、ArrayDeque是线程不安全的,在多线程环境下,需要手动同步;另外,ArrayDeque不允许插入null元素。

3、由于ArrayDeque是基于头尾指针来实现Deque的,所以不能直接访问第一个和最后一个元素,如果想要遍历元素,需要使用Iterator迭代器,可以使用正反迭代遍历元素。

4、ArrayDeque一般优于链表队列/双端队列,有限数量的垃圾产生(旧数组将被丢弃在扩展),建议使用deque,ArrayDeque优先。

(二)、ArrayDeque操作简图

假定数组的长度为6,也就是ArrayDeque队列的长度为6;

Java中的集合(三)继承Collection的Queue接口

Java中的集合(三)继承Collection的Queue接口

从上面图中可以看出:front总是指向数组中的第一个有效元素的位置,rear终是指向第一个可以可以插入元素的空间位置,所以front并一定等于0,且不总会比rear大,rear也不总是比front小。

(三)、ArrayDeque中,循环数组的实现

ArrayDeque维护了两个属性,分别指向头指针和尾指针:

transient int head; // 指向头指针

transient int tail; // 指向尾指针

假定数组的长度为10,也就是ArrayDeque队列的长度为10;

1、ArrayDeque刚创建时;

Java中的集合(三)继承Collection的Queue接口

2、当向尾部插入时,直接在tail下标的位置插入元素,所以tail下标 + 1,head小标不变;

Java中的集合(三)继承Collection的Queue接口

3、当从头部插入时,head下标 - 1,然后插入元素,tail下标为当前数组末尾元素的下标不变;

Java中的集合(三)继承Collection的Queue接口Java中的集合(三)继承Collection的Queue接口

通过上面的步骤可以知道,将ArrayDeque看出成是一个首尾相接的圆形数组更好理解循环数组的含义。

通过addFrist(E e)代码,看看ArrayQueue是如何实现的:

 public void addFirst(E e) {
if (e == null)
throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
    • 当加入元素时,先看是否为空(ArrayDeque不可以存取null元素,因为系统根据某个位置是否为null来判断元素的存在)。然后head-1,插入元素。
    • head = (head - 1) & (elements.length - 1)很好的解决了下标越界的问题。这段代码相当于取模,同时解决了head为负值的情况。因为elements.length必需是2的指数倍(代码中有具体操作),elements - 1就是二进制低位全1,跟head - 1相与之后就起到了取模的作用。如果head - 1为负数,其实只可能是-1,当为-1时,和elements.length - 1进行与操作,这时结果为elements.length - 1。其他情况则不变,等于它本身。
    • 当插入元素后,在进行判断是否还有余量。因为tail总是指向下一个可插入的空位,也就意味着elements数组至少有一个空位,所以插入元素的时候不用考虑空间问题。

(四)、扩容函数doubleCapacity()

扩容函数doubleCapacity()的逻辑是:申请一个更大容量的数组,将原数组原样复制到新数组中。

Java中的集合(三)继承Collection的Queue接口

从上图可以看出,复制分为两次进行:先复制head右边的元素,然后再复制head左边的元素。

 private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // head右边元素的个数
int newCapacity = n << 1;//原空间的2倍
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);//复制右半部分,对应上图中绿色部分
System.arraycopy(elements, 0, a, r, p);//复制左半部分,对应上图中灰色部分
elements = (E[])a;
head = 0;
tail = n;
}

(五)、小结

通过上面描述,我们便理解了ArrayDeque循环数组添加以及扩容的过程,另外需要注意的是:ArrayDeque不是线程安全的。 当作为栈使用时,性能比Stack好;当作为队列使用时,性能比LinkedList好。

五、PriorityQueue实现类

(一)、PriorityQueue:底层基于数组实现的堆结构的优先队列。

PriorityQueue是AbstractQueue的子类,AbstractQueue又实现了Queue接口,所以PriorityQueue具有Queue接口的优先队列。

 优先队列与普通队列不同,普通队列遵循“FIFO”的特性,获取元素时根据元素的插入顺序获取,优先队列获取元素时根据元素的优先级,获取优先级最高的数据。

(二)、PriorityQueue的排序方式

PriorityQueue保存队列元素时不是按照插入队列顺序进行排序,而是按照插入元素的大小进行排序的。因此当调用peek()、pop()方法时,不是取出最先插入的元素,而是取出队列当中最小元素。

1、排序的方式

PriorityQueue队列当中的元素是可以默认自然排序(数值型元素默认是最小的在队列头部,字符串则按字典序排序),或者通过Comparator(比较器)在队列实例化指定排序方式。

注意:当PriorityQueue中没有指定Comparator时,加入PriorityQueue的元素必须实现了Comparable接口(即元素是可比较的),否则会导致 ClassCastException。

(三)、PriorityQueue的本质

PriorityQueue本质是一个动态数组,默认实现由三种构造方法:

  1. public PriorityQueue() 调用无参构造方法时,使用默认的初始容量(DEFAULT_INITIAL_CAPACITY=11)来创建PriorityQueue,并根据其自然顺序排序其中的元素(排序方式使用的是元素中实现的Comparable接口);
  2. public PriorityQueue(int initialCapacity) 调用指定容量构造方法时,使用initialCapacity定义初始容量创建PriorityQueue,并根据其自然顺序排序其中的元素(排序方式使用的是元素中实现的Comparable接口);
  3. PriorityQueue(int initialCapacity,Comparator<? super E> comparator) 当使用指定的初始容量创建一个 PriorityQueue,并根据指定的比较器comparator来排序其元素。

从上面的三个构造函数可以得出:PriorityQueue内部维护了一个动态数组,

除此之外,还要注意:

    • PriorityQueue不是线程安全的。如果多个线程中的任意线程从结构上修改了列表, 则这些线程不应同时访问 PriorityQueue 实例,这时请使用线程安全的PriorityBlockingQueue 类。
    • 不允许插入 null 元素。
    • PriorityQueue实现插入方法(offer、poll、remove() 和 add 方法) 的时间复杂度是O(log(n)) ;实现 remove(Object) 和 contains(Object) 方法的时间复杂度是O(n) ;实现检索方法(peek、element 和 size)的时间复杂度是O(1)。所以在遍历时,若不需要删除元素,则以peek的方式遍历每个元素。
    • 方法iterator()中提供的迭代器并不保证以有序的方式遍历优PriorityQueue中的元素。

(四)、自然排序和Comparator比较器

1、Java中的两种比较器:Conparator和Comparable

Comparable和Comparator接口都是为了对类进行比较,众所周知,诸如int,double等基本数据类型,Java可以对他们进行比较,而对于对象即类的比较,需要人工定义比较用到的字段比较逻辑。可以把Comparable理解为内部比较器,而Comparator是外部比较器

(1)、Comparable接口:内部比较器,实现了Comparable接口的类需要实现compareTo(T o)方法,传入一个外部参数进行比对;

当一个对象调用该compareTo(T o)方法与另一个对象比较时,例如o1.compareTo(o2)

  • 如果该方法返回0,则表明两个对象相等;
  • 如果该方法返回一个整数,则表明o1大于o2;
  • 如果该方法返回一个负整数,则表明o1小于o2。

(2)、Conparator接口:外部比较器,实现了Comparator接口的方法需要实现compare(T o1,T o2)方法,对外部传入的两个类进行比较,从而让外部方法在比较时调用;

该compare(T o1,T o2)方法用于比较o1,o2的大小:

  • 如果该方法返回正整数,则表明o1大于o2;
  • 如果该方法返回0,则表明o1等于o2;
  • 如果该方法返回负整数,则表明o1小于o2。

2、自然排序

自然排序是调用元素所属类的compareTo(T o)方法来比较元素之间的大小关系,然后将集合元素按升序排列,即把通过compareTo(T o)方法比较后比较大的的往后排。这种方式就是自然排序。