字节二面：了解环形队列吗？有哪些使用场景？-平芜编程栈

在日常开发工作中，环形队列的使用并不多，但其实环形队列是一个很有用的数据结构，而且有不少使用场景。今天来聊一聊环形队列的使用场景。

1.环形队列

队列这个数据结构最大的特点就是先进先出，它可以有两种实现方式，无界队列一般用链表来实现，有界队列可以用数组来实现。

但使用数组来实现队列，有新数据插入时，需要搬移元素，造成额外的性能开销。要解决数据搬移的问题，我们可以考虑使用环形队列。

下图是一个 8 个元素的环形队列：

环形队列的特点是写完最后一个元素后接着从头开始写，读元素也一样。初始状态，head 和 tail 都指向数据下标是 0 的位置。每写入一个元素，tail 往后移动一个指针，每读取一个元素，head 指针往后移动一个指针。如果写入的速度超过了读取速度一圈，未读取的元素就会被覆盖。

下图是用数组来表示的环形队列，尾节点指向头结点，实现首尾相连：

在上图中，head 所在数组位置元素值是 3，tail 所在数组位置元素值是 7。这时如果我们插入一个新元素 a，环形队列变成下图：

那环形队列代码怎么实现呢？这里给出一个示例代码：

public class CircleQueue { //实现环形队列的数组 private String[] items; //数组大小 private int size; //数组元素数量 private int count = 0; private int head = 0; private int tail = 0; //申请一个指定容量的队列 public CircleQueue(int size){ items = new String[size]; this.size = size; } public boolean enqueue(String item){ if ((tail + 1) % size == head){ //队列满 return false; } items[tail] = item; tail = (tail + 1) % size; count++; return true; } public String dequeue(){ String item = null; //队列空 if(head == tail){ return item; } item = items[head]; head = (head + 1) % size; count--; return item; } }

在上面的例子中，如果队列满了，就会写入消息失败。不过在实际使用场景中，有些场景如果队列满了，可以覆盖掉当前 tail 位置上的元素，tail 继续往下一个位置移动。这个适用于丢失数据影响较小的场景，比如记录日志。

2.使用场景

2.1 延时消息

在消息队列中，延时消息的使用场景很多，比如超过 30 分钟关闭未支付订单。主流消息队列实现延时关闭订单的方式是采用线程轮询的方式来判断订单是否超过 30 分钟，如果超过则关闭订单。

在 RocketMQ 5.0 之前，4.x 版本定义了 18 个延时级别：

private String messageDelayLevel = "1s 5s 10s 30s 1m 2m 3m 4m 5m 6m 7m 8m 9m 10m 20m 30m 1h 2h";

Broker 收到消息后，会根据延时级别把消息保存到同一个 Topic（SCHEDULE_TOPIC_XXXX）下的不同 queue。然后启动 18 个线程来对每个 queue 做轮询判断，如果时间到了，就把消息投递到原始队列，等待 Consumer 来拉取。

这样的设计存在一个问题，延时级别只有 18 个，不太灵活，对于大型的复杂业务系统，延时级别可能成千上万，这种设计无法满足。

为了解决这个设计问题，RocketMQ 5.0 基于时间轮算法引入了定时消息。如下图：

图中定义了一个 60s 的时间轮，时间轮上有一个指向当前时间的指针定时地移动到下一秒时间。

这样不用去轮询所有消息，每一个时间节点上的消息用链表串起来，当时间轮上的指针移动到当前的时间时，这个时间节点上符合条件的消息就交给异步线程来处理。

如果一个消息的延时时间超过 60s，比如 130s，该怎么设置呢？在每个时间轮节点增加一个 round 字段，记录时间轮转动的圈数，对于延时 130s 的消息，round 就是 2，放在第 10 个时间刻度的链表中。时间轮每转动一圈，round 值减一，这样当时间轮转到一个节点，处理节点上的消息时，首先判断 round 值是否等于 0，如果等于 0，则把这个消息从链表中移出交给异步线程执行，否则将 round 减 1 继续检查后面的任务。