一、什么是队列？
1.先进先出（FIFO）
2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。
3.栈一样，队列也是一种操作受限的线性表。
二、如何实现队列？
队列API
public interface Queue<T> {
public void enqueue(T item); //入队
public T dequeue(); //出队
public int size(); //统计元素数量
public boolean isNull(); //是否为空
public boolean isFull(); //是否已满
}
实现方法
1.数组实现
2.链表实现
三、队列的分类
顺序队列
基于数组实现的顺序的队列
时间复杂度
入队：O(1)
出队：O(n) 因为要后续元素移动数据
循环队列
可以解决假溢出的问题，但是操作更加复杂，需要区分队列满和队列空的情况，因为这个时候队头和队尾坐标一样。
时间复杂度
入队：O(1)
出队：O(1)
若是用链表实现，就无上面问题，且入出队列时间复杂度都是O(1);但是数组实现在并发队列有应用。
四、队列的应用
阻塞队列
1.可以队列的基础上增加阻塞操作，就成了阻塞队列。
2.阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
阻塞队列的操作方法
抛出异常 返回特殊值 一直阻塞 超时退出
插入方法 add（e） offer(e) put(e) offer(e,time,unit)
移除方法 remove() poll() take() poll(time,unit)
检查方法 element() peek()
JDK提供的阻塞队列有
ArrayBlockingQueue: 数组结构组成的有界阻塞队列,需要初始化队列的容量，初始化后容量不能修改。FIFO
LinkedBlockingQueue: 链表结构组成的有界（无界的是MAX.INTEGER）阻塞队列，FIFO
PriorityBlockingQueue: 支持优先级排序的无界阻塞队列 ，有扩容机制
DelayQueue: 使用优先级队列实现的无界阻塞可延迟队列
SysnchronousQueue: 一个元素的阻塞队列，单个元素
LinkedTransferQueue: 一个由链表组成的无界阻塞队列
LinkedBlockingDeque: 一个由链表组成的双向阻塞队列
被阻塞的情况主要有如下两种
当队列满了的时候进行入队列操作
当队列空了的时候进行出队列操作
并发队列
1.在多线程的情况下，会有多个线程同时操作队列，会存在线程安全问题；这时需要使用并发队列。
2.简单实现就是在入、出方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
3.高效的并发队列基于数组的循环队列利用CAS原子操作。
3.线程池的使用的场景
JDK提供了两套实现
1.以ConcurrentLinkedQueue为代表的高性能队列非阻塞队列
2.以BlockingQueue接口为代表的阻塞队列，无论哪种都继承自Queue
ConcurrentLinkedDeque 非阻塞式队列
无界线程安全队列
先进先出的原则
不允许null元素
add() 和 offer() 都是加入元素的方法
poll() 和 peek() 都是取头元素节点，区别在于前者会删除元素，后者不会
网友评论