图解白菜用到的循环队列

实现了用循环队列存QQ消息后，就七八个月没有管（能用的代码才是好代码），以至于写上简历被问到之后支支吾吾说不出……

这个队列比较特殊，只有入队和遍历，没有写出队（业务用不到）。
代码如下（CqMsg为反序列化出来的实体类，记载着QQ号、消息体、发送时间等信息）：

public class MsgQueue {

    private int start = 0;
    private int end = 0;
    private int len = 0;
    private int N=100;
    
    private CqMsg[] msgs = new CqMsg[N];
    public MsgQueue(){}
    public MsgQueue(int N) {
        this.N=N;
        msgs = new CqMsg[N];
    }
    public void addMsg(CqMsg msg) {
        len++;
        if (len >= N) {
            len = N;
            start++;
        }
        if (end == N) {
            end = 0;
        }
        if (start == N) {
            start = 0;
        }
        msgs[end] = msg;
        this.msg = msg;
        end++;
    }
    
      
     public ArrayList<CqMsg> getMsgsByQQ(Long QQ) {
        ArrayList<CqMsg> result = new ArrayList<>();
        if (start < end) {
            for (int i = 0; i < end; i++) {
                if (QQ.equals(msgs[i].getQQ())) {
                    result.add(msgs[i]);
                }
            }
        } else {
            for (int i = end; i < msgs.length; i++) {
                if (QQ.equals(msgs[i].getQQ())) {
                    result.add(msgs[i]);
                }
            }
            for (int i = 0; i < start - 1; i++) {
                if (QQ.equals(msgs[i].getQQ())) {
                    result.add(msgs[i]);
                }
            }
        }
        return result;

    }
}    

一开始我创建了一个数组（容量由构造器指定），同时定义两个整数作为坐标变量，再加一个表示队列当前长度的变量，大概是这样的：

length = 0

null	null	null	null	null	null
Start
End

之后每当收到新消息，都将消息插入到end坐标上，之后将end++，同时length++，直到数组装满。

在数组装满后，队列是这样的：

length = 5

消息1	消息2	消息3	消息4	消息5	消息6
Start
				End

当有下一条消息进入队列时，尝试将队列长度增加：

length++

随即满足下方if语句块的判定，将length重置为数组长度，并且将起始点右移：

if (len >= N) {
    len = N;
    start++;
}

length = 5

进入下一个if块：

if (end == N) {
    end = 0;
}

最后把结果插入到end上，之后end++：

消息7	消息2	消息3	消息4	消息5	消息6
Start
End

不断的插入消息后，Start也会达到数组最右端，此时的队列如图：

消息7	消息8	消息9	消息10	消息11	消息6
				Start
			End

此时插入消息的逻辑如下：

首先依旧将length重置为当前数组长度；

但是不会进第二个if块，直接进第三个：

if (start == N) {
    start = 0;
}

这之后执行end++，会回到数组第一次装满时候队列的样子：

消息7	消息8	消息9	消息10	消息11	消息12
Start
				End

每次遍历时，只需要从end→length，再从0→start就行，是一次O(n)的操作。

而插入时，则只需要O(1)（判断几个数字的大小、给数组某个位置赋值）。

如改用纯数组实现，在数组满后，插入消息需要O(n)的时间。

若改用链表，则可以使用迭代器达到与循环队列相同的复杂度：

有新消息时，丢弃头部消息，在尾部追加消息，也是O(1)的操作。

遍历时， 并不使用传统的for+get方法（每次获取链表的某个位置的值代价都是O(n)），而是使用迭代器，可以达到O(n)的时间复杂度。