AI_第一部分 数据结构与算法（8.队列）

第四阶段我们进行深度学习(AI)，本部分（第一部分）主要是对底层的数据结构与算法部分进行详尽的讲解，通过本部分的学习主要达到以下两方面的效果：

1.对开发中常见的算法能应用自如，让你在跳槽找工作中“算法题”不再是阻碍你“钱途”的拦路虎。

2.我们不需要调参数的调参攻城狮，我们要做正真的自己的AI模型。

3.本部分预计40篇左右。

今天我们聊聊队列这种数据结，这种数据结构的思想在开发中也是经常会使用的，不是说让你去实现一个队列，而是使用队列的特性。

第一、如何理解队列？

在现实生活中，我们每天排队，先来的人先上车，后来的人后上车（当然理想环境中哈），这种“先进先出，就是典型的队列”。

我们知道，栈只支持两种基本操作：入栈push()和出栈pop(),对于使用python如何实践其功能，可以参考上篇。队列跟栈很相似，支持的操作也很有限，最基本的操作就是：入队enqueue(),放一个数据到队尾部，出队dequeue(),从队列头部取一个元素。所以这也是一种操作受限的线性表数据结构。

第二、顺序队列和链式队列以及循环队列

和栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的队列叫顺序队列，用链表实现的队列叫做链式队列。

循环队列，就是它长的像一个环。原本数组就是有头有尾的，是一条直线。现在我们把首尾相连，变成一个环。

第三、阻塞队列和并发队列

阻塞队列其实就在队列基础上增加了阻塞操作。简单的说，就是在队列为空的时候，从队头取数据会被阻塞。因为此时还没有数据可取，直到队列中有了数据才会返回；如果队列已经满了，那么插入数据的操作就是会被阻塞，直到队列中有空闲位置后再插入数据，然后返回。你应该已经发现了，上述的定义是一个“生产者 - 消费者模型”！是的，我们可以使用阻塞队列，轻松实现一个“生产者 --消费者模型”

这种基于阻塞队列实现的“生产者 --消费者模型”,可以有效的协调生产和消费的速度。当“生产者”生产的数据的速度过快，“消费者”来不及消费时，存储数据的队列很快就满了。这个时候，生产者就阻塞等待，直到“消费者”消费了数据，“生产者”才会被唤醒继续“生产”。 而且不仅如此，基于阻塞队列，我们还可以通过协调“生产者”和“消费者“的个数，来提高数据的处理效率。

在多线程的情况下，会有多个线程同时操作队列，这个时候就会存在线程安全的问题，那如何实现一个线程安全的队列呢？

线程安全的队列呢，我们可以称为并发队列。最简单的实现就是直接在enqueue()和dequeue()方法上加锁，但是锁粒度大并发程度就会降低，同一时刻仅仅允许一个存储或者取操作。实际上，基于数组的循环队列，利用CAS原子操作，可以实现非常高效的并发队列。这也就是循环队列比链式队列更加广泛应用的原因。

第四、实践思考

CPU的资源是有限的，任务的处理速度和线程个数并不是线性的正相关。相反的，过多的线程会导致CPU的频繁的切换，处理的性能会有所下降。所以就会产生一个问题：在实际的开发中，这个线程池的大小如何来评估呢？当我们向固定大小的线程池中请求一个线程时，如果线程池中没有空闲的资源了，这个时候线程池如何处理这个请求呢？

通过第三部分的分析，我们有两种方式来处理。其一就是非阻塞的处理方式，直接拒绝任务请求；另一种就是阻塞的处理方式，将请求排队，等到有空闲线程时，取出排队的请求继续处理，这样就会有一个问题，如何存储排队的请求呢？

我们的期望是公平的处理每一个排队的请求，先进者先服务（这种思想在操作系统中的cpu调度算法中的一种是一致的），所以队列的这种数据结构很适合来存储排队的请求。

总结：对于大部分的资源有限的场景，当没有空闲资源时候，基本上就可以通过“队列”这种数据结构来实现排队请求。

好了，今天关于队列的知识就分享到这里，关于python版本的队列，我会已福利的方式提供给大家，为大家提供我的github链接，如有需要到时可以自行下载，谢谢。