循环数组的另一种实现

 1/**
 2 * 队列的循环数组另一种实现，参考：
 3 * <a href="https://www.baeldung.com/java-ring-buffer">
 4 * Implementing a RingBuffer in Java</a>
 5 *
 6 * <p>
 7 * 这种方法的解决思路是：
 8 * <ul>
 9 * <li>
10 * 1.
11 * 引入2个变量，{@link CircularBufferVariety#readSequence}和
12 * {@link CircularBufferVariety#writeSequence},
13 * 分别记录元素入队和出队的次数；初始化时，readSequence = 0， writeSequence =
14 * -1；writeSequence=-1的好处在于其实际上
15 * 相当于<b>直接指向</b>了队列队尾元素的index；
16 * </li>
17 * <li>
18 * 2. 为了循环使用数组中的slot，可以使用<code>writeSequence % N</code>取模
19 * 的方式找到当前队列队尾的元素对应的index；
20 * </li>
21 * <li>
22 * 3. 当readSequence > writeSequence时，即可认为队列为空；
23 * </li>
24 * <li>
25 * 4. 当（writeSequence - readSequence）+ 1 ==
26 * {@link CircularBufferVariety#data}.length时，即可认为队列已满；
27 * </li>
28 * </ul>
29 *
30 * @author wangy
31 * @version 1.0
32 * @date 2021/7/1 / 14:53
33 * @see CircularBuffer
34 */
35public class CircularBufferVariety {
36    private int[] data;
37    // 出队次数
38    private int readSequence;
39    // 入队次数
40    private int writeSequence;
41    // 队列中元素的个数，等于 writeSequence - readSequence + 1
42    private int count;
43
44    public CircularBufferVariety(int cap) {
45        this.data = new int[cap];
46        this.readSequence = 0;
47        this.writeSequence = -1;
48        this.count = 0;
49    }
50
51    boolean isEmpty() {
52        return readSequence > writeSequence;
53    }
54
55    boolean isFull() {
56        return writeSequence - readSequence + 1 == data.length;
57    }
58
59    int enQueue(int e) {
60        if (isFull())
61            throw new RuntimeException("Queue full!");
62        data[++writeSequence % data.length] = e;
63        return e;
64    }
65
66    int deQueue() {
67        if (isEmpty())
68            throw new RuntimeException("Queue empty!");
69        return data[readSequence++ % data.length];
70    }
71
72    void printAll() {
73        System.out.println("数组：" + Arrays.toString(data));
74        System.out.print("队列：[");
75        // 从队头到队尾
76        for (int i = readSequence; i <= writeSequence; i++) {
77            System.out.print(data[i % data.length] + " ");
78        }
79        System.out.println("]");
80    }
81
82    public static void main(String[] args) {
83        CircularBufferVariety cb = new CircularBufferVariety(4);
84        cb.enQueue(1);
85        cb.deQueue();
86        cb.enQueue(2);
87        cb.enQueue(3);
88        cb.enQueue(5);
89        cb.deQueue();
90        cb.enQueue(7);
91        cb.printAll();
92        cb.enQueue(9);
93        cb.printAll();
94        // full exception
95        cb.enQueue(11);
96    }
97}