数据结构之「队列」
什么是队列？
队列（queue）是只允许在一端进行插入操作，而在另一端进行删除操作的线性表。是一种先进先出（First In First Out）的线性表，简称 FIFO。允许插入的一端称为队尾，允许删除的一端称为队头。
队列有 2 种方式来存储：数组 和 链表。
数组我们都知道它是预先分配好长度的，因此会出现溢出现象，而且删除元素需要向队头移动一个位置，时间复杂度就变成 O(n)。因此，需要一种新的方式来解决这个问题，那就是循环队列。
队列的这种头尾相接的顺序存储结构称为循环队列。为了避免队列删除元素需要移动整个队列，使得队头和队尾可以在数组中循环变化。解决了移动元素的时间损耗，使得本来删除是 O(n) 的时间复杂度变成了 O(1)。
1. 数组式队列
申请一片连续的存储空间，并设置两个指针进行管理。一个是队头指针front，它指向队头元素；另一个是队尾指针rear，它指向下一个入队元素的存储位置。一般是实现循环队列，队头和队尾会随着入队和出队的变化而变化的。例如 JDK 中 ArrayBlockingQueue 就是基于循环队列来实现的。不过它会有溢出现象，一般解决方案是如果队列满了，设置入队等待时间或者返回入队不成功。一般在确定元素个数情况下使用，如果不确定元素个数，建议使用链表式队列。
2. 链表式队列
它就是基于链表存储结构的队列，可以动态的创建和删除元素，不用关心队列的长度，因此不用担心溢出现象。新元素插入到队尾，读取的时候从队头开始，每次读取一个元素，释放一个元素，这就是所谓的动态创建和动态删除。
队列有什么用？
1. 保证输入顺序
比如吃饭排队，先找服务员拿个号码，上面会写着前面还有 n 桌，这就相当于服务员把你加入了她们店的队列中，当有空位置时，就直接叫你入座吃饭，当没有空位子时，要么排队等候，要么换一家吃饭。这就是队列的用处。
2. 解耦
在系统设计中，好的设计是低耦合，高内聚。意思就是一个系统只做一件事情，把一件事情做好。既方便代码维护，又方便扩展。比如又一个下单的场景，用户下单之后需要加积分，需要给各种优惠券等等。我们就可以利用队列来解偶，但真实使用一般是用开源的消息队列，如Rocket MQ,Kafka 等等。
3. 提升系统吞吐量
就拿上面订单来说，本来以前是用户下单，给用户添加积分，给用户发优惠券是一起处理成功后返回的。现在只是处理下单，然后告诉某某系统，给某某用户加积分，给某某用户发优惠券了，它自己并不真正做这个动作，所以会提升系统响应，当需要保证最终一致性。一般也是用开源的消息队列来完成的。
队列怎么实现？
这里是基于数组的循环队列实现，也就是 JDK 的 ArrayBlockingQueue。有兴趣的朋友也可以看看基于链表的 LinkedBlockingQueue 的实现。
存储结构
public class ArrayBlockingQueue<E> {
//用数组来存储元素
Object[] items;
//数组里出队的下标
int takeIndex;
//入队的下标
int putIndex;
//元素个数
int count;
}入队
public boolean offer(E e) {
//加入数组满了，则返回入队失败
if (count == items.length) {
return false;
} else {
//获得当前数组
Object[] items = this.items;
//把元素 e 加入到队尾
items[putIndex] = e;
//判断是不是队尾是不是倒数第二个元素
//是的话把下标为 0 置为队尾，说明一圈了
if (++putIndex == items.length) {
putIndex = 0;
}
//总数加一
count++;
return true;
}
}出队
public E poll() {
//空队列则返回 null
if (count == 0) {
return null;
} else {
//获取当前数组
Object[] items = this.items;
//获取队头元素
E item = (E) items[takeIndex];
//置空
items[takeIndex] = null;
//重置队头为下标 0；
if (++takeIndex == items.length) {
takeIndex = 0;
}
//总数减一
count--;
return item;
}
}总结
队列的作用还是很大的，比如保证输入顺序，解偶，提升系统吞吐量等等，都基于队列的原理来实现的。队列有数组式队列和链表式队列。数组式队列就是基于数组存储结构来实现的，数组的优缺点它全有。链表式队列就是基于链表存储结构来实现的，它也包含来链表的优缺点。所以在使用时可以根绝业务需求来选择最优的方案。
PS:
清山绿水始于尘，博学多识贵于勤。
我有酒，你有故事吗？
微信公众号：「清尘闲聊」。
欢迎一起谈天说地，聊代码。
