玩转数据结构与算法：探索环形队列的魅力

class CircleArray { // 数组最大容量 private int maxSize; // front指向队列的第一个元素，也就是说arr[front]，初始值为0 private int front; // rear指向队列的最后一个元素的后一个位置，因为希望空出一个位置作为约定，初始值为0 private int rear; // 存放数据 private int arr[]; public CircleArray(int maxSize) { this.maxSize = maxSize; arr = new int[maxSize]; } // isFull public boolean isFull() { return (rear + 1) % maxSize == front; } // isEmpty public boolean isEmpty() { return front == rear; } // addQueue public void addQueue(int data) { if (isFull()) { throw new RuntimeException("full"); } // 直接将数据加入即可 arr[rear] = data; // 将rear后移一位，这里必须考虑取模，因为如果rear到最后一位了，但是前面还有空间，所以需要取模,否则数组越界 rear = (rear + 1) % maxSize; } // getQueue public int getQueue() { if (isEmpty()) { throw new RuntimeException("empty"); } // 这里需要分析出front是指向队列的第一个元素 // 1.先把front对应的值保存到一个临时变量 // 2.将front后移,取模，否则数组越界 // 3.将临时保存的变量返回 int value = arr[front]; front = (front + 1) % maxSize; return value; } // showQueue public void showQueue() { if (isEmpty()) { return; } // 从front开始遍历，遍历多少个元素？ for (int i = front; i < front + size(); i++) { System.out.printf("arr[%d]=%d\n", i % maxSize, arr[i]); } } // 获取当前队列有效数据的个数 public int size() { // 1, 3, 0 = 1 return (rear + maxSize - front) % maxSize; } // headQueue public int headQueue() { if (isEmpty()) { throw new RuntimeException("empty"); } return arr[front]; } }