06、数据结构与算法 - 基础：队列
1、队列的基本概念
队列（queue）是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为**先进先出（FIFO—first in first out）**线性表。
队列的容量可以有限，也可以是无限的。
队列分为：
1、 单向队列（Queue）：只能在一端插入数据，另一端删除数据。
2、 双向队列（Deque）：每一端都可以进行插入数据和删除数据操作。
队列的实现
一、基于数组的Queue实现
一般情况下，对于Queue而言，最核心的操作是：插入队列(enqueue)、移出队列(dequeue)。因为在队列中，插入操作是插入到队列的最后，而移出操作是移出队列的头部元素。因此我们通常会使用两个变量**front（队头指针）和rear（队尾指针）**记录当前元素的位置。
假设我们有一个容量有限队列，用于存放字母，如下图所示：
当我们要插入一个元素时，因为总是插入到队列的最尾部，所以插入的位置是rear+1的位置。
当我们要移出一个元素时，是从队头指针front的位置开始移除(因为Queue头部的元素是最先加入进来的，根据FIFO原则，应该最先移除)。当移除一个元素之后，front应该加1，因为移出一个元素之后，下一个元素就变成了第一个元素。例如现在我们移出了5个元素：
当移出5个元素之后，队头指针就移动到了字母F的位置，前五个位置空下来了。队尾指针rear不变。
现在问题来了：队列头部移出的几个元素，位置空下来了。当我们添加元素的时候，从队尾开始加，当添加到最后一个位置时，怎么办？不让添加时不合理的，毕竟前几个位置已经空下来了。我们的期望是，当一个位置上的元素被移出之后，这个位置是可以被重复使用的。而我们这里讨论的是有限容量的数据，如果我们还继续添加元素，那么就要往队列头部来添加。
这实际上就涉及到了循环队列的概念。也就是当队尾指针到了数组的最后一个下标时，下一个位置应该就是数组的首部。
**因此，当队尾指针指向数组顶端的时候，我们要将队尾指针(rear)重置为-1，此时再加1，就是0，也就是数组顶端例。**如我们又添加了5个字母，那么结果应该如下图：
java 基于数组实现Queue
public class MyQueue {
private Object[] queArray;
//队列总大小
private int maxSize;
//前端
private int front;
//后端
private int rear;
//队列中元素的实际数目
private int nItems;
public MyQueue(int s){
maxSize = s;
queArray = new Object[maxSize];
front = 0;
rear = -1;
nItems = 0;
}
//队列中新增数据
public void insert(int value){
if(isFull()){
System.out.println("队列已满！！！");
}else{
//如果队列尾部指向顶了，那么循环回来，执行队列的第一个元素
if(rear == maxSize -1){
rear = -1;
}
//队尾指针加1，然后在队尾指针处插入新的数据
queArray[++rear] = value;
nItems++;
}
}
//移除数据
public Object remove(){
Object removeValue = null ;
if(!isEmpty()){
removeValue = queArray[front];
queArray[front] = null;
front++;
if(front == maxSize){
front = 0;
}
nItems--;
return removeValue;
}
return removeValue;
}
//查看对头数据
public Object peekFront(){
return queArray[front];
}
//判断队列是否满了
public boolean isFull(){
return (nItems == maxSize);
}
//判断队列是否为空
public boolean isEmpty(){
return (nItems ==0);
}
//返回队列的大小
public int getSize(){
return nItems;
}
}
java中的队列Queue
典型代表：
ConcurrentLinkedQueue：
- ConcurrentLinkedQueue是由链表结构组成的线程安全的先进先出无界队列。
- 当多线程要共享访问集合时，ConcurrentLinkedQueue是一个比较好的选择。
- 不允许插入null元素
- 支持非阻塞地访问并发安全的队列，不会抛出ConcurrentModifiationException异常。
java中的双端队列(Deque)
Deque继承自Queue接口，也可以作为单端队列使用
典型代表：LinkedList
使用双端队列Deque实现栈的功能
java已经废弃了类Stack, 使用Deque定义了LIFO（后进先出）的栈操作
阻塞队列(BlockingQueue)
阻塞队列特点:
阻塞队列的特点就在于阻塞，它可以阻塞线程，让生产者消费者得以平衡，阻塞队列中有两个关键方法 Put 和 Take 方法
Take : 方法的功能是获取并移除队列的头结点，通常在队列里有数据的时候是可以正常移除的。可是一旦执行 take 方法的时候，队列里无数据，则阻塞，直到队列里有数据。一旦队列里有数据了，就会立刻解除阻塞状态，并且取到数据。
**Put:**方法插入元素时，如果队列没有满，那就和普通的插入一样是正常的插入，但是如果队列已满，那么就无法继续插入，则阻塞，直到队列里有了空闲空间。如果后续队列有了空闲空间，比如消费者消费了一个元素，那么此时队列就会解除阻塞状态，并把需要添加的数据添加到队列中。
常见的阻塞队列成员:
1、ArrayBlockingQueue: 数组结构的有界阻塞队列，此队列按照先进先出(FIFO)原则对元素进行排序，同时支持公平锁和非公平锁。它的线程安全性由 ReentrantLock 来实现的。
public ArrayBlockingQueue(int capacity) {...}
public ArrayBlockingQueue(int capacity, boolean fair) {...}
- 如上所示，ArrayBlockingQueue 提供的构造函数中，我们需要指定队列的长度，同时我们也可以设置队列是都是公平的，当我们设置了容量后就不能再修改了，符合数组的特性，此队列按照先进先出（FIFO）的原则对元素进行排序。
- 和 ReentrantLock 一样，如果 ArrayBlockingQueue 被设置为非公平的，那么就存在插队的可能；如果设置为公平的，那么等待了最长时间的线程会被优先处理，其他线程不允许插队，不过这样的公平策略同时会带来一定的性能损耗，因为非公平的吞吐量通常会高于公平的情况。
2、LinkedBlockingQueue: 链表结构的有界阻塞队列，队列的默认大小为 Integer.MAX_VALUE，这个值是非常大的，几乎无法达到，对此我们可以认为这个队列基本属于一个无界队列（也又认为是有界 队列）也是按照先进先出原则对元素进行排序的。它的线程安全性由 ReentrantLock 来实现的。
3、PriorityBlockingQueue: 支持线程优先级排序的无界阻塞队列。默认自然序进行排序，也可以自定义实现compareTo()方法来指定元素排序规则，不能保证同优先级元素的顺序。
4、DelayQueue: 实现PriorityBlockingQueue优先级排序的延迟阻塞队列，在创建元素时，可以指定多久才能从队列中获取当前元素。只有延时期满后才能从队列中获取元素。
5、SynchronousQueue: 不存储元素的阻塞队列，每一个put操作必须等待take操作，否则不能添加元素。支持公平锁和非公平锁。
6、LinkedBlockingDeque： 一个由链表结构组成的双向阻塞队列。队列头部和尾部都可以添加和移除元素，多线程并发时，可以将锁的竞争最多降到一半。
这些阻塞队列的实现类是都是实现了BlockingQueue接口