队列(Queue):与栈相对性的一种算法设计, 结合(Collection)的一个派生类。队列容许在一端开展插进实际操作,而在另一端开展移除使用的线性表,栈的特性是后进先出,而队列的特点是先进先出法。队列的用途非常大,例如完成信息队列。Queue 类关系图,如下图所示:
注:为了更好地让大家更直接地了解,图中为精简的 Queue 类关系图。文中如无特别表明,內容是根据 Java 1.8 版本号。
队列(Queue)
1)Queue 归类
从图中可以看得出 Queue 大致可分成下列三类。
- 二端队列:双端队列(Deque)是 Queue 的派生类也是 Queue 的填补类,头顶部和尾端都适用元素插进和获得。
- 堵塞队列:阻塞队列指的是在元素实际操作时(加上或删掉),要是没有取得成功,会堵塞等候实行。例如,当加上元素时,假如队列元素已满,队列会堵塞等候直到有位置时再插进。
- 非堵塞队列:非阻塞队列和堵塞队列反过来,会立即返回实际操作的結果,并非堵塞等候。二端队列也是非堵塞队列。
2)Queue 方式表明
Queue 常见方式,如下图所示:
方法表明:
- add(E):加上元素到队列尾端,取得成功返回 true,队列超过时抛出异常;
- offer(E):加上元素到队列尾端,取得成功返回 true,队列超过时返回 false;
- remove():删掉元素,取得成功返回 true,不成功返回 false;
- poll():获得并清除此队列的第一个元素,若队列为空,则返回 null;
- peek():获得但不清除此队列的第一个元素,若队列为空,则返回 null;
- element():获得但不清除此队列的第一个元素,若队列为空,则抛出现异常。
3)Queue 应用案例
Queue<String> linkedList = new LinkedList<>();
linkedList.add(\"Dog\");
linkedList.add(\"Camel\");
linkedList.add(\"Cat\");
while (!linkedList.isEmpty()) {
System.out.println(linkedList.poll());
}
程序运行結果:
Dog
Camel
Cat
堵塞队列
1)BlockingQueue
BlockingQueue 在 java.util.concurrent 包下,别的堵塞类都完成自 BlockingQueue 插口,BlockingQueue 给予了线程安全的队列浏览方法,当向队列中插进数据信息时,假如队列已满,进程则会堵塞等候队列中元素被取下后再插进;当从队列中取数据信息时,假如队列为空,则进程会堵塞等候队列中有新元素再获得。BlockingQueue 关键方式插入方法:
- add(E):加上元素到队列尾端,取得成功返回 true,队列超过时抛出异常;
- offer(E):加上元素到队列尾端,取得成功返回 true,队列超过时返回 false ;
- put(E):将元素插进到队列的尾端,假如该队列已满,则一直堵塞。
删掉方式:
- remove(Object):清除特定元素,取得成功返回 true,不成功返回 false;
- poll(): 获得并清除队列的第一个元素,假如队列为空,则返回 null;
- take():获得并清除队列第一个元素,要是没有元素则一直堵塞。
查验方式:
- peek():获得但不清除队列的第一个元素,若队列为空,则返回 null。
2)LinkedBlockingQueue
LinkedBlockingQueue 是一个由单链表完成的有限堵塞队列,容积初始值为 Integer.MAX_VALUE,还可以自定容积,提议特定容积尺寸,默认设置尺寸在加上速率超过删掉速率状况下有导致内存溢出的风险性,LinkedBlockingQueue 是先进先出法的形式储存元素。
3)ArrayBlockingQueue
ArrayBlockingQueue 是一个有界限的堵塞队列,它的里面完成是一个二维数组。它的存储容量是有局限的,大家一定在其复位的情况下特定它的容积尺寸,容积尺寸一旦特定就不能更改。ArrayBlockingQueue 也是先进先出法的形式存放数据信息,ArrayBlockingQueue 内部结构的堵塞队列是根据再入锁 ReenterLock 和 Condition 标准队列完成的,因而 ArrayBlockingQueue 中的元素存有公平公正浏览和非公平公正浏览的差别,针对公平公正浏览队列,被堵塞的进程可以依照堵塞的顺序浏览队列,即先堵塞的进程先浏览队列。并非公平公正队列,当队列可以用时,堵塞的进程将进到角逐浏览資源的市场竞争中,换句话说谁先抢得谁就实行,沒有稳固的顺序。实例编码如下所示:
// 默认设置非公平公正堵塞队列
ArrayBlockingQueue queue = new ArrayBlockingQueue(6);
// 公平公正堵塞队列
ArrayBlockingQueue queue2 = new ArrayBlockingQueue(6,true);
// ArrayBlockingQueue 源代码展现
public ArrayBlockingQueue(int capacity) {
this(capacity, false);
}
public ArrayBlockingQueue(int capacity, boolean fair) {
if (capacity <= 0)
throw new IllegalArgumentException();
this.items = new Object[capacity];
lock = new ReentrantLock(fair);
notEmpty = lock.newCondition();
notFull = lock.newCondition();}
4)DelayQueue
DelayQueue 是一个适用延迟获得元素的无边堵塞队列,队列中的元素务必完成 Delayed 插口,在建立元素时可以特定时间延迟,仅有抵达了延时的时间段以后,才可以得到到该元素。完成了 Delayed 插口务必重新写过2个方式 ,getDelay(TimeUnit) 和 compareTo(Delayed),如下所示编码所显示:
class DelayElement implements Delayed {
@Override // 获得剩下的时间
public long getDelay(TimeUnit unit) {
// do something
}
@Override // 队列里元素的排列根据
public int compareTo(Delayed o) { // do something
}
}
DelayQueue 应用的详细实例,请参照下列编码:
public class DelayTest {
public static void main(String[] args) throws InterruptedException {
DelayQueue delayQueue = new DelayQueue();
delayQueue.put(new DelayElement(1000));
delayQueue.put(new DelayElement(3000));
delayQueue.put(new DelayElement(5000));
System.out.println(\"开始时间:\" DateFormat.getDateTimeInstance().format(new Date()));
while (!delayQueue.isEmpty()){
System.out.println(delayQueue.take());
}
System.out.println(\"完毕時间:\" DateFormat.getDateTimeInstance().format(new Date()));
}
static class DelayElement implements Delayed { // 延迟时间截止时间(单层:ms)
long delayTime = System.currentTimeMillis();
public DelayElement(long delayTime) {
this.delayTime = (this.delayTime delayTime);
}
@Override // 获得剩下的时间
public long getDelay(TimeUnit unit) {
return unit.convert(delayTime - System.currentTimeMillis(), TimeUnit.MILLISECONDS);
}
@Override // 队列里元素的排列根据
public int compareTo(Delayed o) {
if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) {
return 1;
} else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) {
return -1;
} else {
return 0;
}
}
@Override
public String toString() {
return DateFormat.getDateTimeInstance().format(new Date(delayTime));
}
}
}
程序运行結果:
开始时间:2019-6-13 20:40:38 2019-6-13 20:40:39 2019-6-13 20:40:41 2019-6-13 20:40:43 完毕時间:2019-6-13 20:40:43
非阻塞队列
ConcurrentLinkedQueue 是一个根据连接连接点的无边线程安全序列,它选用先进先出法的标准对连接点开展排列,在我们加上一个原素的情况下,它会加上到序列的尾端;在我们获得一个因素时,它会回到序列头顶部的原素。它的入队和出队实际操作均运用 CAS(Compare And Set)升级,那样容许好几个进程高并发实行,而且并不会由于上锁而堵塞进程,促使高并发特性更强。ConcurrentLinkedQueue 应用实例:
ConcurrentLinkedQueue concurrentLinkedQueue = new ConcurrentLinkedQueue();
concurrentLinkedQueue.add(\"Dog\");
concurrentLinkedQueue.add(\"Cat\");
while (!concurrentLinkedQueue.isEmpty()) {
System.out.println(concurrentLinkedQueue.poll());
}
实行結果:
Dog
Cat
可以看得出无论是阻塞队列还是是非非阻塞队列,操作方法全是相近的,差别是最底层的建立方法。
优先级队列
PriorityQueue 一个根据优先堆的无边优先级队列。优先级队列的原素依照其当然次序开展排列,或是依据结构序列时给予的 Comparator 开展排列,实际在于所采用的构造函数。优先级队列不允许应用 null 原素。PriorityQueue 编码应用实例:
Queue<Integer> priorityQueue = new PriorityQueue(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// 非自然排列,数据倒序 return o2 - o1; }});priorityQueue.add(3);priorityQueue.add(1);priorityQueue.add(2);while (!priorityQueue.isEmpty()) { Integer i = priorityQueue.poll(); System.out.println(i);}
程序运行的結果是:
3
2
1
PriorityQueue 留意的点:
- PriorityQueue 是是非非线程安全的,在线程同步状况下可应用 PriorityBlockingQueue 类取代;
- PriorityQueue 不允许插进 null 原素。
有关面试问题
1.ArrayBlockingQueue 和 LinkedBlockingQueue 的差异是啥?
答:ArrayBlockingQueue 和 LinkedBlockingQueue 都完成自阻塞队列 BlockingQueue,他们的差异具体反映在下述一些层面:
- ArrayBlockingQueue 应用时务必特定容积值,LinkedBlockingQueue 可以无需特定;
- ArrayBlockingQueue 的最高容积值是应用时特定的,而且特定以后就不允许改动;而 LinkedBlockingQueue 较大的容积为 Integer.MAX_VALUE;
- ArrayBlockingQueue 数据储存器皿是选用二维数组储存的;而 LinkedBlockingQueue 选用的是 Node 连接点存放的。
2.LinkedList 中 add() 和 offer() 有什么关系?
答:add() 和 offer() 全是加上原素到序列尾端。offer 方式是根据 add 方式完成的,Offer 的源代码如下所示:
public boolean offer(E e) { return add(e);}
3.Queue 和 Deque 有什么不同?
答:Queue 归属于一般序列,Deque 归属于双端队列。一般序列是先进先出法,也就是仅有优秀的才可以先出;而双端队列则是两边都能插进和删掉原素。
4.LinkedList 归属于一般序列或是双端队列?
答:LinkedList 完成了 Deque 归属于双端队列,因而有着 addFirst(E)、addLast(E)、getFirst()、getLast() 等方式。
5.下列表述不正确的是?
A:DelayQueue 内部结构是根据 PriorityQueue 完成的 B:PriorityBlockingQueue 并不是先进先出法的数据存储方式 C:LinkedBlockingQueue 容积是无穷大的 D:ArrayBlockingQueue 内部结构的数据存储器是二维数组,复位时务必特定序列容积 答:C 题型分析:LinkedBlockingQueue 默认设置容积是 Integer.MAX_VALUE,并并不是无穷大的,源代码如下图所示:
6.有关 ArrayBlockingQueue 观点不正确的是?
A:ArrayBlockingQueue 是线程安全的 B:ArrayBlockingQueue 原素容许为 null C:ArrayBlockingQueue 关键应用领域是“经营者-顾客”实体模型 D:ArrayBlockingQueue 务必表明地设定容积 答:B 题型分析:ArrayBlockingQueue 不允许原素为 null,假如加上一个 null 原素,会抛 NullPointerException 出现异常。
7.下列程序运行的结论是啥?
PriorityQueue priorityQueue = new PriorityQueue();priorityQueue.add(null);
System.out.println(priorityQueue.size());
答:程序运行出错,PriorityQueue 不可以插进 null。
8.Java 中多见的阻塞队列有什么?
答:Java 中多见的阻塞队列如下所示:
- ArrayBlockingQueue,由二维数组构造构成的有限阻塞队列;
- PriorityBlockingQueue,适用优先级排序的无边阻塞队列;
- SynchronousQueue,是一个不储存原素的阻塞队列,会立即将每日任务交到顾客,务必等序列中的增加原素被交易后能够再次加上新的原素;
- LinkedBlockingQueue,由单链表构造构成的阻塞队列;
- DelayQueue,适用延迟获得要素的无边阻塞队列。
9.有限序列和无边序列有什么差别?
答:有限序列和无边序列的差别如下所示:
- 有限序列:有固定不动尺寸的序列称为有限序列,例如:new ArrayBlockingQueue(6),6 便是序列的尺寸。
- 无边序列:指的是沒有设定固定不动尺寸的序列,这种序列的特性是可以立即入役,直到外溢。他们并没有确实无边,他们最高值通常为 Integer.MAXVALUE,仅仅平时非常少能使用这么大的容积(超出 Integer.MAXVALUE),因而从用户的感受上,就等同于 “无边”。
10.怎样手动式完成一个延迟时间线程池?
答:说到延迟时间线程池,大家应当可以第一时间想起要应用 DelayQueue 延迟时间序列来处理这个问题。完成构思,线程池分成经营者和顾客,经营者用以提升信息,顾客用以获得并交易信息,大家只必须经营者把信息放进到 DelayQueue 序列并设定时间延迟,顾客循环系统应用 take() 堵塞获得信息就可以。详细的建立源代码如下所示:
public class CustomDelayQueue { // 信息序号
static AtomicInteger MESSAGENO = new AtomicInteger(1);
public static void main(String[] args) throws InterruptedException {
DelayQueue<DelayedElement> delayQueue = new DelayQueue<>(); // 经营者1
producer(delayQueue, \"生产者1\"); // 经营者2
producer(delayQueue, \"生产者2\"); // 顾客
consumer(delayQueue); } //生产者
private static void producer(DelayQueue<DelayedElement> delayQueue, String name) {
new Thread(new Runnable() {
@Override
public void run() {
while (true) { // 造成 1~5 秒的随机数字
long time = 1000L * (new Random().nextInt(5) 1);
try {
Thread.sleep(time);
} catch (InterruptedException e) {
e.printStackTrace();
} // 组成信息体
String message = String.format(\"%s,消息序号:%s 推送時间:%s 延迟时间:%s 秒\", name, MESSAGENO.getAndIncrement(), DateFormat.getDateTimeInstance().format(new Date()), time / 1000); // 生产制造信息
delayQueue.put(new DelayedElement(message, time));
}
}
}).start();
} //顾客
private static void consumer(DelayQueue<DelayedElement> delayQueue) {
new Thread(new Runnable() {
@Override
public void run() {
while (true) {
DelayedElement element = null;
try { // 交易信息
element = delayQueue.take();
System.out.println(element);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
}
}).start(); }
// 延迟时间序列目标
static class DelayedElement implements Delayed {
// 到期時间(企业:ms)
long time = System.currentTimeMillis();
// 信息体
String message;
// 主要参数:delayTime 时间延迟(企业ms)
public DelayedElement(String message, long delayTime) {
this.time = delayTime;
this.message = message;
}
@Override
// 获得到期時间 public long getDelay(TimeUnit unit) { return unit.convert(time - System.currentTimeMillis(), TimeUnit.MILLISECONDS); } @Override // 序列原素排列 public int compareTo(Delayed o) { if (this.getDelay(TimeUnit.MILLISECONDS) > o.getDelay(TimeUnit.MILLISECONDS)) return 1; else if (this.getDelay(TimeUnit.MILLISECONDS) < o.getDelay(TimeUnit.MILLISECONDS)) return -1; else return 0; } @Override public String toString() { // 打印消息 return message \" |实行時间:\" DateFormat.getDateTimeInstance().format(new Date()); } }}
以上程序流程适用多生产者,实行的結果如下所示:
生产者1,信息序号:1 推送時间:2019-6-12 20:38:37 延迟时间:2 秒 |实行時间:2019-6-12 20:38:39 生产者2,信息序号:2 推送時间:2019-6-12 20:38:37 延迟时间:2 秒 |实行時间:2019-6-12 20:38:39 生产者1,信息序号:3 推送時间:2019-6-12 20:38:41 延迟时间:4 秒 |实行時间:2019-6-12 20:38:45 生产者1,信息序号:5 推送時间:2019-6-12 20:38:43 延迟时间:2 秒 |实行時间:2019-6-12 20:38:45 ……
汇总
序列(Queue)依照是不是堵塞可分成:阻塞队列 BlockingQueue 和 非阻塞队列。在其中,双端队列 Deque 也是非阻塞队列,双端队列除开有着序列的先进先出法的方式以外,还具有自身特有的方式,如 addFirst()、addLast()、getFirst()、getLast() 等,适用首未插进和删掉原素。序列中较为常见的2个序列也有 PriorityQueue(优先级队列)和 DelayQueue(延迟时间序列),可应用延迟时间序列来完成延迟时间线程池,这也是招聘面试中较为常见的问题之一。必须招聘面试好朋友对延迟时间序列一定要保证心里有数,动手能力写一个线程池也是十分需要的。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。