队列

1. 队列：先进先出

队列的基本操作：

• 入队enqueue(),放一个数据到队列尾部；
• 出队dequeue(),从队列头部取一个元素；

如下，和栈的对比图：

所以，队列和栈一样，也是一种操作受限的线性表数据结构。

注：作为一种非常基础的数据结构，队列的应用广泛，特别是一些具有某些额外特性的队列，比如：循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性作用。比如高性能Disruptor、Linux环性缓存、都用到了循环并发队列。Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。

2.顺序队列和链式队列

跟栈一样，队列可以用数组来实现，也可以用链表来实现。

用数组实现的栈叫做顺序栈；用链表实现的栈叫做链式栈。

对于顺序队列的实现：队列的实现需要两个指针，一个是head指针，指向队头；一个是tail指针，指向队尾；

2.1 顺序队列

实现如下图：

2.2 链式队列

如下：

2.3 循环队列

用数组实现队列的时候，当tail==n时，会有数据搬移操作。那么有办法能避免数据搬移吗？这里讲下循环队列。

循环队列，如何判断队空和队满呢？

队列为空的判断条件依然是head==tail。队列为满的条件是（tail+1）%n=head

2.4 阻塞队列和并发队列

阻塞队列其实就是在队列基础上增加了阻塞操作。

简单来说，就是在队列为空的时候，从队头取数据会被阻塞。

因为此时还没有数据可取，直到队列中有了数据才能返回；

如果队列已经满了，那么插入数据的操作就会被阻塞，直到队列中有空闲位置后再插入数据，然后返回。

如图:

其实上面就是一个“生产者-消费者模型”。我们可以用一个阻塞队列，实现它。

这种基于队列实现的“生产者-消费者模型”，可以有效的协调生产和消费的速度。

当生产者生产数据的速度过快，消费者来不及消费时，存储数据的队列很快就会满了。

这个时候，生产者就阻塞等待，直到消费者消费了数据，生产者才会被唤醒继续生产。

而且，基于阻塞队列，我们可以协调生产者和消费者的个数，来提高数据的处理效率。

比如前面的例子，我们可以多配置几个消费者，来应对一个生产者。

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

线程安全的队列，叫做并发队列。

最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁，

但是粒度锁大并发度会比较低，同一时刻仅允许一个存或者取操作。

3.线程池没有空闲线程时，新的任务请求线程资源时，线程池该如何处理？各种处理策略又是如何实现的呢？

对此，我们一般有两种处理策略。

1. 非租塞的处理方式。直接拒绝任务请求；
2. 阻塞的处理方式。将请求排队，等到有空闲线程时，取出排队的请求继续处理。

对于第二种方式，那么怎么存储排队的请求呢？

为了公平的处理每个请求，先进者先服务，所以我们用队列这种数据结构来存储排队。

但是队列的实现又有基于链表和数组这两种方式，这两种实现方式对于排队请求有什么区别？

1 基于链表的实现方式，可以实现一个支持无限排队的无界队列(unbounded queue)，

但是会导致过多的请求排队等待，请求处理的响应时间过长。

所以，针对响应时间比较敏感的系统，基于链表实现的无限排队的线程池是不合适的。

2 而基于数组实现的有界队列(bounded queue)，队列的大小有限，

所以线程池中的排队的请求超过队列大小时，接下来的请求就会被拒绝，这种方式对响应时间敏感的系统来说，就更合理。

不过，要设置一个合理的队列大小，也是非常讲究的。

队列太大导致等待的请求太多，队列太小，会导致无法充分利用系统资源，发挥最大性能。

队列除了应用在线程池请求排队的场景之外，队列可以应用在任何有限资源池中，用于排队请求，比如数据库连接池。

课后思考：

1. 除了线程池这种池结构会用到队列排队请求，你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢？

答：数据库连接池，任务队列

2.关于如何实现无锁并发队列，你怎么看？