Java集合ArrayDeque类实例分析

Java集合ArrayDeque类实例分析

前言

ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实习了部分集合通用的方法,其实现了Collection接口),其实现的接口Deque接口中定义了双端队列的主要的方法,比如从头删除,从尾部删除,获取头数据,获取尾部数据等等。

public class ArrayDeque<E> extends AbstractCollection<E>
   implements Deque<E>, Cloneable, Serializable

ArrayDeque基本特征

就其实现而言,ArrayDeque采用了循环数组的方式来完成双端队列的功能。

1. 无限的扩展,自动扩展队列大小的。(当然在不会内存溢出的情况下。)
2. 非线程安全的,不支持并发访问和修改。
3. 支持fast-fail.
4. 作为栈使用的话比比栈要快.
5. 当队列使用比linklist要快。
6. null元素被禁止使用。

ArrayDeque实现方法解读

最小初始化容量限制

 /**
  * The minimum capacity that we'll use for a newly created deque.
  * Must be a power of 2.
  */
 private static final int MIN_INITIAL_CAPACITY = 8;

这里根据注释中提及,必须是2的幂次。仅仅通过这里是不会知道为何要这样设定的。

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

addFirst方法中使用了head-1和length-1相与的形式来计算,那么,length-1这里是多少,因为规定了length必须是2的幂次,所以length-1后二进制低位将全部为1,然后与head-1相与相当于对其进行取模。

扩容

之所以说该ArrayDeque容量无限制,是因为只要检测到head==tail的时候,就直接调用doubleCapacity方法进行扩容。
这个时候将数组展开,head和tail指向的是同一个位置,那么,因为是循环数组,所以head左边可能存在一部分元素为p个,右边也可能存在一部分数据r=n-p个,右边的部分复制到从0到r,左边的部分复制到从r到结束。这样原来的数据从0开始往下排列。

 private void doubleCapacity() {
  assert head == tail;
  int p = head;
  int n = elements.length;
  int r = n - p; // number of elements to the right of 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 = (E[])a;
  head = 0;
  tail = n;
 }

删除元素

删除元素的基本思路为确定那一侧的数据少,少的一侧移动元素位置,这样效率相对于不比较更高些,然后,判断head是跨越最大值还是为跨越最大值,继而可以分两种不同的情况进行拷贝。但是该方法比较慢,因为存在数组的拷贝。

private boolean delete(int i) {
  checkInvariants();
  final E[] elements = this.elements;
  final int mask = elements.length - 1;
  final int h = head;
  final int t = tail;
  final int front = (i - h) & mask;
  final int back = (t - i) & mask;

  // Invariant: head <= i < tail mod circularity
  if (front >= ((t - h) & mask))
   throw new ConcurrentModificationException();

  // Optimize for least element motion
  // 为了最小的拷贝数据
  if (front < back) {
   // 递增的顺序时
   if (h <= i) {
    // 删除部分前面的向后移动
    System.arraycopy(elements, h, elements, h + 1, front);
   } else { // Wrap around
    // 跨越最小与最大值
    // 分两次拷贝
    System.arraycopy(elements, 0, elements, 1, i);
    // 最大的地方单独处理
    elements[0] = elements[mask];
    // 前面的部分向后移动一位
    System.arraycopy(elements, h, elements, h + 1, mask - h);
   }
   elements[h] = null;
   head = (h + 1) & mask;
   return false;
  } else {
   // 递增的顺序时
   if (i < t) { // Copy the null tail as well
    // 拷贝i后面的部分数据前置
    System.arraycopy(elements, i + 1, elements, i, back);
    tail = t - 1;
   } else { // Wrap around
    // 跨越中间最大值的时候
    // 后面向前拷贝
    // 0处的值单独处置放在最大的下标处
    // 后面的部分从1开始向前移动一个,原来的1在0处
    System.arraycopy(elements, i + 1, elements, i, mask - i);
    elements[mask] = elements[0];
    System.arraycopy(elements, 1, elements, 0, t);
    tail = (t - 1) & mask;
   }
   return true;
  }
 }

获取并删除元素

这里在举个简单点的例子,中间判断是不是null,可以看出该队列不支持null,通过把其值设为null就算是将其删除了。然后head向递增的方向退一位即可。

 public E pollFirst() {
  int h = head;
  E result = elements[h]; // Element is null if deque empty
  if (result == null)
   return null;
  elements[h] = null;  // Must null out slot
  head = (h + 1) & (elements.length - 1);
  return result;
 }

感谢阅读,希望能帮助大家,谢谢大家对本站的支持!

(0)

