作者:小傅哥 博客:https://bugstack.cn
❝沉淀、分享、成长,让自己和他人都能有所收获!😜 ❞
什么是队列?
在计算机科学中,队列(queue)是一种特殊类型的抽象数据类型或集合(可以用链表实现,也可以用数组实现)。集合中的实体对象按顺序保存,可以通过在序列的一端添加实体和从序列的另一端移除实体来进行修改。
将元素添加到队列后的操作称为入队,从队列中移除元素的操作称为出队。也允许其他的一些操作,包括 peek、element等。另外队列还分为单端队列(queue)和双端队列(deque),这在本章节要实现的优先队列中会有所体现。
在计算机科学中, 一个队列(queue)是一种特殊类型的抽象数据类型或集合。集合中的实体按顺序保存。
队列的数据结构更像是数组和链表的变种,只要能看懂数组和链表,就能看懂队列。那么这里我们来扩展实现一个延迟队列,并在这个过程中会涉及到阻塞队列、优先队列的使用。通过这样的一个手写源码的学习队列的扩展使用。
本章节我们就借着数组结构的学习,实现一个延迟队列的 DelayQueue,让使用 Java 的读者既能了解学习数据结构,也能了解到 Java 源码实现。
Java 算法与数据结构
DelayQueue 是一个 BlockingQueue(无界阻塞)队列,它封装了一个使用完全二叉堆排序元素的 PriorityQueue(优先队列)。在添加元素时使用 Delay(延迟时间)作为排序条件,延迟最小的元素会优先放到队首。
二叉堆是一种特殊结构的堆,它的表现形态可以是一棵完整或近似二叉树的结构。如我们本章节要实现的延迟队列中的元素存放,使用的就是 PriorityQueue 实现的平衡二叉堆结构,数据以队列形式存放在基础数组中。
n-1>>>1
相当于除2取整延迟队列的实现,主要为在优先队列的基础上,添加可重入锁 ReentrantLock 对阻塞队列的实现。当数据存放时,按照二叉堆结构排序元素,出队时依照排序结构进行迁移。
二叉堆的在存放元素时,以遵循它的特点,会在存存放过程中,通过队尾元素向上比对迁移。
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
// 获取父节点Idx,相当于除以2
int parent = (k - 1) >>> 1;
logger.info("【入队】寻找当前节点的父节点位置。k:{} parent:{}", k, parent);
Object e = queue[parent];
// 如果当前位置元素,大于父节点元素,则退出循环
if (key.compareTo((E) e) >= 0) {
logger.info("【入队】值比对,父节点:{} 目标节点:{}", JSON.toJSONString(e), JSON.toJSONString(key));
break;
}
// 相反父节点位置大于当前位置元素,则进行替换
logger.info("【入队】替换过程,父子节点位置替换,继续循环。父节点值:{} 存放到位置:{}", JSON.toJSONString(e), k);
queue[k] = e;
k = parent;
}
queue[k] = key;
logger.info("【入队】完成 Idx:{} Val:{} \r\n当前队列:{} \r\n", k, JSON.toJSONString(key), JSON.toJSONString(queue));
}
元素入队过程
单元测试
Queue<Job> queue = new DelayQueue<>();
queue.add(new Job("1号", 1000L));
queue.add(new Job("3号", 3000L));
queue.add(new Job("5号", 5000L));
queue.add(new Job("11号", 11000L));
queue.add(new Job("4号", 4000L));
queue.add(new Job("6号", 6000L));
queue.add(new Job("7号", 7000L));
queue.add(new Job("12号", 12000L));
queue.add(new Job("15号", 15000L));
queue.add(new Job("10号", 10000L));
queue.add(new Job("9号", 9000L));
queue.add(new Job("8号", 8000L));
// 新增入队
queue.add(new Job("2号", 2000L));
测试结果
【入队】元素:{"name":"2号"} 当前队列:[{"name":"1号"},{"name":"3号"},{"name":"5号"},{"name":"11号"},{"name":"4号"},{"name":"6号"},{"name":"7号"},{"name":"12号"},{"name":"15号"},{"name":"10号"},{"name":"9号"},{"name":"8号"},null,null,null,null,null,null,null,null,null,null,null,null]
【入队】寻找当前节点的父节点位置。k:12 parent:5
【入队】替换过程,父子节点位置替换,继续循环。父节点值:{"name":"6号"} 存放到位置:12
【入队】寻找当前节点的父节点位置。k:5 parent:2
【入队】替换过程,父子节点位置替换,继续循环。父节点值:{"name":"5号"} 存放到位置:5
【入队】寻找当前节点的父节点位置。k:2 parent:0
【入队】值比对,父节点:{"name":"1号"} 目标节点:{"name":"2号"}
【入队】完成 Idx:2 Val:{"name":"2号"}
当前队列:[{"name":"1号"},{"name":"3号"},{"name":"2号"},{"name":"11号"},{"name":"4号"},{"name":"5号"},{"name":"7号"},{"name":"12号"},{"name":"15号"},{"name":"10号"},{"name":"9号"},{"name":"8号"},{"name":"6号"},null,null,null,null,null,null,null,null,null,null,null]
元素的出队其实很简单,只要把根元素直接删除弹出即可。但剩余接下里的步骤才是复杂的,因为需要在根元素迁移走后,寻找另外的最小元素迁移到对头。这个过程与入队正好相反,这是一个不断向下迁移的过程。
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) {
logger.info("【出队】左右子节点比对,获取最小值。left:{} right:{}", JSON.toJSONString(c), JSON.toJSONString(queue[right]));
c = queue[child = right];
}
// 目标值与c比较,当目标值小于c值,退出循环。说明此时目标值所在位置适合,迁移完成。
if (key.compareTo((E) c) <= 0) {
break;
}
// 目标值小于c值,位置替换,继续比较
logger.info("【出队】替换过程,节点的值比对。上节点:{} 下节点:{} 位置替换", JSON.toJSONString(queue[k]), JSON.toJSONString(c));
queue[k] = c;
k = child;
}
// 把目标值放到对应位置
logger.info("【出队】替换结果,最终更换位置。Idx:{} Val:{}", k, JSON.toJSONString(key));
queue[k] = key;
}
元素出队过程
这里以弹出元素1举例,之后将队尾元素替换到相应的位置。整个过程分为6张图表述。
单元测试
@Test
public void test_queue() throws InterruptedException {
Queue<Job> queue = new DelayQueue<>();
queue.add(new Job("1号", 1000L));
queue.add(new Job("3号", 3000L));
queue.add(new Job("5号", 5000L));
queue.add(new Job("11号", 11000L));
queue.add(new Job("4号", 4000L));
queue.add(new Job("6号", 6000L));
queue.add(new Job("7号", 7000L));
queue.add(new Job("12号", 12000L));
queue.add(new Job("15号", 15000L));
queue.add(new Job("10号", 10000L));
queue.add(new Job("9号", 9000L));
queue.add(new Job("8号", 8000L));
while (true) {
Job poll = queue.poll();
if (null == poll) {
Thread.sleep(10);
continue;
}
System.out.println(poll.getName());
}
}
测试结果
16:20:26.273 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:{"name":"1号"} 下节点:{"name":"3号"} 位置替换
16:20:26.273 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】左右子节点比对,获取最小值。left:{"name":"11号"} right:{"name":"4号"}
16:20:26.273 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:{"name":"3号"} 下节点:{"name":"4号"} 位置替换
16:20:26.273 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】左右子节点比对,获取最小值。left:{"name":"10号"} right:{"name":"9号"}
16:20:26.273 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:4 Val:{"name":"8号"}
1号
16:20:28.272 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:{"name":"3号"} 下节点:{"name":"4号"} 位置替换
16:20:28.272 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】左右子节点比对,获取最小值。left:{"name":"11号"} right:{"name":"8号"}
16:20:28.272 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】替换过程,节点的值比对。上节点:{"name":"4号"} 下节点:{"name":"8号"} 位置替换
16:20:28.272 [main] INFO cn.bugstack.algorithms.data.queue.PriorityQueue - 【出队】替换结果,最终更换位置。Idx:4 Val:{"name":"9号"}
3号
...
在延迟队列关于元素的操作中,都会进行加锁处理。
offer:——入队元素
public boolean offer(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
q.offer(e);
if (q.peek() == e) {
available.signal();
}
return true;
} finally {
lock.unlock();
}
}
poll:——出队元素
public E poll() {
final ReentrantLock lock = this.lock;
lock.lock();
try {
E first = q.peek();
if (first == null || first.getDelay(NANOSECONDS) > 0) {
return null;
} else {
return q.poll();
}
} finally {
lock.unlock();
}
}
五、常见面试问题
- END -
你好,我是小傅哥。一线互联网java
工程师、T8架构师,开发过交易&营销、写过运营&活动、设计过中间件也倒腾过中继器、IO板卡。不只是写Java语言,也搞过C#、PHP,是一个技术活跃的折腾者。