队列在有限资源池中的应用

1. 什么是队列?

队列的特点是先进先出,有两个基本操作:入队(enqueue),放一个数据到队列尾部;出队(dequeue),从队列头部取一个元素。。它和栈一样,也是一种操作受限的线形表数据结构。

队列的应用非常广泛,特别是一些具有某些额外特性的队列,比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性的作用。

队列

2. 如何实现队列?

跟栈一样,队列可以用数组来实现,也可以用链表来实现。用数组实现的队列叫作顺序队列,用链表实现的队列叫作链式队列

使用数组实现的队列:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
public class QueueByArray<E> {
private int size;
private E[] data;
private int head;
private int tail;

public QueueByArray() {
this(8);
}

public QueueByArray(int size) {
data = (E[]) new Object[size];
this.size = size;
}

/**
* 入队
*
* @param element
* @return
*/
public boolean enqueue(E element) {
// 队尾没有空间
if (tail == size) {
// 队列已满
if (head == 0) {
return false;
}
System.out.println("move element, head " + head + ", tail " + tail);
// 移动元素,从尾部向首部搬移
for (int i = head; i < tail; i++) {
data[i - head] = data[i];
}
tail -= head;
head = 0;
}
data[tail++] = element;
return true;
}

/**
* 出队
*
* @return
*/
public E dequeue() {
// 队列为空
if (head == tail) {
return null;
}
return data[head++];
}
}

使用链表实现的队列:

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
34
35
36
37
38
39
40
41
42
43
44
public class QueueByLink<E> {
private int size;
private Node head;
private Node tail;

/**
* 入队
*
* @param element
*/
public void enqueue(E element) {
if (head == null) {
head = new Node();
head.element = element;
tail = head;
} else {
Node node = new Node();
node.element = element;
tail.next = node;
tail = node;
}
size++;
}

/**
* 出队
*
* @return
*/
public E dequeue() {
if (head == null) {
return null;
}
E element = head.element;
head = head.next;
size--;
return element;
}

private class Node {
private E element;
private Node next;
}
}

3. 循环队列

循环队列像一个环,首尾相连,避免了数据移动。实现循环队列的关键是,确定好队空和队满的判定条件。当队满时,(tail+1)%n=head

下面是使用数组实现循环队列:

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
public class CircularQueue<E> {
// 容量
private int size;
private E[] data;
private int head;
private int tail;

public CircularQueue() {
this(8);
}

public CircularQueue(int size) {
data = (E[]) new Object[size];
this.size = size;
}

/**
* 入队
*
* @param element
* @return
*/
public boolean enqueue(E element) {
// 队列已满
if ((tail + 1) % size == head) {
return false;
}
data[tail] = element;
tail = (tail + 1) % size;
return true;
}

/**
* 出队
*
* @return
*/
public E dequeue() {
// 队列为空
if (head == tail) {
return null;
}
E ele = data[head];
head = (head + 1) % size;
return ele;
}
}

4. 阻塞队列和并发队列

阻塞队列就是在队列基础上增加了阻塞操作。简单来说,就是在队列为空的时候,从队头取数据会被阻塞。直到队列中有了数据才能返回;如果队列已经满了,那么插入数据就会被阻塞,直到队列中有空闲位置后再插入数据,然后再返回。这种基于阻塞队列实现的“生产者 - 消费者模型”,可以有效地协调生产和消费的速度。

线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在 enqueue()、dequeue() 方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或者取操作。实际上,基于数组的循环队列,利用 CAS 原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

线程池的阻塞队列分为两种:基于链表的实现方式,可以实现一个支持无限排队的无界队列,但是可能会导致过多的请求排队等待,请求处理的响应时间过长。而基于数组实现的有界队列,队列的大小有限,所以线程池中排队的请求超过队列大小时,接下来的请求就会被拒绝,设置一个合理的队列大小非常有讲究。

课后思考

还有哪些类似线程池结构或者场景中会用到队列的排队请求呢?

本文标题:队列在有限资源池中的应用

文章作者:落英坠露

发布时间:2019年04月26日 - 22:04

最后更新:2019年04月26日 - 22:04

原始链接:https://isuperqiang.cn/2019/04/26/队列在有限资源池中的应用/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

赞赏是一种行为艺术