有界循环队列

  1/**
  2 * 有界循环队列，实际上是循环数组实现。
  3 * 参考：<a href=
  4 * "http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/8-List/array-queue2.html">
  5 * Implementing a Queue using a circular array</a>
  6 * <p>
  7 * 另一种实现思路：<a href="https://www.baeldung.com/java-ring-buffer">Implementing a
  8 * Ring Buffer in Java</a>
  9 * <p>
 10 * 上述两种思路的主要差别是：
 11 * <ul>
 12 * <li>
 13 * read(入队)指针的指向不同。前者指向的是空槽，而后者指向的是队尾的元素；
 14 * </li>
 15 * <li>
 16 * 指针的内涵不同，前者对应的是数组的index，而后者对应的是入队/出队的次数；
 17 * </li>
 18 * </ul>
 19 * <p>
 20 * 这种设计的差别，最终导致队列满/空判断上面的差异。
 21 * <p>
 22 * 
 23 * <pre>
 24 *     循环队列的数据简单模型图——有8个slot的定容数组：此时count = 4
 25 *     (o代表此槽为空，N为数组容量）
 26 *         =========================================================
 27 *            [0]    [1]    [2]    [3]    [4]   [5]    [6]    [7]
 28 *         ｜  o  ｜  o  ｜  12 ｜  34  ｜ 65  ｜ 26  ｜  o  ｜  o  ｜
 29 *                         read                       write
 30 *         =========================================================
 31 * </pre>
 32 * <p>
 33 * 在之前的顺序队列中，如果<code>write = N && read!=0</code>的情况下，
 34 * 数组的空间可以重复利用，当时的处理办法是对数组中的元素进行"整理"；
 35 * <p>
 36 * 在循环队列中，我们无需再这样做，队列中的slot可以重复使用，
 37 * slot的值可以一直被覆盖写入，而队列真正
 38 * 需要关心的内容是<b>read</b>和<b>write</b>指针：<br>
 39 * 
 40 * <pre>
 41 *     当循环队列入队时，
 42 *         =========================================================
 43 *            [0]    [1]    [2]    [3]    [4]   [5]    [6]    [7]
 44 *         ｜  o  ｜  o  ｜  12 ｜  34  ｜ 65  ｜ 26  ｜  19  ｜  o  ｜
 45 *                         read                               write
 46 *         =========================================================
 47 *         =========================================================
 48 *            [0]    [1]    [2]    [3]    [4]   [5]    [6]    [7]
 49 *         ｜  o  ｜  o  ｜  12 ｜  34  ｜ 65  ｜ 26  ｜  19  ｜  32  ｜
 50 *           write         read
 51 *         =========================================================*
 52 *      write指针后移一位，即<code>write +=write</code>。
 53 *      不过，当write指针指向数组的末尾时，write该如何计算呢？
 54 *      事实上，由于循环数组的slot一直在重用，故write的取值总介于[0，N)之间，
 55 *      因此当有元素入队时，可用
 56 *      <code>write = (write +1) % N</code>计算得到write指针指向。
 57 *
 58 *      同理，当循环队列有元素出队时，
 59 *         =========================================================
 60 *            [0]    [1]    [2]    [3]    [4]   [5]    [6]    [7]
 61 *         ｜  o  ｜  o  ｜  12 ｜  34  ｜ 65  ｜ 26  ｜  19  ｜  o  ｜
 62 *                                read                        write
 63 *         =========================================================
 64 *       和入队类似，<code>read = (read + 1) % N</code>
 65 * </pre>
 66 * </p>
 67 * 不难发现，如果read指针追上write指针，即read==write时，队列为空；
 68 * 反之，若write指针追上read指针，即read==write时，
 69 * 队列为满。<b>如何消除歧义？</b>
 70 * 
 71 * <p>
 72 * 有2种办法消除歧义：
 73 * <ul>
 74 * <li>1. 引入整型变量{@link CircularBuffer#count}，用于实时统计队列中的元素个数</li>
 75 * <li>
 76 * 2. 取个巧，将write指针对应的slot闲置，如果发现write指针的下一个指针是read指针的时候，
 77 * 即认为队列满了。这种情况下，队列实际的容量为N-1。
 78 * </li>
 79 * </ul>
 80 * <p>
 81 * 如果按照方法2，队列为空的判断条件不变，仍为<code>read == write</code>；
 82 * 但是队列为满的条件变了，即若
 83 * <code>
 84 *     read == (write + 1) % N
 85 * </code>
 86 * 时，认为队列已满。
 87 * <p>
 88 * 循环数组的效率很高，空间复杂度为O(1)，入队和出队的时间复杂度均为O(1)。
 89 *
 90 * @author wangy
 91 * @version 1.0
 92 * @date 2021/7/1 / 10:52
 93 * @see ArrayQueue
 94 * @see CircularBufferVariety
 95 */
 96public class CircularBuffer {
 97    private int[] data;
 98
 99    private int read;
100
101    private int write;
102    // 队列中元素计数
103    private int count;
104
105    public CircularBuffer(int cap) {
106        this.data = new int[cap];
107        this.read = this.write = this.count = 0;
108    }
109
110    boolean isFull() {
111        return (write + 1) % data.length == read;
112    }
113
114    boolean isEmpty() {
115        return read == write;
116    }
117
118    int enQueue(int e) {
119        if (isFull())
120            throw new RuntimeException("Queue full!");
121        data[write] = e;
122        write = (write + 1) % data.length;
123        return e;
124    }
125
126    int deQueue() {
127        if (isEmpty())
128            throw new RuntimeException("Queue empty!");
129        int e = data[read];
130        read = (read + 1) % data.length;
131        return e;
132    }
133
134    void printAll() {
135        System.out.println("数组：" + Arrays.toString(data));
136        System.out.print("队列：[");
137        // 从队头到队尾
138        for (int i = read; i % data.length != write; i++) {
139            System.out.print(data[i % data.length] + " ");
140        }
141        System.out.println("]");
142    }
143
144    public static void main(String[] args) {
145        // 实际上，仅可以入队3个元素
146        CircularBuffer cb = new CircularBuffer(4);
147        cb.enQueue(1);
148        cb.deQueue();
149        cb.enQueue(2);
150        cb.enQueue(3);
151        cb.enQueue(5);
152        cb.deQueue();
153        cb.enQueue(7);
154        cb.printAll();
155        // full exception
156        cb.enQueue(9);
157    }
158}