09 | 队列：队列在线程池等有限资源池中的应用

队列也是一种“操作受限”的线性表，只支持两种基本操作：入队和出队。 队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层的系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。 关于如何实现无锁并发队列 可以使用 cas + 数组的方式实现。 队列的其他应用 分布式消息队列，如 kafka 也是一种队列。

循环队列的长度设定需要对并发数据有一定的预测，否则会丢失太多请求。

1.分布式应用中的消息队列，也是一种队列结构 2.考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入队，反之，本次入队失败。出队则是获取head位置，进行cas。 个人浅见，请批评指正

王争老师，为了更好的区分队列和栈，小鹿给大家一个更好的口诀。 “吃多了拉就是队列，吃多了吐就是栈”。哈哈！

老师，循环队列的数组实现，在您的代码中，入队时会空留出一个位置，而且我感觉不太好理解。我定义一个记录队列大小的值size，当这个值与数组大小相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size—，入队时size++

循环队列：队列满的表达式 这里讲一下，这个表达式是怎么来的。在一般情况下，我们可以看出来，当队列满时，tail+1=head。但是，有个特殊情况，就是tail=n-1，而head=0时，这时候，tail+1=n，而head=0，所以用(tail+1)%n == n%n == 0。而且，tail+1最大的情况就是 n ，不会大于 n，这样，tail+1 除了最大情况，不然怎么余 n 都是 tail+1 本身，也就是 head。这样，表达式就出现了。

队列实现 一、数组实现 public class ArrayQueue { //存储数据的数组 private String[] items; //记录数组容量 private int n; private int size; //head记录队头索引，tail记录队尾索引 private int head = 0; private int tail = 0; //申请一个指定容量的队列 public ArrayQueue(int capacity){ items = new String[capacity]; n = capacity; } /* * 入队： * 1.堆满的时，入队失败 * 1.1频繁出入队，造成数组使用不连续 * 1.2在入队的时候，集中触发进行数据搬移 * 2.在末尾插入数据，注意tail指向队尾元素的索引+1 */ public boolean enqueue(String item){ //表示队满 if(head == 0 && tail == n) return false; //表示需要数据搬移 else if(head != 0 && tail == n){ for (int i = head; i < tail; i++) { items[i-head] = items[i]; } head = 0; tail = tail - head; } //将数据加入队列 items[tail++] = item; size++; return true; } //出队：1.队空时，出队失败;2.出队，head索引+1 public String dequeue(){ String res = null; if(head == tail) return res; res = items[head++]; size--; return res; } } 二、循环队列 public class LoopArrayQueue { //存储数据的数组 private String[] items; //记录数组容量 private int n; private int size = 0; //head记录队头索引，tail记录队尾索引 private int head = 0; private int tail = 0; //申请一个指定容量的队列 public LoopArrayQueue(int capacity){ items = new String[capacity]; n = capacity; } //入队：关键在于队满的条件 public boolean enqueue(String item){ if ((tail + 1) % n == head) return false; items[tail] = item; tail = (tail + 1) % n; size++; return true; } //出队：关键在于队空的条件 public String dequeue(){ String res = null; if(head == tail) return res; res = items[head]; head = (head + 1) % n; size--; return res; } } 三、链表实现 public class LinkedQueue { //定义一个节点类 private class Node{ String value; Node next; } //记录队列元素个数 private int size = 0; //head指向队头结点，tail指向队尾节点 private Node head; private Node tail; //申请一个队列 public LinkedQueue(){} //入队 public boolean enqueue(String item){ Node newNode = new Node(); newNode.value = item; if (size == 0) head = newNode; else tail.next = newNode; tail = newNode; size++; return true; } //出队 public String dequeue(){ String res = null; if(size == 0) return res; if(size == 1) tail = null; res = head.value; head = head.next; size--; return res; } }

在正常情况下，队列的入队和出队操作时间复杂度都是O(1)，在进行“数据搬移”改造的情况下，入队的时间复杂度我是这么分析的： 如果队尾没有满，可以直接入队，时间复杂度为O(1)。 如果队尾已满的情况下，就必须进行数据搬移了，tail=n,搬移的时间复杂度为O(n). 总体情况来看，tail的可能是0~n的任意值，在0~n-1的时候队列入队的时间复杂度都是O(1)，不需要搬移直接入队即可；只有当tail=n的时候时间复杂度才迅速飙升为O(n)，即需要进行n次搬移，此时n次的搬移如果均摊到0~n-1这n次上，其实总体的均摊复杂度还是O(1)。 老师，我分析的是否正确？

总结 一、什么是队列？ 1.先进者先出，这就是典型的“队列”结构。 2.支持两个操作：入队enqueue()，放一个数据到队尾；出队dequeue()，从队头取一个元素。 3.所以，和栈一样，队列也是一种操作受限的线性表。 二、如何实现队列？ 1.队列API public interface Queue<T> { public void enqueue(T item); //入队 public T dequeue(); //出队 public int size(); //统计元素数量 public boolean isNull(); //是否为空 } 2.数组实现（顺序队列）：见下一条留言 3.链表实现（链式队列）：见下一条留言 4.循环队列（基于数组）：见下一条留言 三、队列有哪些常见的应用？ 1.阻塞队列 1）在队列的基础上增加阻塞操作，就成了阻塞队列。 2）阻塞队列就是在队列为空的时候，从队头取数据会被阻塞，因为此时还没有数据可取，直到队列中有了数据才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后在返回。 3）从上面的定义可以看出这就是一个“生产者-消费者模型”。这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就会满了，这时生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续生产。不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据处理效率，比如配置几个消费者，来应对一个生产者。 2.并发队列 1）在多线程的情况下，会有多个线程同时操作队列，这时就会存在线程安全问题。能够有效解决线程安全问题的队列就称为并发队列。 2）并发队列简单的实现就是在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或取操作。 3）实际上，基于数组的循环队列利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛的原因。 3.线程池资源枯竭是的处理 在资源有限的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。 四、思考 1.除了线程池这种池结构会用到队列排队请求，还有哪些类似线程池结构或者场景中会用到队列的排队请求呢？ 2.今天讲到并发队列，关于如何实现无锁的并发队列，网上有很多讨论。对这个问题，你怎么看？

很多同学都提到循环队列增加flag来避免浪费最后一个存储空间，那是不是flag本身也需要一个存储空间？