beauty of algorithms 9 summary. queue

队列的概念

  • 先进者先出
  • 支持两个操作:入队 enqueue(),放一个数据到队尾;出队 dequeue(),从队头取一个元素。
  • 队列也是一种操作受限的线性表

    数组实现 ( 顺序队列 )

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
public class  {
private String[] items;
private int n = 0;
private int head = 0;
private int tail = 0;

public (int n) {
items = new String[n];
this.n = n;
}

public void enqueue(String item) throws Exception {
if (tail == n) {
throw new Exception("queue is full , cant enter any more !");
}
items[tail] = item;
tail++;
}

public String dequeue() throws Exception {
if (head == tail) {
throw new Exception("queue is empty !");
}
String ret = items[head];
head++;
return ret;
}

public void printQueue() {
for (int i = head; i < tail; i++) {
System.out.print(items[i] + " ");
}
}

public static void main(String[] args) throws Exception {
ArrayQueue arrayQueue = new ArrayQueue(10);
arrayQueue.enqueue("1");
arrayQueue.enqueue("2");
arrayQueue.enqueue("3");
arrayQueue.enqueue("4");
arrayQueue.enqueue("4");

arrayQueue.printQueue();
System.out.println(" ");
System.out.println("***************************");
System.out.println(arrayQueue.dequeue());
System.out.println("***************************");

arrayQueue.printQueue();
}

}
假溢出

以上代码中的出队入队会造成假溢出现象,即随着不断的出队,head在增加,head前面的数组空间是被空着的。

修改入队方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void enqueue2(String item) throws Exception {
if (tail == n) {
if (head == 0) {
throw new Exception("queue is full , cant enter any more !");
}
for (int i = head; i < tail; i++) {
items[i - head] = items[i];
}
tail -= head;
head = 0;
}
items[tail] = item;
tail++;
}

链表实现

链表无需考虑溢出

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
54
55
56
57
58
59
60
61
62
63
public class SingleLinkQueue<T> {
private class Node<T> {
private T data;
private Node<T> next;

public Node(T data, Node<T> next) {
this.data = data;
this.next = next;
}
}

private Node<T> tail;
private Node<T> head;
private int size;

public SingleLinkQueue() {
head = tail = null;
}

public void enqueue(T item) {
Node<T> node = new Node<T>(item, null);
if (head == null) {
head = node;
tail = node;
}

tail.next = node;
tail = node;
size++;
}

public T dequeue() throws Exception {
if (head == null) {
throw new Exception("Queue is empty, no element to dequeue !");
}
T ret = head.data;
head = head.next;
size--;
return ret;
}

public void printQueue(){
Node<T> tem = head;
while (tem!= null){
System.out.print(tem.data + " ");
tem = tem.next;
}
}

public static void main(String[] args) throws Exception {
SingleLinkQueue<String> singleLinkQueue = new SingleLinkQueue<>();
singleLinkQueue.enqueue("1");
singleLinkQueue.enqueue("2");
singleLinkQueue.enqueue("3");
singleLinkQueue.enqueue("4");
singleLinkQueue.printQueue();
System.out.println("n***************************");
System.out.println(singleLinkQueue.dequeue());
System.out.println("***************************");
singleLinkQueue.printQueue();
}

}

循环队列 ( 基于数组 )

循环队列可以实现不进行数据搬移而解决假溢出现象。

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
public class CircularQueue {
private String[] items;
int n = 0;
int head = 0;
int tail = 0;

public CircularQueue(int n) {
this.n = n;
items = new String[n];
}

public void enqueue(String item) throws Exception {
if ((tail + 1) % n == head) {
throw new Exception("queue is full ,cant enqueue any more items !");
}
items[tail] = item;
tail = (tail + 1) % n;
}

public String dequeue() throws Exception {
if (tail == head) {
throw new Exception("queue is empty !");
}
String ret = items[head];
head = (head + 1) % n;
return ret;
}

public void printQueue() {
for (int i = head; i % n != tail; i++) {
System.out.print(items[i] + " ");
}
}

public static void main(String[] args) throws Exception {
CircularQueue circularQueue = new CircularQueue(10);
circularQueue.enqueue("1");
circularQueue.enqueue("2");
circularQueue.enqueue("3");
circularQueue.enqueue("4");
circularQueue.enqueue("4");

circularQueue.printQueue();
System.out.println(" ");
System.out.println("***************************");
System.out.println(circularQueue.dequeue());
System.out.println("***************************");

circularQueue.printQueue();
}

}

队列的常见应用

阻塞队列

  • 在队列的基础上增加阻塞操作,就成了阻塞队列。

  • 阻塞队列就是在队列为空的时候,从队头取数据会被阻塞,因为此时还没有数据可取,直到队列中有了数据才能返回;

    如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后在返回。

  • 从上面的定义可以看出这就是一个“生产者-消费者模型”。

    这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。

    当“生产者”生产数据的速度过快,“消费者”来不及消费时,存储数据的队列很快就会满了,

    这时生产者就阻塞等待,直到“消费者”消费了数据,“生产者”才会被唤醒继续生产。

    不仅如此,基于阻塞队列,我们还可以通过协调“生产者”和“消费者”的个数,来提高数据处理效率,

    比如配置几个消费者,来应对一个生产者。

并发队列

  • 在多线程的情况下,会有多个线程同时操作队列,这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
  • 并发队列简单的实现就是在enqueue()、dequeue()方法上加锁,但是锁粒度大并发度会比较低,同一时刻仅允许一个存或取操作
  • 实际上,基于数组的循环队列利用CAS原子操作,可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。

线程池资源枯竭时的处理

在资源有限的场景,当没有空闲资源时,基本上都可以通过“队列”这种数据结构来实现请求排队。

思考

如何实现无锁的并发队列?