前面,我们学习了 栈的实现及应用 ,本篇我们来学习一下最后一种线性表——队列。
队列是我们日常开发中经常会用到的一种数据结构,我们经常使用队列进行异步处理、系统解耦、数据同步、流量削峰、缓冲、限流等。例如,不是所有的业务都必须实时处理、不是所有的请求都必须实时反馈结果给用户、不是所有的请求都必须100%处理成功、不知道谁依赖“我”的处理结果、不关心其他系统如何处理后续业务、不需要强一致性,只需保证最终一致性即可、想要保证数据处理的有序性等等,这些问题都考虑使用队列来解决。
## 队列
### 定义
队列与 栈 一样,都是操作受限的线性表数据结构。队列从一端插入数据,然后从另一端取出数据。插入数据的一端称为”队尾“,取出数据的一端称为”队头“,如图所示:
特点
- FIFO(First In First Out):先进先出原则
分类
与 栈 一样,队列也分为顺序队列与链式队列,分别使用数组与链表来实现。
链式队列
链式队列实现比较简单,使用单链表即可实现,如果所示:
### 代码实现
1 | package one.wangwei.algorithms.datastructures.queue.impl; |
> 源码
基于链表的实现方式,可以实现一个支持无限排队的无界队列(unbounded queue),但是可能会导致过多的请求排队等待,请求处理的响应时间过长。所以,针对响应时间比较敏感的系统,基于链表实现的无限排队的线程池是不合适的。
## 顺序队列
顺序队列采用数组实现,数组的实现有两种方式,一种是顺序式的,一种是循环数组实现。
### 顺序队列
当队列尾部没有剩余空间后,需要集中进行一次数据搬迁腾出空间,才能继续进行入队操作。如图所示:
### 循环队列
顺序队列会存在数据搬迁的问题,对入队操作有性能方面的影响。我们可以采用循环数组的方式来解决这一问题,如图所示:
当队尾无存储空间且队列未满时,我们可以将其存储到数组的前半部分剩余的空间去。
代码实现
循环队列的实现关键在于队列为空和为满时的状态判断:
- 当队列为空时:
rear == front
- 当队列为满时:
front == (rear + 1) % array.length
,队满时,会浪费一个数组的存储空间。
代码如下:
1 | package one.wangwei.algorithms.datastructures.queue.impl; |
基于数组实现的有界队列(bounded queue),队列的大小有限,当请求数量超过队列大小时,接下来的请求就会被拒绝,这种方式对响应时间敏感的系统来说,就相对更加合理。不过,设置一个合理的队列大小,也是非常有讲究的。队列太大导致等待的请求太多,队列太小会导致无法充分利用系统资源、发挥最大性能。