相关推荐

  • java.util.ArrayDeque类使用方法详解

    本文为大家介绍了java.util.ArrayDeque类使用方法,供大家参考,具体内容如下 1. ArrayDeque有两个类属性,head和tail,两个指针. 2. ArrayDeque通过一个数组作为载体,其中的数组元素在add等方法执行时不移动,发生变化的只是head和tail指针,而且指针是循环变化,数组容量不限制. 3. offer方法和add方法都是通过其中的addLast方法实现,每添加一个元素,就把元素加到数组的尾部,此时,head指针没有变化,而tail指针加一,因为指针是

  • Java ArrayDeque使用方法详解

    题目要求为: 卡拉兹(Callatz)猜想: 对任何一个自然数n,如果它是偶数,那么把它砍掉一半:如果它是奇数,那么把(3n+1)砍掉一半.这样一直反复砍下去,最后一定在某一步得到n=1.当我们验证卡拉兹猜想的时候,为了避免重复计算,可以记录下递推过程中遇到的每一个数.例如对n=3进行验证的时候,我们需要计算3.5.8.4.2.1,则当我们对n=5.8.4.2进行验证的时候,就可以直接判定卡拉兹猜想的真伪,而不需要重复计算,因为这4个数已经在验证3的时候遇到过了,我们称5.8.4.2是被3"覆盖

  • Java ArrayDeque实现Stack的功能

    在J2SE6引入了ArrayDeque类,它继承了Deque(双向队列)接口,使用此类可以自己实现java.util.Stack类的功能,去掉了java.util.Stack的多线程同步的功能. 例如创建一个存放Integer类型的Stack,只要在类中创建一个ArrayDeque类的变量作为属性,之后定义的出栈.入栈,观察栈顶元素的操作就直接操作ArrayDeque的实例变量即可. import java.util.ArrayDeque; import java.util.Deque; pub

  • Java集合ArrayDeque类实例分析

    Java集合ArrayDeque类实例分析 前言 ArrayDeque类是双端队列的实现类,类的继承结构如下面,继承自AbastractCollection(该类实习了部分集合通用的方法,其实现了Collection接口),其实现的接口Deque接口中定义了双端队列的主要的方法,比如从头删除,从尾部删除,获取头数据,获取尾部数据等等. public class ArrayDeque<E> extends AbstractCollection<E> implements Deque&

  • java中object类实例分析

    问:什么是Object类? 答:Object类存储在java.lang包中,是所有java类(Object类除外)的终极父类.当然,数组也继承了Object类.然而,接口是不继承Object类的,Object类不作为接口的父类. 下面,我们就通过实例,对object进行分析 public class ObjectStu { /*Object类:java里所有类的父类,顶层的类 *equals:判断两个对象是否"相等"; *hashcode:返回一个对象的哈希码值,是一个整数 *因为之后

  • Java集合源码全面分析

    Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组.链表.栈.队列.集合.哈希表等.学习Java集合框架下大致可以分为如下五个部分:List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections). 从上图中可以看出,集合类主要分为两大类:Collection和Map. Collection是List.Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Se

  • java编程约瑟夫问题实例分析

    一.简介 约瑟夫问题(有时也称为约瑟夫斯置换,是一个出现在计算机科学和数学中的问题.在计算机编程的算法中,类似问题又称为约瑟夫环.又称"丢手绢问题".) 例子: len个人围成一个圈,玩丢手绢游戏.从第k个人开始,从1开始数数,当数到m时,数m的人就退出圈子,当圈子只剩下一个人为止. 问题分析与算法设计 约瑟夫问题并不难,但求解的方法很多:题目的变化形式也很多.这里给出一种实现方法. 题目中len个人围成一圈,因而启发我们用一个循环的链来表示,可以使用结构数组来构成一个循环链.结构中有

  • Java集合框架源码分析之LinkedHashMap详解

    LinkedHashMap简介 LinkedHashMap是HashMap的子类,与HashMap有着同样的存储结构,但它加入了一个双向链表的头结点,将所有put到LinkedHashmap的节点一一串成了一个双向循环链表,因此它保留了节点插入的顺序,可以使节点的输出顺序与输入顺序相同. LinkedHashMap可以用来实现LRU算法(这会在下面的源码中进行分析). LinkedHashMap同样是非线程安全的,只在单线程环境下使用. LinkedHashMap源码剖析 LinkedHashM

  • java日期相关类实例详解

    一.Date类 类 Date 表示特定的瞬间,精确到毫秒.用距离1970年1月1日00:00:00的毫秒数(long)类型来表示一个特定的时间点,该值可正可负. Date类中很多方法已经过时,使用Calendar来替代. 常用方法有 long getTime() void setTime(long time) public class T01Date { public static void main(String[] args) { //getTime():返回的时间是距离1970年的毫秒数.

  • Java中Swing类实例讲解

    Swing类部分画图方法讲解 定义框架 JFrame jFrame=new JFrame("标题名字"); jFrame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); //设置用户在此窗体上发起 "close" 时默认执行的操作. //有两种选择,默认是 HIDE_ON_CLOSE即点击关闭时隐藏界面. jFrame.setBounds(0,0,1200,1200); //设置框架的大小 jFrame.setVisi

  • java 集合工具类Collections及Comparable和Comparator排序详解

    目录 一.常用功能 二.Comparator比较器 三.Comparable和Comparator两个接口的区别 四.练习 五.扩展 一.常用功能 java.utils.Collections是集合工具类,用来对集合进行操作. 部分方法如下: public static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素. public static void shuffle(List<?> lis

  • Java中递归原理实例分析

    本文实例分析了Java中递归原理.分享给大家供大家参考.具体分析如下: 解释:程序调用自身的编程技巧叫做递归. 程序调用自身的编程技巧称为递归( recursion).递归做为一种算法在程序设计语言中广泛应用. 一个过程或函数在其定义或说明中有直接或间接调用自身的一种方法,它通常把一个大型复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解,递归策略只需少量的程序就可描述出解题过程所需要的多次重复计算,大大地减少了程序的代码量.递归的能力在于用有限的语句来定义对象的无限集合.   递归的三

随机推荐