队列的基本操作:
如下,和栈的对比图:
所以,队列和栈一样,也是一种操作受限的线性表数据结构。
注:作为一种非常基础的数据结构,队列的应用广泛,特别是一些具有某些额外特性的队列,比如:循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中,起着关键性作用。比如高性能Disruptor、Linux环性缓存、都用到了循环并发队列。Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。
跟栈一样,队列可以用数组来实现,也可以用链表来实现。
用数组实现的栈叫做顺序栈;用链表实现的栈叫做链式栈。
对于顺序队列的实现:队列的实现需要两个指针,一个是head指针,指向队头;一个是tail指针,指向队尾;
2.1 顺序队列
实现如下图:
2.2 链式队列
如下:
2.3 循环队列
用数组实现队列的时候,当tail==n时,会有数据搬移操作。那么有办法能避免数据搬移吗?这里讲下循环队列。
循环队列,如何判断队空和队满呢?
队列为空的判断条件依然是head==tail。队列为满的条件是(tail+1)%n=head
2.4 阻塞队列和并发队列
阻塞队列其实就是在队列基础上增加了阻塞操作。
简单来说,就是在队列为空的时候,从队头取数据会被阻塞。
因为此时还没有数据可取,直到队列中有了数据才能返回;
如果队列已经满了,那么插入数据的操作就会被阻塞,直到队列中有空闲位置后再插入数据,然后返回。
如图:
其实上面就是一个“生产者-消费者模型”。我们可以用一个阻塞队列,实现它。
这种基于队列实现的“生产者-消费者模型”,可以有效的协调生产和消费的速度。
当生产者生产数据的速度过快,消费者来不及消费时,存储数据的队列很快就会满了。
这个时候,生产者就阻塞等待,直到消费者消费了数据,生产者才会被唤醒继续生产。
而且,基于阻塞队列,我们可以协调生产者和消费者的个数,来提高数据的处理效率。
比如前面的例子,我们可以多配置几个消费者,来应对一个生产者。
在多线程情况下,会有多个线程同时操作队列,这个时候会有安全问题。那么如何实现一个线程安全的队列呢?
线程安全的队列,叫做并发队列。
最简单直接的实现方式是直接在enqueue()、dequeue()方法上加锁,
但是粒度锁大并发度会比较低,同一时刻仅允许一个存或者取操作。
对此,我们一般有两种处理策略。
对于第二种方式,那么怎么存储排队的请求呢?
为了公平的处理每个请求,先进者先服务,所以我们用队列这种数据结构来存储排队。
但是队列的实现又有基于链表和数组这两种方式,这两种实现方式对于排队请求有什么区别?
1 基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),
但是会导致过多的请求排队等待,请求处理的响应时间过长。
所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。
2 而基于数组实现的有界队列(bounded queue),队列的大小有限,
所以线程池中的排队的请求超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就更合理。
不过,要设置一个合理的队列大小,也是非常讲究的。
队列太大导致等待的请求太多,队列太小,会导致无法充分利用系统资源,发挥最大性能。
队列除了应用在线程池请求排队的场景之外,队列可以应用在任何有限资源池中,用于排队请求,比如数据库连接池。
课后思考:
1. 除了线程池这种池结构会用到队列排队请求,你还知道有哪些类似的池结构或者场景中会用到队列的排队请求呢?
答:数据库连接池,任务队列
2.关于如何实现无锁并发队列,你怎么看?