源码的魅力 - ArrayDeque 的工作原理

ArrayDeque 的工作原理(Android 7.1源码)

简介

ArrayDeque 是以循环数组形式实现的双向队列

运行原理

  1. ArrayDeque内部是使用的数组实现,并通过head以及tail两个索引来进行操作。
    ...
    transient Object[] elements;
    // non-private to simplify nested class access
    ...
    transient int head;
    ...
    transient int tail;
    ...
    public ArrayDeque() {
        //默认2的倍数
        elements = new Object[16];
    }
    //另一个指定大小的构造函数也是将elements的大小设置成2的倍数
    //由于函数太长就不再解释.
  1. offer函数的分析
  ...
  public boolean offer(E e) {
      return offerLast(e);
  }

  ...
  public boolean offerLast(E e) {
      addLast(e);
      return true
  }

  ...
  public void addLast(E e) {
     if (e == null)
         throw new NullPointerException();
     elements[tail] = e;
     if ( (tail = (tail + 1) & (elements.length - 1)) == head)
         doubleCapacity();
 }
  • 在tail位置插入数据

  • (tail + 1) 与 (elements.length - 1)相与,这一步是整个ArrayDeque设计本人认为最巧妙之处,大家可以借鉴到自己的项目中. (tail + 1) & (length - 1) 的作用就是获得tail的索引值,这一步就省去了判断是否索引越界的问题,首先ArrayDeque的大小是2的倍数,一般的Java数据结构都是这样设计的,方便计算与扩展。

  • 如何当前是数组的大小16,那么最大的索引值就是(length - 1)就是15, 如果此时(tail + 1) 正好超出索引值也就是最后位置增1 = 16,正常的结果应该是在数组的顶部也就是为0。

    tail = (1000 & 0111)
    
  • 如果tail值与head相等则翻倍扩展, 此处的位操作可以收入自己的项目中,n << 1 其实就是 n * 2。

    private void doubleCapacity() {
       assert head == tail;
       int p = head;
       int n = elements.length;
       // number of elements to the right of p
       int r = n - p;
       int newCapacity = n << 1;
       if (newCapacity < 0)
           throw new IllegalStateException("Sorry, deque too big");
       Object[] a = new Object[newCapacity];
       System.arraycopy(elements, p, a, 0, r);
       System.arraycopy(elements, 0, a, r, p);
       elements = a;
       head = 0;
       tail = n;
     }
    
  1. addFirst函数分析

  public void addFirst(E e) {
      if (e == null)
          throw new NullPointerException();
      elements[head = (head - 1) & (elements.length - 1)] = e;
      if (head == tail)
          doubleCapacity();
  }

与上面的addLast的同理,只不过head是减1,tail是加1。

  1. pollFirst与pollLast函数分析
//从队列的顶部获取数据
public E pollFirst() {
     final Object[] elements = this.elements;
     final int h = head;
     @SuppressWarnings("unchecked")
     E result = (E) elements[h];
     // Element is null if deque empty
     if (result != null) {
         elements[h] = null; // Must null out slot
         head = (h + 1) & (elements.length - 1);
     }
     return result;
 }
  //从队列底部获取数组
  public E pollLast() {
      final Object[] elements = this.elements;
      final int t = (tail - 1) & (elements.length - 1);
      @SuppressWarnings("unchecked")
      E result = (E) elements[t];
      if (result != null) {
          elements[t] = null;
          tail = t;
      }
      return result;
  }

其实原理依旧和offer相似只是获取数据而已,pollFirst直接把head的数据返回并置为空(GC可以清理),然后将head下移。pollLast由于当前的tail是指向的尾部的下一位,所以尾部的数据是tail的上一位,返回上一位数据并置空,然后将tail上移。

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,768评论 0 33
  • 一、基本数据类型 注释 单行注释:// 区域注释:/* */ 文档注释:/** */ 数值 对于byte类型而言...
    龙猫小爷阅读 4,288评论 0 16
  • ArrayDeque 原文见Java 容器源码分析之 Deque 与 ArrayDeque。 概述 ArrayDe...
    Leocat阅读 8,390评论 0 4
  • 昨天晚上孩子他爸半夜起来发现儿子还在玩手机,立马混身都充斥着焦虑和愤怒,基至坐在他的床前苦口婆心地讲道理。儿...
    王琛_Amy阅读 358评论 3 5
  • “不准你听你妈妈的话,听到没有?再听她的话,小心我揍你......” 只有九岁的盈盈心惊胆战的听着爸爸朝自己吼叫着...
    谢小蚁阅读 767评论 1 2