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

09|队列：队列在线程池等有限资源池中的应用 09|队列：队列在线程池等有限资源池中的应用 CPU CPU 我们知道， 资源是有限的，任务的处理速度与线程个数并不是线性正相关。相反，过多的线程反而会导致 频繁切换，处理性能下降。所以，线程池的大 小一般都是综合考虑要处理任务的特点和硬件环境，来事先设置的。 当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲资源了，这个时候线程池如何处理这个请求？是拒绝请求还是排队请求？各种处理策略又 是怎么实现的呢？ 实际上，这些问题并不复杂，其底层的数据结构就是我们今天要学的内容，队列（queue）。 “ ” 如何理解 队列 ？ 队列这个概念非常好理解。你可以把它想象成排队买票，先来的先买，后来的人只能站末尾，不允许插队。先进者先出，这就是典型的“队列”。 我们知道，栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue() ，放一个数据到 队列尾部；出队dequeue() ，从队列头部取一个元素。 file:///F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html[2019/1/15 15:35:21] 09|队列：队列在线程池等有限资源池中的应用 file:///F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html[2019/1/15 15:35:21] 09|队列：队列在线程池等有限资源池中的应用 所以，队列跟栈一样，也是一种操作受限的线性表数据结构。 队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、 阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列Disruptor、Linux环形缓存，都用到了循环并发队 列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。 顺序队列和链式队列 我们知道了，队列跟栈一样，也是一种抽象的数据结构。它具有先进先出的特性，支持在队尾插入元素，在队头删除元素，那究竟该如何实现一个队列呢？ 跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列， 用链表实现的队列叫作链式队列。 Java Java 我们先来看下基于数组的实现方法。我用 语言实现了一下，不过并不包含 语言的高级语法，而且我做了比较详细的注释，你应该可以看懂。 // 用数组实现的队列 public class ArrayQueue { // 数组：items ，数组大小：n private String[] items; private int n = 0; // head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0; // 申请一个大小为capacity的数组 public ArrayQueue(int capacity) { items = new String[capacity]; n = capacity; } // 入队 public boolean enqueue(String item) { // 如果tail == n 表示队列已经满了