1、 items; private int n = 0; 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 / head表示队头下标，tail表示队尾下标 private int head = 0; private int tail = 0; / 申请一个大小为capacity的数组 public CircularQueue(int capacity) items = new Stringcapacity; n = capacity; / 入队 pu
2、blic boolean enqueue(String item) / 队列满了 if (tail + 1) % n = head) return false; itemstail = item; tail = (tail + 1) % n; return true; / 出队 public String dequeue() / 如果head = tail 表示队列为空 if (head = tail) return null; String ret = itemshead; head = (head + 1) % n; return ret; 阻塞队列和并发队列 前面讲的内容理论比较多，看起
3、来很难跟实际的项目开发扯上关系。确实，队列这种数据结构很基础，平时的业务开发不大可能从零实现一个队列，甚至都不会 直接用到。而一些具有特殊特性的队列应用却比较广泛，比如阻塞队列和并发队列。 阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据 才能返回；如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后再返回。 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html
4、2019/1/15 15:35:21 你应该已经发现了，上述的定义就是一个“生产者-消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者-消费者模型”！ 这种基于阻塞队列实现的“生产者-消费者模型”，可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快，“消费者”来不及消费时，存储数据的队列 很快就会满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。 而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者”的个数，来提高数据的处理效率。比如前面的例子，我们可以多配置几个“消费者”，来应 对一个“生产者”。 09|队列：
5、队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 前面我们讲了阻塞队列，在多线程情况下，会有多个线程同时操作队列，这个时候就会存在线程安全问题，那如何实现一个线程安全的队列呢？ 线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁，但是锁粒度大并发度会比较低，同一时刻仅允许一个存或 者取操作。实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列。这也是循环队列比链式队列应用更加广泛
6、的原因。在实战篇 讲Disruptor的时候，我会再详细讲并发队列的应用。 解答开篇 队列的知识就讲完了，我们现在回过来看下开篇的问题。线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的 呢？ 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 我们一般有两种处理策略。第一种是非阻塞的处理方式，直接拒绝任务请求；另一种是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续 处理。那如何存储排队的请
7、求呢？ 我们希望公平地处理每个排队的请求，先进者先服务，所以队列这种数据结构很适合来存储排队请求。我们前面说过，队列有基于链表和基于数组这两种实现方 式。这两种实现方式对于排队请求又有什么区别呢？ 基于链表的实现方式，可以实现一个支持无限排队的无界队列（unbounded queue），但是可能会导致过多的请求排队等待，请求处理的响应时间过长。所以，针 对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。 而基于数组实现的有界队列（bounded queue），队列的大小有限，所以线程池中排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏 感的系统来说，就相
8、对更加合理。不过，设置一个合理的队列大小，也是非常有讲究的。队列太大导致等待的请求太多，队列太小会导致无法充分利用系统资 源、发挥最大性能。 除了前面讲到队列应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池等。实际上，对于大部分资源有限 的场景，当没有空闲资源时，基本上都可以通过“队列”这种数据结构来实现请求排队。 内容小结 今天我们讲了一种跟栈很相似的数据结构，队列。关于队列，你能掌握下面的内容，这节就没问题了。 队列最大的特点就是先进先出，主要的两个操作是入队和出队。跟栈一样，它既可以用数组来实现，也可以用链表来实现。用数组实现的叫顺序队列，用
9、链表实 现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候，会有数据搬移操作，要想解决数据搬移的问题，我们就需要像环一样的循环队列。 循环队列是我们这节的重点。要想写出没有bug的循环队列实现代码，关键要确定好队空和队满的判定条件，具体的代码你要能写出来。 除此之外，我们还讲了几种高级的队列结构，阻塞队列、并发队列，底层都还是队列这种数据结构，只不过在之上附加了很多其他功能。阻塞队列就是入队、出 队操作可以阻塞，并发队列就是队列的操作多线程安全。 课后思考 1. 除了线程池这种池结构会用到队列排队请求，你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢？ 2. 今天讲到
10、并发队列，关于如何实现无锁并发队列，网上有非常多的讨论。对这个问题，你怎么看呢？ 欢迎留言和我分享，我会第一时间给你反馈。 我已将本节内容相关的详细代码更新到GitHub，戳此即可查看。 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 精选留言： 城 2018-10-10 00:46:32 1.分布式应用中的消息队列，也是一种队列结构 2.考虑使用CAS实现无锁队列，则在入队前，获取tail位置，入队时比较tail是否发生变化，如果否，则允许入
11、队，反之，本次入队失败。出队则是获取head位 置，进行cas。 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 个人浅见，请批评指正 63赞 作者回复2018-10-10 01:34:47 wean 2018-10-10 11:58:30 队列也是一种“操作受限”的线性表，只支持两种基本操作：入队和出队。 队列的应用非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层的系统、框架、中间件的开发中，起
12、着关键性的作用。比如高性能队列 Disruptor、Linux 环形缓存，都用到了循环并发队列；Java concurrent 并发包利用 ArrayBlockingQueue 来实现公平锁等。 关于如何实现无锁并发队列 可以使用 cas + 数组的方式实现。 队列的其他应用 分布式消息队列，如 kafka 也是一种队列。 12赞 作者回复2018-10-11 15:02:39 花见笑 2018-10-10 01:05:54 循环队列的长度设定需要对并发数据有一定的预测，否则会丢失太多请求。 8赞 作者回复2018-10-10 02:04:31 只会安卓De小鹿 2018-10-11 13:3
13、5:38 王争老师，为了更好的区分队列和栈，小鹿给大家一个更好的口诀。 “吃多了拉就是队列，吃多了吐就是栈”。哈哈！ 158赞 作者回复2018-10-12 02:18:38 计科一班 2018-10-10 06:19:53 老师，循环队列的数组实现，在您的代码中，入队时会空留出一个位置，而且我感觉不太好理解。我定义一个记录队列大小的值size，当这个值与数组大小 相等时，表示队列已满，当tail达到最底时，size不等于数组大小时，tail就指向数组第一个位置。当出队时，size，入队时size+ 65赞 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektim
14、e/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 作者回复2018-10-11 01:52:16 你这个思路挺巧妙的 我暂时还没有想到破绽 Peter丶桥 2018-10-10 04:36:48 老师要是有时间对课后问题集中式做下解答就好了 21赞 作者回复2018-10-11 01:52:33 行的 姜威 2018-10-12 00:51:09 队列实现 一、数组实现 public class ArrayQueue /存储数据的数组 private String items; /记录数组容量 private int n; pri
15、vate int size; /head记录队头索引，tail记录队尾索引 private int head = 0; private int tail = 0; /申请一个指定容量的队列 public ArrayQueue(int capacity) items = new Stringcapacity; n = capacity; /* * 入队： * 1.堆满的时，入队失败 * 1.1频繁出入队，造成数组使用不连续 * 1.2在入队的时候，集中触发进行数据搬移 * 2.在末尾插入数据，注意tail指向队尾元素的索引+1 */ public boolean enqueue(String i
16、tem) / 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 表示队满 if(head = 0 /表示需要数据搬移 else if(head != 0 i tail; i+) itemsi-head = itemsi; head = 0; tail = tail - head; /将数据加入队列 itemstail+ = item; size+; return true; /出队：1.队空时，出队失败;2.出队，head索引+1 public
17、String dequeue() String res = null; if(head = tail) return res; res = itemshead+; size-; return res; 二、循环队列 public class LoopArrayQueue /存储数据的数组 private String items; /记录数组容量 private int n; private int size = 0; /head记录队头索引，tail记录队尾索引 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geektime/数据结构与算法之美/09队列：队列在线程
18、池等有限资源池中的应用.html2019/1/15 15:35:21 private int head = 0; private int tail = 0; /申请一个指定容量的队列 public LoopArrayQueue(int capacity) items = new Stringcapacity; n = capacity; /入队：关键在于队满的条件 public boolean enqueue(String item) if (tail + 1) % n = head) return false; itemstail = item; tail = (tail + 1) % n;
19、 size+; return true; /出队：关键在于队空的条件 public String dequeue() String res = null; if(head = tail) return res; res = itemshead; head = (head + 1) % n; size-; return res; 三、链表实现 public class LinkedQueue /定义一个节点类 private class Node String value; Node next; /记录队列元素个数 09|队列：队列在线程池等有限资源池中的应用 file:/F/temp/geek
20、time/数据结构与算法之美/09队列：队列在线程池等有限资源池中的应用.html2019/1/15 15:35:21 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; 18赞
个人主页
