建筑公司做网站买空间多大合适,公司介绍ppt内容,石家庄营销网站建设,域名拍卖平台我们知道#xff0c;CPU资源是有限的#xff0c;任务的处理速度与线程个数并不是线性正相关的。相反#xff0c;过多的线程反而会导致CPU频繁切换#xff0c;处理性能下降。所以#xff0c;线程池的大小一般都是综合考虑要处理任务的特点和硬件环境#xff0c;来事先设置…我们知道CPU资源是有限的任务的处理速度与线程个数并不是线性正相关的。相反过多的线程反而会导致CPU频繁切换处理性能下降。所以线程池的大小一般都是综合考虑要处理任务的特点和硬件环境来事先设置的。当我们向固定大小的线程池中请求一个线程时如果线程池没有空闲资源了这个时候线程池如何处理这个请求是拒绝请求还是排队请求各种处理策略又是怎么实现的呢实际上这些问题并不复杂其底层的数据结构就是我们今天要学的内容队列queue。如果理解“队列”队列这个概念非常好理解。你可以把它想象成排队买票先来的先买后来的人只能站末尾不允许插队。先进来先出这就是典型的“队列”。我们知道栈只支持两个基本操作入栈push()和出栈pop()。队列跟栈非常相似支持的操作也很有限最基本的操作也是两个入队enqueue()放一个数据到队列尾部出列dequeue(),从队列头部取一个元素。所以队列跟栈一样也是一种操作受限的线性表数据结构。队列的概念很好理解基本操作也很容易掌握。作为一种非常基础的数据结构队列的应用也非常广泛特别是一些具有某些额外特性的队列比如循环队列阻塞队列并发队列。他们在很多偏底层系统框架中间件的开发中起着关键性的作用。比如高性能队列Disruptor,Linux环形缓存都用到循环并发队列Java concurrent并发包利用ArrayBlockingQueue来实现公平锁。顺序队列和链式队列我们知道了队列和栈一样也是一种抽象的数据结构。它具有先进先出的特性支持在队尾插入元素在对头删除元素那究竟该如何实现一个队列呢跟栈一样队列可以用数组来实现也可以用链表来实现。用数组实现的栈叫顺序栈用链表实现的栈叫链式栈。同样用数组实现的队列叫作顺序队列用链表实现的队列叫作链式队列。我们先来看下基于数组的实现方法。我用java语言实现了一下不过并不包含Java语言的高级语法而且我做了比较详细的注释你应该可以看懂。//用数组实现的队列
比起栈的数组实现队列的数组实现稍微有点儿复杂但是没关系。我稍微解释一下实现思路你很容易就能明白了。对于栈来说我们只需要一个栈顶指针就可以了。但是队列需要两个指针一个是head指针指向对头一个是tail指针指向队尾。你可以结合下面这幅图来理解。当abcd依次入队之后队列中的head指针指向下标为0的位置tail指针指向下标为4的位置。当我们调用两次出队操作之后队列中head指针指向下标为2的位置tail指针仍然指向下标为4的位置。你肯定已经发现了随着不停地进行入队出队操作head和tail都会持续往后移动。当tail移动到最右边即使数组中还有空闲空间也无法继续往队列中添加数据了。这个问题该如何解决呢你是否还记得在数组那一节我们也遇到过类似的问题就是数组的删除操作会导致数组中的数组不连续。你还记得我们当时是怎么解决的吗对用数据搬移但是每次进行出队操作都相当于删除数组下标为0的数据要搬移整个队列中的数据这样出队操作的时间复杂度就会从原来的O(1)变成O(n)。能不能优化一下呢实际上我们在出队时可以不用搬移数据。如果没有空闲空间了我们只需要在入队时再集中触发一次数据的搬移操作。借助这个思想出队函数dequeue()保持不变我们稍加改造一下函数enqueue()的实现就可以轻松解决刚才的问题了。下面是具体的代码//入队操作将item放入队尾
从代码中我们看到当队列的tail指针移动到数组的最右边后如果有新的数据入队我们可以将head到tail之间的数据整体搬移到数组中0到tail-head的位置。这种实现思路中出队操作的时间复杂度仍然是O(1),但入队操作的时间复杂度还是O(1)吗你可以用我们第3节第4节讲的算法复杂度分析方法自己试着分析一下。接下来我们再来看下基于链表的队列实现方法。基于链表的实现我们同样需要两个指针head指针和tail指针。他们分别指向链表的第一个结点和最后一个结点。如图所示入队是tail-nextnew_node,tail tail-next;出队时head head-next。循环队列我们刚才用数组来实现队列的时候在tail n时会有数据搬移操作这样入队操作性能就会收到影响。那有没有办法能够避免数据搬移呢我们来看看循环队列的解决思路。循环队列顾名思义它长得像一个环。原本数组是有头有尾的是一条直线。现在我们把首尾相连扳成了一个环。我画了一张图你可以直观地感受一下。我们可以看到图中这个队列的大小为8当前head4,tail7。当有一个新的元素a入队时我们放入下标为7的位置。但这个时候我们并不把tail更新为8而是将其在环中后移一位到下标为0的位置。当再有一个元素b入队时我们将b放入下标为0的位置然后tail加1更新为1。所以在a,b依次入队之后循环队列中的元素就变成了下面的样子通过这样的方法我们成功避免了数据搬移操作。看起来不难理解但是循环队列的代码实现难度要比前面讲的非循环队列难多了。要想写出没有bug的循环队列的实现代码我个人觉得最关键的是确定好对空和队满的判定条件。在用数组实现的非循环队列中队满的判断条件是tail n,队空的判断条件是headtail。那针对循环队列如何判断队空和队满呢队列为空的判断条件仍然是head tail。但队列满的判断条件就稍微有点复杂了。我画了一张队列满的图你可以看一下试着总结一下规律。就像我图中画的队满的情况tail3,head4,n8,所以总结一下规律就是31%84。多画几张队满 的图你就会发现当队满时(tail1)%nhead。你有没有发现当队列满时图中的tail指向的位置实际上是没有存储数据的。所以循环队列会浪费一个数组的存储空间。Taik is cheap,如果还是没怎么理解那就show 有code吧。public 阻塞队列和并发队列前面讲的内容理论比较多看起来很难跟实际的项目开发扯上关系。确实队列这种数据结构很基础平时的业务开发不大可能从零实现一个队列甚至都不会直接用到。而一些具有特殊特性的队列应用却比较广泛比如阻塞队列和并发队列。阻塞队列其实就是在队列基础上增加了阻塞操作。简单来说就是在队列为空的时候从队头取数据会被阻塞。因为此时还没有数据可取直到队列中有了数据才能返回如果队列已经满了那么插入数据的操作就会阻塞直到队列中有空闲位置后再插入数据然后再返回。你应该已经发现了上述的定义就是一个“生产者-消费者模型”是的我们可以使用阻塞队列轻松实现一个“生产者-消费者模型”这种基于阻塞队列实现的“生产者-消费者模型”可以有效地协调生产和消费的速度。当“生产者”生产数据的速度过快“消费者”来不及消费时存储数据的队列很快就会满了。这个时候生产者阻塞等待知道“消费者”消费了数据“生产者”才会被唤醒继续“生产”。而且不仅如此基于阻塞队列我们还可以通过协调“生产者”和“消费者”的个数来提高数据的处理效率。比如前面的例子我们可以配置几个“消费者”来应对一个“生产者”。前面我们讲了阻塞队列在多线程情况下会有多个线程同时操作队列这个时候就会存在线程安全问题那如何实现一个线程安全的队列呢线程安全的队列我们叫作并发队列。最简单直接的实现方式是直接在enqueue(),dequeue()方法上加锁但是锁粒度大并发度会比较低同一时刻仅允许一个存或者取操作。实际上基于数组的循环队列利用CAS原子操作可以实现非常高效的并发队列。这个也是循环队列比链式队列应用更加广泛的原因。在实战篇讲Disruptor的时候我会再详细讲并发队列的应用。解答开篇队列的知识就讲完了我们现在回过来看下开篇的问题。线程池没有空闲线程时新的任务请求线程资源时线程池该如何处理各种处理策略又是如何现实的呢我们一般有两种处理策略。第一种是非阻塞的处理方式直接拒绝任务请求另一种是阻塞的处理方法将请求排队等到有空闲线程时取出排队的请求继续处理。那如何存储排队的请求呢我们希望公平地处理每个排队的请求先进者先服务所以队列这种数据结构很适合来存储排队请求。我们前面说过队列有基于链表和基于数组这两种实现方式。这两种实现方式对于排队请求又有什么区别呢基于链表的实现方式可以实现一个支持无限排队的无界队列unbounded queue,但是可能会导致过多的请求排队等待请求处理的响应时间过长。所以针对响应时间比较敏感的系统基于链表实现的无限排队的线程池是不合适的。而基于数组实现的有界队列bounded queue,队列的大小有限所以线程池中队列的请求超过队列大小时接下来的请求就会被拒绝这种方式对响应敏感的系统来说就相对更加合理。不过设置一个合理的队列大小也是非常有讲究的。队列太大导致等待的请求太多队列太小会导致无法充分利用系统资源发挥最大性能。除了前面讲到队列应用在线程池请求队列的场景之外队列可以应用在任何有限资源池中用于排队请求比如数据库连接池等。实际上对于大部分资源有限的场景当没有空闲资源时基本上都可以通过“队列”这种数据结构来实现请求排队。内容小结今天我们讲 了一种跟栈很相似的数据结构队列。关于队列你能掌握下面的内容这节就没问题了。队列最大的特点就是先进先出主要的两个操作是入队和出队。跟栈一样它既可以用数组来实现也可以用链表来实现。用数组实现的叫顺序队列用链表实现的叫链式队列。特别是长得像一个环的循环队列。在数组实现队列的时候会有数组搬移操作要想解决数据搬移的问题我们就需要像环一样的循环队列。循环队列是我们这节的重点。要想写出没有bug的循环队列实现代码关键要确定好队空和队满的判定条件具体的代码你要能写出来。除此之外我们还讲了几种高级队列结构阻塞队列并发队列底层都还是队列这种数据结构只不过在之上附加了很多其他功能。阻塞队列就是入队出队操作可以阻塞并发队列就是队列的操作多线程安全。参考文献王争老师 《数据结构与算法之美》
