死磕Java队列

Rothschil 2020-05-18 15:53:00
多线程,Java,Queue,队列

1. 概念

队列是在JDK1.5中被引入,它是一种数据结构,遵循原则就是 “FIFO”,即”先进先出”。

Queue接口与List同一级别,继承自Collection接口,LinkedList实现了Deque接 口。

类继承图

2. 分类

队列在实际应用有很多分类,如是否阻塞、是否线程安全、是否有界。这里也仅从这三块来加以区分。

类名 是否阻塞 是否线程安全 是否有界 特点
LinkedList 非阻塞 线程安全 有界 基于链表
ArrayBlockingQueue 阻塞 线程安全 有界 基于数组的有界队列
LinkedBlockingQueue 阻塞 线程安全 可选有界 基于链表的无界队列
ConcurrentLinkedQueue 非阻塞 线程安全 无界 基于链表 线程安全的队列
PriorityBlockingQueue 阻塞 线程安全 无界 基于优先次序的无界队列
PriorityQueue 非阻塞 非线程安全 无界
SynchronousQueue 阻塞 线程安全 无数据队列 内部没有容器的队列 较特别
LinkedBlockingDeque 阻塞 线程安全 无界
DelayQueue 阻塞 线程安全 无界 基于时间优先级的队列

2.1. 队列容量

从队列的大小以及容量来说,分为 有界队列无界队列

2.2. 阻塞

从阻塞特征来说,分为 阻塞队列非阻塞队列

2.3. 线程安全

从线程安全来说,分为 线程安全非线程安全

2.4. LinkedList

2.4.1. 适用场景

通常适用与插入元素和删除元素,时间的复杂度O(1)。它性能高效的原理是通过链表实现,插入和删除只需要改变前后两个节点指针指向即可。

2.4.2. 构造函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* Constructs an empty list.
*/
public LinkedList() {
}

/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}

2.4.3. 常用方法

方法名 描述
element 检索但不删除此列表的头(第一个元素)
getFirst 返回此列表中的第一个元素
getLast 返回此列表中的最后一个元素
offer 将指定的元素添加为此列表的尾部
poll 检索并删除此列表的头(第一个元素)
pop 从此列表表示的堆栈中弹出一个元素,换句话说,删除并返回此列表的第一个元素
peek 检索但不删除此列表的头(第一个元素)

2.4.4. 样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
initQueue(queue);
for(String q : queue){
System.out.print(q+"\t");
}
System.out.print("\n");
System.out.println(" 队列中头信息element: "+queue.element());
System.out.println(" 获取信息poll: " + queue.poll());
System.out.println(" 队列中头信息element: "+queue.element());
System.out.println(" ============ ");
System.out.println(" 队列中头信息peek: "+queue.peek());

for(String q : queue){
System.out.print(q+"\t");
}
System.out.print("\n");
}

/** 初始化队列中的数据
* @Description
* @param queue
* @return void
* @throws
* @date 2020/8/5 15:12
*/
public static void initQueue(Queue<String> queue){
queue.offer("Q1");
queue.offer("Q2");
queue.offer("Q3");
queue.offer("Q4");
queue.offer("Q5");
}

2.5. CoucurrentLinkedQueue

同步队列,无界

3. 阻塞队列

java.util.concurrent 包中加入 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素,线程执行操作阻塞,直到有空间或者元素可用

3.1. ArrayBlockingQueue

有界

3.2. LinkedBlockingQueue

无界

3.3. 优先级阻塞队列PriorityBlockingQueue

每次调用take方法获取元素的时候将优先级最高的返回出来!

3.4. 延迟阻塞队列DelayQueue

3.5. SynchronousQueue

容器中不支持直接加元素,需要take线程与add线程阻塞集合

3.6. 阻塞队列BlockingQueue

3.6.1. ArrayBlockingQueue

有界

3.6.2. LinkedBlockingQueue

无界

3.6.3. SynchronousQueue

容器中不支持直接加元素,需要take线程与add线程阻塞集合

3.6.4. 优先级阻塞队列PriorityBlockingQueue

每次调用take方法获取元素的时候将优先级最高的返回出来!

3.6.5. 延迟阻塞队列DelayQueue