1. 什么是队列？
队列的特点是先进先出，有两个基本操作：入队（enqueue），放一个数据到队列尾部；出队（dequeue），从队列头部取一个元素。。它和栈一样，也是一种操作受限的线形表数据结构。
队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。
队列
2. 如何实现队列？
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列。
使用数组实现的队列：
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++];
}
}
使用链表实现的队列：
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。
下面是使用数组实现循环队列：
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 原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
线程池的阻塞队列分为两种：基于链表的实现方式，可以实现一个支持无限排队的无界队列，但是可能会导致过多的请求排队等待，请求处理的响应时间过长。而基于数组实现的有界队列，队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，设置一个合理的队列大小非常有讲究。
课后思考
还有哪些类似线程池结构或者场景中会用到队列的排队请求呢？
网友评论