Queue接口
JDK1.5新增的队列接口, 直接继承自顶级集合接口
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();
}
除
add
是重写的Collection
方法, 其余是新增的
AbstractQueue
AbstractQueue
: 抽象队列, 实现了Queue
同时继承了AbstractCollection
抽象类
public abstract class AbstractQueue<E>
extends AbstractCollection<E>
implements Queue<E> {
public boolean add(E e) {
if (offer(e))
return true;
else
throw new IllegalStateException("Queue full");
}
public E remove() {
E x = poll();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public E element() {
E x = peek();
if (x != null)
return x;
else
throw new NoSuchElementException();
}
public void clear() {
while (poll() != null);
}
public boolean addAll(Collection<? extends E> c) {
if (c == null)
throw new NullPointerException();
if (c == this)
throw new IllegalArgumentException();
boolean modified = false;
for (E e : c)
if (add(e))
modified = true;
return modified;
}
}
可以看到
AbstractQueue
只是将会抛出异常的方法使用不会抛出异常的方法实现了
PriorityQueue
PriorityQueue
: 优先级队列, 继承自AbstractQueue
引入的变量
// 使用数组来保存数据
transient Object[] queue;
int size;
// 比较器, 优先队列嘛, 需要不断比较优先级,
// 如果未指定比较器, 就按元素的自然顺序对优先级队列进行排序
private final Comparator<? super E> comparator;
// 见过很多次了, 记录集合结构变化的次数, 用于检测并发修改
transient int modCount;
注意到的是,
queue
和modCount
是非私有的, 这样做是为了嵌套类能直接访问, 主要就是迭代器可以直接访问, 还有就是他这里使用的是默认权限控制, 就是是同包下可以访问,但不同包下是不可以访问的
构造函数
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
这是主要的构造函数
扩容函数
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// 小于64时每次增长2, 大于64时每次增长一半
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// 如果过最大尺寸了允许再继续扩容8
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
实现的函数
// 可以看到, 重写了AbstractQueue的add方法, 并不会抛异常
public boolean add(E e) {
return offer(e);
}
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
siftUp(i, e);
size = i + 1;
return true;
}
// 直接返回堆顶元素, 并未重写element()函数,
// 若peek()返回null, element()还是会抛异常
public E peek() {
return (E) queue[0];
}
// 同样未重写remove(), 调用remove()时,若poll返回null会抛异常
public E poll() {
final Object[] es;
final E result;
if ((result = (E) ((es = queue)[0])) != null) {
modCount++;
final int n;
final E x = (E) es[(n = --size)];
es[n] = null;
if (n > 0) {
final Comparator<? super E> cmp;
if ((cmp = comparator) == null)
siftDownComparable(0, x, es, n);
else
siftDownUsingComparator(0, x, es, n, cmp);
}
}
return result;
}
注意的是,
offer
函数不允许添加null
元素, 也就是优先队列说不允许空元素
上滑函数
private static <T> void siftUpComparable(int k, T x, Object[] es) {
Comparable<? super T> key = (Comparable<? super T>) x;
while (k > 0) {
// 获得父节点下标
int parent = (k - 1) >>> 1;
Object e = es[parent];
// 跟父节点比较
if (key.compareTo((T) e) >= 0)
break; // 如果大于等于父节点,则不再上滑
es[k] = e; // 如果该节点小于父节点, 则父节点下滑
k = parent; // 待调整节点上滑
}
es[k] = key; //最终将待调整节点放入上滑完毕后的位置
}
从上面可以看出, 采用的是最小堆来实现的优先级队列, 也就是说优先级越高的其值应该越小, 下滑函数与上滑函数差不多, 就不贴代码了
Deque接口
Deque
: 双端队列, 就是两端都可进可出, 继承自Queue
接口
新增的方法
public interface Deque<E> extends Queue<E> {
// 添加元素, 没添加成功抛异常
void addFirst(E e);
void addLast(E e);
// 添加元素, 成功与否通过返回值确定
boolean offerFirst(E e);
boolean offerLast(E e);
// 删除头尾元素, 未成功抛异常
E removeFirst();
E removeLast();
// 删除头尾元素, 未成功返回null
E pollFirst();
E pollLast();
// 查看首尾元素, 未获取到抛异常
E getFirst();
E getLast();
// 查看首尾元素, 未获取到返回null
E peekFirst();
E peekLast();
// 可将双端队列用作栈
void push(E e);
E pop();
// 删除第一次出现的某个元素
boolean removeFirstOccurrence(Object o);
// 删除最后一次出现的某个元素, 其实就是反向遍历第一次出现
boolean removeLastOccurrence(Object o);
}
可以看到, 与
Queue
相比,Deque
就是将原来的对首 / 尾的操作拓展为了对首尾的操作
ArrayDeque
ArrayDeque
: 使用数组实现的双端队列, 实现了Deque
接口, 继承了AbstractCollection
抽象类
定义
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
新增的变量
// 不用说, 既然是数组实现的坑定用数组来保存数据
// 至于非私有跟PriorityQueue一样, 方便嵌套类直接访问而已
transient Object[] elements;
// 头指针,由数组的最后往前走
transient int head;
// 尾指针, 由数组的开始往后走, 指向的是下一个addLast()的位置
transient int tail;
扩容函数
private void grow(int needed) {
final int oldCapacity = elements.length;
int newCapacity;
// 跟优先队列增长方式差不多
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// 异常情况下,tail == head需要消除歧义
if (tail < head || (tail == head && es[head] != null)) {
// 将原来头部数据整体向后移动
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
// 将新增位置清空
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}
实现的方法
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
final Object[] es = elements;
es[head = dec(head, es.length)] = e;
if (head == tail)
grow(1);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
// 这里遇到null还是会抛异常
public E removeFirst() {
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
总结:
ArrayDeque
: 使用数组实现的双端队列, 双端队列就是可以在头尾进行增删,ArrayDeque
使用数组时逻辑上将数组分成了两段, 前半段表示尾部, 后半段表示头部, 这里的"半"并不是一半, 根据实际情况来, 如果一直从头部添加, 那后半段会越来越长, 每次扩容是先在数组尾部增加指定容量, 然后将后半段向后移动, 所以最终新增的容量会在"中间", 这样前后都能用
AbstractSequentialList抽象类
AbstractSequentialList
: 抽象顺序表, 这个抽象类本来是List接口下的, 放到这里说是因为..., 不知道咋描述, 去看我整理的集合族谱就知道了
public abstract class AbstractSequentialList<E> extends AbstractList<E> {
protected AbstractSequentialList() {
}
public E get(int index) {
try {
return listIterator(index).next();
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E set(int index, E element) {
try {
ListIterator<E> e = listIterator(index);
E oldVal = e.next();
e.set(element);
return oldVal;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public void add(int index, E element) {
try {
listIterator(index).add(element);
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public E remove(int index) {
try {
ListIterator<E> e = listIterator(index);
E outCast = e.next();
e.remove();
return outCast;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public boolean addAll(int index, Collection<? extends E> c) {
try {
boolean modified = false;
ListIterator<E> e1 = listIterator(index);
for (E e : c) {
e1.add(e);
modified = true;
}
return modified;
} catch (NoSuchElementException exc) {
throw new IndexOutOfBoundsException("Index: "+index);
}
}
public Iterator<E> iterator() {
return listIterator();
}
public abstract ListIterator<E> listIterator(int index);
}
比较简单, 就是使用迭代器实现了一些增删方法
LiskedList
LiskedList
: 这个集合同时实现了List
与Deque
, 且使用的是链表的方式来实现, 接下来看源码
定义
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
新增的变量
// 见名知意, 集合的现有元素个数嘛
transient int size = 0;
// 头指针
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连个接口, 实现的方法有点多, 我挑几个核心的看看
// 在头部添加一个节点
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
// 在尾部添加一个节点
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
// 在某个节点之前添加一个节点
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
// 删除头部节点
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
first = next;
if (next == null)
last = null;
else
next.prev = null;
size--;
modCount++;
return element;
}
// 删除尾部节点
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
last = prev;
if (prev == null)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
// 删除某个节点
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
这里将核心的增删操作方法列举了出来, 其他的什么add,
remove
,pop
,push
,poll
,offer
等方法都是用上面的核心方法来实现的