Queue及其实现类

概要

Queue是继承于Collection的接口，是FIFO的单端队列。
- PriorityQueue实现了Queue，是优先队列。
Deque是继承于Queue的子接口，是双端队列。
- LinkedList实现了Deque，是双向链表。
ArrayQueue实现了Deque，是用数组表示的小顶堆。

一、Queue(interface)

是FIFO的接口，只有：添加元素到队尾、取队首元素并删除、取队首元素但不删除。

这些方法以两种形式存在：（1）操作失败时抛出异常；（2）操作失败时返回特殊值（false或null）。

要避免把null加入队列中。因为poll()方法返回null时，不确定是取到了null元素还是队列为空返回的null特殊值。

二、PriorityQueue(class)

1、优先队列、排序

PriorityQueue 实现了一个优先队列：从队首获取元素时，总是获取优先级最高的元素。

PriorityQueue 默认按元素比较的顺序排序（必须实现 Comparable 接口），也可以通过 Comparator 自定义排序算法（元素就不必实现 Comparable 接口）。

Queue<String> p = new PriorityQueue<>();//String元素实现了 Comparable 接口

Queue<User> q = new PriorityQueue<>(new UserComparator());//自定义UserComparator对象来判断两个元素的顺序
class UserComparator implements Comparator<User> {
    public int compare(User u1, User u2) {
        //...
    }
}

2、底层结构：数组表示的堆

PriorityQueue 底层数据结构是数组表示的小顶堆transient Object[] queue;。

二叉堆用数组来表示：父子节点下标关系为：

1
2
3

int leftNo = (parentNo << 1) + 1;     //leftNo = parentNo*2+1;
int rightNo = leftNo + 1;             //rightNo= parentNo*2+2;
int parentNo = (nodeNo - 1) >> 1;    //parentNo=(nodeNo-1)/2;

3、方法

add(E e)/offer(E e)：新加入的元素可能会破坏小顶堆的性质，需要向上调整。不允许加入null元素

poll()/remove(Object o)：删除堆顶或其他位置元素，也需要向下调整。

4、扩容

三、Deque(interface)

Deque接口扩展自Queue接口，实现了一个双端队列，可以当作栈使用，也可以当作队列使用。

使用Deque，最好是明确调用 offerLast()/offerFirst() 或者 pollFirst()/pollLast() 方法，更能直观表明操作队首还是队尾。

Deque 是一个接口，它的实现类有 ArrayDeque 和 LinkedList。

四、ArrayDeque(class)

数组方式实现的双端队列。

1、特点：

底层由数组实现，没有容量限制，根据需要扩容
不是线程安全的，在没有外部同步的情况下，不知道多线程并发访问
不允许放入null元素
用作堆栈时，比Stack快；用作队列时，比LinkedList快

2、属性：head、tail

底层数据结构为数组，最小长度为8，默认长度为16，若构造时指定初始长度，调用方法使长度始终为2的幂。

ArrayDeque中数组是当做环形/循环数组来使用的。

head指向队首第一个有效元素（也是removeFirst/pollFirst删除的元素）。

tail指向队尾第一个可以插入元素的空位（也是addLast/offerLast加入元素的位置）。

transient Object[] elements;

/**
 * The index of the element at the head of the deque (which is the
 * element that would be removed by remove() or pop()); or an
 * arbitrary number equal to tail if the deque is empty.
 */    
transient int head;

/**
 * The index at which the next element would be added to the tail
 * of the deque (via addLast(E), add(E), or push(E)).
 */
transient int tail;

3、方法：`addFirst()`/`offerFirst()`，`addLast()`/`offerLast()`。

addFirst(E e)是在队列的首端（即head的前面）加入元素。

addLast(E e)是在队列的尾端（即tail位置）加入元素。

public void addFirst(E e) {
    if (e == null) // 不允许放入null
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e; // 1、解决下标越界问题
    if (head == tail) // 2、扩容
        doubleCapacity();
}

1）新加入的元素数组下标为：(head - 1) & (elements.length - 1)，可以解决head-1下标越界问题。

不是直接通过head-1,tail-1等直接计算来更新head/tail，而是与element.length - 1做位与运算，解决下标越界问题。(element.length为2的幂)

// todo head-1为-1时，位与运算

2）判断扩容是在元素加入之后，因为 tail 指向队尾可插入的空位，保证数组elements至少有一个空位。

3、扩容

扩容是发生在元素插入之后，若head == tail（此时无空位），实现扩容两倍doubleCapacity()。

private void doubleCapacity() {
    assert head == tail;//无空位
    int p = head;
    int n = elements.length;
    int r = n - p; // number of elements to the right of p
    int newCapacity = n << 1
    if (newCapacity < 0)
        throw new IllegalStateException("Sorry, deque too big");
    Object[] a = new Object[newCapacity]; //创建2倍容量的新数组
  // arraycopy(Object src,  int  srcPos,Object dest, int destPos,int length);
    System.arraycopy(elements, p, a, 0, r);// 第一次复制 head 右边的元素 
    System.arraycopy(elements, 0, a, r, p);// 第二次复制 head 左边的元素
    elements = a;
    head = 0;// head指向元素不变
    tail = n;// tail指向空位
}

五、LinkedList

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    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。

六、用作：堆栈、队列

ArrayDeque和LinkedList都实现了队列Deque接口，可用作堆栈，也可用作队列。

ArrayDeque用作堆栈时，比Stack快；用作队列时，比LinkedList快

1、`Stack`继承自`Vector`（Vector是线程安全的List），已经过时。

2、用作栈的方法名称：

add/remove等方法操作失败时抛出异常；push/pop/peek/offer/poll等方法操作失败时返回特殊值（false或null）。

push(E e)/addFirst()
pop()/removeFirst()
peek()

3、用作队列的方法名称：

单端队列Queue
- offer(E e)/add(E e)：添加元素到队尾
- poll()/remove()：取队首元素并删除
- peek()/element()：取队首元素但不删除
双端队列Deque
- offerFirst()/addFirst()，offerLast()/addLast()
- pollFirst()/removeFirst()，pollLast()/removeLast()
- peekFirst()/getFirst()，peekLast()/getLast()

概要