阅读com.sun.jmx.remote.internal.ArrayQueue源码Note

原创
2020/04/25 23:02
阅读数 104

ArrayQueue

  1. 底层使用数组存储
  2. 添加时放置于tail指定的位置,从尾部开始添加,尾部满时,继续从头部开始添加,直到head位置,此时队列已满
  3. head 和tail 操作可以在数组上循环。
    public boolean add(T o) {
        queue[tail] = o;
        int newtail = (tail + 1) % capacity;
        if (newtail == head)
            throw new IndexOutOfBoundsException("Queue full");
        tail = newtail;
        return true; // we did add something
    }
  1. 移除时,只能从头部移除
    // 构建一个指定初始容量的ArrayQueue,数据为空
    public ArrayQueue(int capacity) {
        // 容量,resize
        this.capacity = capacity + 1;
        // 存储数据
        this.queue = newArray(capacity + 1);
        // 头部元素
        this.head = 0;
        // 尾部元素
        this.tail = 0;
    }
    // 获取队列的大小
    public int size() {
        // Can't use % here because it's not mod: -3 % 2 is -1, not +1.
        int diff = tail - head;
        if (diff < 0)
            diff += capacity;
        return diff;
    }   
    // 获取指定位置的元素
    public T get(int i) {
        int size = size();
        if (i < 0 || i >= size) {
            final String msg = "Index " + i + ", queue size " + size;
            throw new IndexOutOfBoundsException(msg);
        }
        //head
        int index = (head + i) % capacity;
        return queue[index];
    } 

示例

X 代表未填充元素,E代表填充元素,h代表头部元素位置;t代表尾部元素位置

  1. 初始化 , capacity 指定为4
位置 位置 位置 位置 位置
X X X X X
h        
t        
  1. 添加4元素
位置 位置 位置 位置 位置
E E E E X
h        
        t
  1. 移除二个元素
位置 位置 位置 位置 位置
X X E E X
    h    
        t
  1. 添加一个元素
位置 位置 位置 位置 位置
X X E E E
    h    
t        
  1. 添加一个元素
位置 位置 位置 位置 位置
E X E E E
    h    
  t      
  1. 移除三个元素
位置 位置 位置 位置 位置
E X X X X
h        
  t      

欢迎关注我的公众号:

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部