1.简介
队列（Queue），是一种先进先出的数据结构，First In First Out(FIFO),可以想象一下，就像是在排队买票，后来的人只能排在对尾，先来的人可以先买票（在对头，可以执行出去的操作）。
队列支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。所以，和栈一样，队列也是一种操作受限的线性表，但是队列比栈多出来一个操作端，可以吧队列想象成一个水管，一头进水，一头出水；栈可以想象成一个瓶子，进出都是一个口，这就是它们最直观的区别。
2. 分类
2.1 分类
（1）队列分类上可以从实现的底层结构上分，一种使用数组实现，一种是使用链表实现。
- 顺序队列
- 链式队列
（2）循环队列，在容量有了限制时，可以从对尾循环回到对头（队列头为空时），充分利用空间。
2.2 应用
（1）阻塞队列
1）在队列的基础上增加阻塞操作，就成了阻塞队列。
2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。
3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。
2.并发队列
1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。
2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。
3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。
3.线程池
在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。
3 队列实现
3.1 顺序队列
顺序队列通过队列头和对尾来控制队列，即使用 front 和 rear 来控制，保证 front 始终在 rear 的前面。特别注意 front 移动到中间，rear 在对尾时，再添加元素，需要整体移动数据到队列头，时间复杂度较大，O(n)。所以才有后面的循环队列。下面就来看下代码,具体的逻辑就不分析了，好好看下，应该能看懂。仅仅提供一种思路，可以进行优化或者提出其他思路，写在评论区一起讨论（Java实现，C代码文章结尾有地址，可以自己查看）
定义接口
public interface Queue<E> {
boolean enQueque(E e);
E deQueue();
E peek();
int size();
}
具体实现
public class RArrayQueue<T> implements Queue<T> {
private static final int DEFAULT_SIZE = 10;
private Object[] elements;
private int head;
private int tail;
public RArrayQueue() {
this(DEFAULT_SIZE);
}
public RArrayQueue(int size) {
if (size < 1) {
size = DEFAULT_SIZE;
}
elements = new Object[size + 1];
}
@Override
public boolean enQueque(T t) {
if (isFull()) {
return false;
}
if (tail == elements.length) {
if (isEmpty()) {
head = 0;
tail = 0;
} else {
Object[] newElements = new Object[elements.length];
System.arraycopy(elements, head, newElements, 0, size());
elements = newElements;
tail = size();
head = 0;
}
}
elements[tail++] = t;
return true;
}
@SuppressWarnings("unchecked")
@Override
public T deQueue() {
if (isEmpty()) {
return null;
}
return (T) elements[head++];
}
@SuppressWarnings("unchecked")
@Override
public T peek() {
if (isEmpty()) {
return null;
}
return (T) elements[head];
}
@Override
public int size() {
return tail - head;
}
public boolean isEmpty() {
return head == tail;
}
public boolean isFull() {
return size() == elements.length - 1;
}
3.2 循环队列
public class CircleQueue<T> implements Queue<T> {
private static final int DEFAULT_CAPACITY = 10;
private Object[] elements;
private int front = 0;
private int rear = 0;
public CircleQueue() {
this(DEFAULT_CAPACITY);
}
public CircleQueue(int capacity) {
if (capacity < 1) {
capacity = DEFAULT_CAPACITY;
}
elements = new Object[capacity + 1];
}
@Override
public boolean enQueque(T t) {
checkQueue();
if (isFull()) {
return false;
}
elements[rear] = t;
rear = (rear + 1) % elements.length;
return true;
}
@SuppressWarnings("unchecked")
@Override
public T deQueue() {
checkQueue();
if (isEmpty()) {
return null;
}
T t = (T) elements[front];
elements[front] = null;
front = (front + 1) % elements.length;
return t;
}
@SuppressWarnings("unchecked")
@Override
public T peek() {
checkQueue();
if (isEmpty()) {
return null;
}
return (T) elements[front];
}
@Override
public int size() {
checkQueue();
return (rear - front + elements.length) % elements.length;
}
public boolean isEmpty() {
return front == rear;
}
public boolean isFull() {
return (rear + 1) % elements.length == front;
}
private void checkQueue() {
if (elements == null || elements.length < 1) {
throw new NullPointerException("Queue is null!");
}
if (front < 0 || front >= elements.length) {
throw new IndexOutOfBoundsException("index id out of bounds!");
}
if (rear < 0 || rear >= elements.length) {
throw new IndexOutOfBoundsException("index id out of bounds!");
}
}
}
3.3 两个队列实现还一个栈
public class StackWithTwoQueue<T> {
private static final int DEFAULT_SIZE = 10;
private CircleQueue<T> queue1;
private CircleQueue<T> queue2;
private int top = -1;
public StackWithTwoQueue() {
this(DEFAULT_SIZE);
}
public StackWithTwoQueue(int capacity) {
if (capacity < 1) {
capacity = DEFAULT_SIZE;
}
queue1 = new CircleQueue<>(capacity);
queue2 = new CircleQueue<>(capacity);
}
public boolean push(T t) {
if (isFull()) {
return false;
}
if (queue1.isEmpty() && queue2.isEmpty()) {
return queue1.enQueque(t);
} else if (queue1.isEmpty()) {
return queue2.enQueque(t);
} else {
return queue1.enQueque(t);
}
}
public T pop() {
if (isEmpty()) {
return null;
}
if (queue1.isEmpty()) {
transQueue(queue1, queue2);
return queue2.deQueue();
} else {
transQueue(queue2, queue1);
return queue1.deQueue();
}
}
private void transQueue(Queue<T> enQueue, Queue<T> deQueue) {
int size = deQueue.size();
for (int i = 0; i < size - 1; i++) {
enQueue.enQueque(deQueue.deQueue());
}
}
/**
* 栈顶元素，有点麻烦，低效
*
* @return
*/
public T peek() {
if (isEmpty()) {
return null;
}
T result = null;
if (queue1.isEmpty()) {
transQueue(queue1, queue2);
result = queue2.deQueue();
queue1.enQueque(result);
} else {
transQueue(queue2, queue1);
result = queue1.deQueue();
queue2.enQueque(result);
}
return result;
}
public boolean isEmpty() {
return queue1.isEmpty() && queue2.isEmpty();
}
public boolean isFull() {
return queue1.isFull() || queue2.isFull();
}
public int size() {
if (queue1.isEmpty()) {
return queue2.size();
} else if (queue2.isEmpty()) {
return queue1.size();
} else {
throw new RuntimeException("the data struct is error!");
}
}
}
3.4 两个栈实现一个队列
public class QueueWithTwoStacks<E> implements Queue<E> {
private static final int DEFAULT_CAPACITY = 10;
private int MAX_LENGTH;
private RStack<E> stack1;
private RStack<E> stack2;
public QueueWithTwoStacks() {
this(DEFAULT_CAPACITY);
}
public QueueWithTwoStacks(int capacity) {
if (capacity < 1) {
capacity = DEFAULT_CAPACITY;
}
MAX_LENGTH = capacity;
stack1 = new RStack<>(capacity);
stack2 = new RStack<>(capacity);
}
@Override
public boolean enQueque(E e) {
if (size() >= MAX_LENGTH || stack1.isFull()) {
return false;
}
stack1.push(e);
return true;
}
@Override
public E deQueue() {
if (size() < 1) {
return null;
}
transStacks();
return stack2.pop();
}
@Override
public E peek() {
if (size() < 1) {
return null;
}
transStacks();
return stack2.peek();
}
public boolean isEmpty() {
return size() < 1;
}
public boolean isFull(){
return size() == MAX_LENGTH;
}
/**
* 转移两个栈的元素
*/
private void transStacks() {
if (!stack2.isEmpty()) {
return;
}
while (!stack1.isEmpty()) {
stack2.push(stack1.pop());
}
}
@Override
public int size() {
return stack1.size() + stack2.size();
}
}
测试的代码就不贴出来了，仅仅参考下，测试代码相对简单，测试的并不严谨，一些边界条件，还需要详细测试。
