环境和版本

  • Mac M1
  • IDEA 2021

  • Zulu Open JDK

    简介

  • ArrayQueue是一个循环队列，继承了AbstractList，内部通过数组实现，同时增加和删除元素不会引起内部数组的拷贝

  • 但是其功能很少，不够爽。

    源码解析

    ```java public class ArrayQueue extends AbstractList { // 构造方法 public ArrayQueue(int capacity) {

    1.   // capacity = capacity + 1 是因为在初始化的时候，队列内没有元素，此时 head = 0
    2.   // tail = 0
    3.   // 当有一个元素添加进去之后，tail就要向后偏移一位(会有一个位移差)，在这个容器中需要多
    4.   // 多放1位来存储这个tail指针
    6.   this.capacity = capacity + 1;
    7.   // 说明是数组
    8.   this.queue = newArray(capacity + 1);
    9.   this.head = 0;
    10.   this.tail = 0;

    }

    // 扩容 - 因为是数组，其大小是确定的，所以只能手动扩容 // 重新设置队列大小 public void resize(int newcapacity) {

      int size = size();
  if (newcapacity < size)
      throw new IndexOutOfBoundsException("Resizing would lose data");
  // 预留一个空间
  newcapacity++;
  if (newcapacity == this.capacity)
      return;
  T[] newqueue = newArray(newcapacity);
  for (int i = 0; i < size; i++)
      newqueue[i] = get(i);
  this.capacity = newcapacity;
  this.queue = newqueue;
  this.head = 0;
  this.tail = size;

    }

    // 创建数组 @SuppressWarnings(“unchecked”) private T[] newArray(int size) {

      return (T[]) new Object[size];

    }

    // 添加元素 public boolean add(T o) {

      // 放入到尾节点
  queue[tail] = o;
  // 计算新的未接到
  int newtail = (tail + 1) % capacity;
  // 如果 尾节点 == head 
  // 说明队列满了
  if (newtail == head)
      throw new IndexOutOfBoundsException("Queue full");
  // 设置新的尾节点下标
  tail = newtail;
  return true; // we did add something

    }

    // 删除元素 public T remove(int i) {

      // 只能移除头节点
  if (i != 0)
      throw new IllegalArgumentException("Can only remove head of queue");
  if (head == tail)
      throw new IndexOutOfBoundsException("Queue empty");
  T removed = queue[head];
  queue[head] = null;
  head = (head + 1) % capacity;
  return removed;

    }

    // 获取元素 public T get(int i) {

      // 计算size
  int size = size();
  // 如果
  if (i < 0 || i >= size) {
      final String msg = "Index " + i + ", queue size " + size;
      throw new IndexOutOfBoundsException(msg);
  }
  // 头节点+元素位置 / 容量
  int index = (head + i) % capacity;
  // 返回元素
  return queue[index];

    }

    // 计算size public int size() {

      // Can't use % here because it's not mod: -3 % 2 is -1, not +1.
  int diff = tail - head;
  // 使用尾节点减去头节点，如果小于0，则说明越界了，需要加上capacity，得到正确的大小
  if (diff < 0)
      diff += capacity;
  return diff;

    }

    // 容量大小 private int capacity; // 队列 private T[] queue; // 头节点 private int head; // 尾节点 private int tail; }

```

理解示意图