前言
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。先进先出，简单暴力的理解就是吃进去拉出来
优点:
- 提供了先进先出的存取方式
缺点:
- 存取其他项很慢
队列有两个最基本的操作，入队enqueue(),放一个数据到队列的尾部；出队dequeue()，从队列头部取出一个元素。
顺序队列和链式队列
队列可以使用数组来实现也可以使用链表来实现，用数组实队列的栈叫做顺序队列，用链表实现的队列叫做链式队列。
使用数组来实现一个队列：
public class ArrayQueue {private String[] items;
private int n = 0;//总大小
private int head = 0;
private int tail = 0;
//申请一个大小为n的数组
public ArrayQueue(int n) {
this.items = new String[n];
this.n = n;
}
//入队
public boolean enqueue(String item){
//如果队列满了返回false
if(tail == n) return false;
items[tail] = item;
++tail;
return true;
}
//出队
public String dequeue(){
//head == tail 表示队列为空
if(head == tail) return null;
String res = items[head];
++head;
return res;
}
}
队列需要两个指针，一个指向队头，一个指向队尾。
当a、b、c、d一次进入队列之后，队列中的head指针指向下标为0的位置，tail下标为4的位置
当我们调用两次出队操作的之后，队列中的head指针指向下标为2的位置，tail指针位置不变。
随着不停的入队和出队操作，head和tail指针会不断的往后移动移动到最右边，即使数组中还有空闲的空间也不能往队列中添加数据了，那怎么办呢？
我们可以使用数据搬移，当然出队的时候不会出现空间不够的情况也就不用搬移，我们只需要在入队的时候集中触发一次数据搬移即可。根据这个思想，上面的出队操作不用变，入队操作可以改成下面的：
public boolean enqueue(String item){//tail==n 说明队列满了
if(tail == n){
//tail==n&&head==0说明整个队列都是满的
if(head == 0) return false;
//搬移数据
for (int i = head; i < tail; i++) {
items[i-head] = items[i];
}
//更新tail 和 head
tail -= head;
head = 0;
}
items[tail] = item;
++tail;
return true;
}
从上面的代码可以看到，当tail指针移动到数据的最右边之后，如果有新数据插入，我们可以将head和tail之间的数据，整体搬移到数组0到tail-head的位置。
使用链表实现队列：
使用链表实现队列同样需要head和tail指针，分别指向链表的第一个结点和最后一个结点。
入队的时候，tail的next指针指向新的结点，然后tail变成新的结点的next。
出队的时候，head的next结点变成它后面的结点的next结点。
public class LinkedQueue {private Node head = null;
private Node tail = null;
//入队
public void enqueue(String value){
if(tail == null){
Node newNode = new Node(value,null);
head = newNode;
tail = newNode;
}else {
tail.next = new Node(value,null);
tail = tail.next;
}
}
//出队
public String dequeue(){
if(head == null) return null;
String value = head.data;
head = head.next;
if(head == null){
tail = null;
}
return value;
}
private static class Node{
private String data;
private Node next;
public Node(String data, Node next) {
this.data = data;
this.next = next;
}
public String getData() {
return data;
}
}
}
循环队列：
上面使用数组来实现的队列，当tail==n的时候，会有数据的搬移操作，这样入队的时候的性能就会收到影响。有没有办法解决呢？可以使用循环队列。
原本的数组是一条直线，有头有尾，现在我们把首位相连组成一个环
当tail == n 的时候，表示队列满了，当 head == tail的时候表示队列是空的。
public class CircleQueue {private String[] items;
private int n = 0;//总大小
private int head = 0;
private int tail = 0;
//申请一个大小为n的数组
public CircleQueue(int n) {
this.items = new String[n];
this.n = n;
}
//入队
public boolean enqueue(String item){
//(tail+1)%n == head表示满了
if((tail + 1)%n == head) return false;
items[tail] = item;
tail = (tail+1)%n;
return true;
}
//出队
public String dequeue(){
//head == tail 表示队列为空
if(head == tail) return null;
String res = items[head];
head = (head+1)%n;
return res;
}
}
阻塞队列：
阻塞队列就是在队列的基础上加了阻塞操作，就是在队列空的时候，从头部取数据会被阻塞，直到队列中有了数据才会返回。如果队列已经满了，那么插入数据的操作会被阻塞，直到队列中有新的空闲位置的时候才返回。
并发队列：
在多线程的情况下，会有多个线程同时操作队列，这时候就会存在线程安全的问题。
线程安全的队列称为并发队列，最简单直接的方式就是在enqueue()和dequeue()的方法上加上锁。
不过锁的粒度比较大，同一时刻只能有一个存或者取的操作。
通过基于数组的循环队列，利用CAS原子操作，可以实现非常高的并发队列。
大部分资源有限的场景，当没有空闲资源的时候，基本上都可以用于排队请求，比如线程池，数据库连接池等。