队列
队列是一种非常常见的数据结构。具体说是操作操作受限的线性表数据结构。队列经常会与栈一起提到，两者是非常相似的，只不过他们的操作受限不同。 队列的受限是先进先出。而栈是先进后出。举个例子，队列就是买票排队，先排队先买票。而栈就是大枪的压子弹，先压进来的子弹最后发射出去。
队列分类
队列从数据结构的实现上讲又分为顺序队列和链表队列。顺序队列是使用数组实现，而链表队列是使用链表实现。
从队列的特定分类的话，有循环队列、阻塞队列、并发队列等。
队列和线程池的关系
CPU的资源是有限的，任务的处理速度与线程的个数并不是线性正相关，而是类似于正太分布关系。有一个顶峰最大值，当线程个数超过那个值时，任务的处理速度会因为cpu切换线程而降低。所以线程池的大小要根据硬件的具体条件来设置。当我们设置了固定大小的线程池后，如果池中没有了多余的资源，这个时候线程池如何处理请求？策略是如何实现的？
这种情况一般有两种处理方法，第一种如果没有多余资源可以直接拒绝请求，第二种就是排队等候，当有了资源的时候再去处理。这个时候我们希望排队等候存在公平性，可以先进者先服务，这个策略就可以使用队列去实现。队列又有两种两种实现方式：数组和链表。两者又有什么区别呢？
数组 -> 数组实现的队列是有界的，他对于响应时间敏感的系统是非常友好的，当超过队列的时候拒绝了请求。合理的设置队列的大小，是非常有效的。
链表 -> 链表实现的队列是无界的，他的请求可以无限多，但是可能会耗费很长的时间。
两者要根据实际情况来考虑，说一种开发中遇到的问题，采用的线程是使用链表实现的，然后线程一直没有被释放，然后任务队列一直在重新创建最终导致了系统挂掉了，如果采用的是数组实现的，那么虽然新的请求也不能被处理，但是不会导致系统挂掉，也可以找到那个没有释放的线程，强制停止掉，线上就可以恢复正常了。
还有就是循环队列、阻塞队列、和并发队列他们的实现也是使用数组和链表，只不过加上了特殊的限制。阻塞队列就是可以设置进队和出队可以阻塞，并发队列可以确保线程安全。
数组实现队列
/**
* @author caopengflying
* @time 2019/2/18 14:04
* 手动实现数组队列
*/
public class CPFArrayQueue {
private int[] datas; //数据区域
private int tail = 0; //尾部指针
private int head = 0; //头部指针
private int size = 0;
/**
* 初始构造数据存储区域的大小
*
* @param size
*/
public CPFArrayQueue(int size) {
this.datas = new int[size];
}
/**
* 进队列
*
* @param data 将要进队列的数据
* @return
*/
public boolean enQueue(int data) {
if (isFull()) {
System.out.println("该队列已满，请出队后重试！");
return false;
}
if (this.datas.length == this.tail && this.head != 0) {
//如果数组队列已满，则迁移数据，防止频繁的移动数据造成效率低
for (int i = head; i < this.datas.length; i++) {
this.datas[i - head] = this.datas[i];
}
tail -= head;
head = 0;
}
this.datas[tail] = data;
tail = tail + 1;
size++;
return true;
}
/**
* 出队
*
* @return
*/
public Integer outQueue() {
if (isEmpty()) {
return null;
}
size--;
return this.datas[head++];
}
/**
* 判断队列是否为空
*
* @return
*/
private boolean isEmpty() {
if (head == tail && size == 0) {
return true;
}
return false;
}
/**
* 判断队列是否为满
*
* @return
*/
private boolean isFull() {
if (this.datas.length == size) {
return true;
}
return false;
}
/**
* 打印队列中的内容
*/
public void print() {
for (int i = head; i < tail; i++) {
System.out.printf(" " + this.datas[i]);
}
}
}
链表队列
/**
* @author caopengflying
* @time 2019/2/18 16:58
*/
public class Node {
private Integer data;
private Node next;
public Integer getData() {
return data;
}
public void setData(Integer data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}
/**
* @author caopengflying
* @time 2019/2/18 16:57
*/
public class CPFLinkQueue {
private Node head = new Node();
private Node tail = new Node();
/**
* 进队
* @param data
* @return
*/
public boolean enQueue(int data){
Node node = new Node();
node.setData(data);
if (null == this.head.getNext()){
this.head.setNext(node);
}
tail.setNext(node);
tail = node;
return true;
}
/**
* 出队
* @return
*/
public Integer outQueue(){
if (isNull()){
System.out.println("队列已空");
return null;
}
Integer data = this.head.getNext().getData();
this.head.setNext(this.head.getNext().getNext());
return data;
}
/**
* 打印队列内容
*/
public void print(){
Node n = head;
while (n.getNext() != null){
System.out.print(n.getNext().getData() + " ");
n = n.getNext();
}
System.out.println(" ");
}
/**
* 判断队列空
* @return
*/
private boolean isNull(){
if (null == this.head.getNext()){
return true;
}
return false;
}
}
