|
|
Queue
queue是一种先进先出的数据结构也叫FIFO（First In First Out）。
可以想象成小朋友滑滑梯，先滑的先出来，一个接一个。
实现的主要方法有
// 往队列插入元素，队列满了，报错抛出异常
boolean add(E e);
// 往队列插入元素，满了返回false
boolean offer(E e);
// 移除并且返回头部的元素,如果为空的报错抛出异常
E remove();
// 移除并且返回头部的元素，如果为空的返回null
E poll();
// 返回头部元素但不删除，如果为空的报错抛出异常
E element();
// 返回头部元素但不删除，如果为空的返回null
E peek();因此在开发过程中尽量不要使用add（），remove（），element（）会抛出异常的方法，当然我们也很少用到queue接口。
PriorityQueue
PriorityQueue是queue的实现类，也叫优先队列。
作用：PriorityQueue保存元素的顺序并不是按照加入的顺序，而是根据元素的大小（实现Comparable接口或提供Comparator类）来决定元素在Queue队列中的顺序。默认情况如果我们存入Integer对象，则是按升序排列。
PriorityQueue<Integer> queue = new PriorityQueue<>();
queue.offer(10);
queue.offer(1);
queue.offer(4);
queue.offer(6);
queue.offer(7);
queue.offer(8);
queue.offer(9);
queue.offer(2);
queue.offer(3);
queue.offer(5);
while (queue.size()>0){
System.err.print(queue.poll()+&#34;->&#34;);
}
下图为继承关系
初始化
// 默认长度11
private static final int DEFAULT_INITIAL_CAPACITY = 11;
// 基于数组实现
transient Object[] queue; // n
private int size = 0;
private final Comparator<? super E> comparator;
// 自定义的比较规则，有该规则时优先使用，默认Comparable接口方法。
transient int modCount = 0; // non-private to simplify nested class access
// 初始化默认长度
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null);
}
public PriorityQueue(int initialCapacity) {
this(initialCapacity, null);
}
// 定义Comparator的排序规则
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < 1)
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}
// 当前容量小于64，则容量增加2；如果当前容量大于等于64，则变为原来的1.5倍。
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by 50%
int newCapacity = oldCapacity + ((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity >> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue, newCapacity);
}新增元素
执行新增操作的时候，
第一个新增的元素会会放在头部，siftUp方法中插入一个新元素，会对其新元素进行排序处理，实际通过compareTo方法，新老的元素对比，交换位置。
这样每次进来都会对该元素进行排序运算，保证了Queue中第一个元素永远是最小的
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1);
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
// 优先使用Comparator
private void siftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
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;
}
//
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;
}小结
PriorityQueue是**优先队列**，**允许排序**的，默认**长度11**，
扩容时候当前容量小于64，则容量增加2；
如果当前容量大于等于64，则变为原来的1.5倍。
每次新增元素的时候都会通过compareTo重新对比，确定新元素的位置。
Deque 非 Queue
Deque英文全称是Double ended queue也叫双端队列，码如其名，可以选择从头部获取、添加也可以从尾部获取、添加。
滑滑梯倒着溜？
那么Deque和Queue名字这么相近又有什么关系？
父子关系
从下方继承图可以看出，Deque继承Queue
Deque 我称多面手，支持的数据结构除了自己的双端队列结构和继承的队列结构外还支持栈结构。
实现的主要方法有
属于双端队列的
// 头部添加元素
void addFirst(E e);
// 尾部添加元素
void addLast(E e);
// 头部添加元素，成功返回true
boolean offerFirst(E e);
// 尾部添加元素，成功返回true
boolean offerLast(E e);
// 删除头部元素并返回，如果队列为空抛出异常
E removeFirst();
// 删除尾部元素并返回，如果队列为空抛出异常
E removeLast();
// 删除头部元素并返回，如果队列为空返回null
E pollFirst();
// 删除尾部元素并返回，如果队列为空返回null
E pollLast();
// 获取头部元素并返回，如果队列为空抛出异常
E getFirst();
// 获取尾部元素并返回，如果队列为空抛出异常
E getLast();
// 获取头部元素并返回，如果队列为空返回null
E peekFirst();
// 获取尾部元素并返回，如果队列为空返回null
E peekLast();
// 删除第一次出现的制定元素
boolean removeFirstOccurrence(Object o);
// 删除最后一次出现的制定元素
boolean removeLastOccurrence(Object o);属于队列的
// 往队列插入元素，队列满了，报错抛出异常
boolean add(E e);
// 往队列插入元素，满了返回false
boolean offer(E e);
// 移除并且返回头部的元素,如果为空的报错抛出异常
E remove();
// 移除并且返回头部的元素，如果为空的返回null
E poll();
// 返回头部元素但不删除，如果为空的报错抛出异常
E element();
// 返回头部元素但不删除，如果为空的返回null
E peek();属于栈的
// 获取队头元素，如果队列为null将返回null
E peek();
// 栈顶添加一个元素
void push(E e);
// 移除栈顶元素，返回移除的元素，如果栈没有元素抛出异常。
E pop();ArrayDeque
ArrayDeque是基于数组的形式实现双端队列，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即**循环数组**。
循环数组：数组的任何一点都可能被看作起点或者终点。
按照惯例继承图
初始化
transient Object[] elements;
transient int head;
transient int tail;
// 默认长度为8但是
private static final int MIN_INITIAL_CAPACITY = 8;
// 初始化的时候是16
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
// 每次扩容x2，超过就会触发扩容
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests &#34;<=&#34; because arrays aren&#39;t kept full.
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
return initialCapacity;
}新增元素
elements[head = (head - 1) & (elements.length - 1)] = e;
不是很理解，查了一下资料说原理是如果一个二进制数全部由1组成和一个大于它的数做&运算结果为0，主要是为了解决数组下标越界问题。
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
// 用2倍大的数组把原数组装进去，套娃？
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(&#34;Sorry, deque too big&#34;);
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
// 明白为啥不抛出异常了吧
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}ArrayDeque是个循环数组，默认值是8但是初始化长度16，
每次扩容x2，很少用，总结完毕。
给个一键三连吧
 |
|
发表于 2022-12-21 20:38:52