Java进阶--ArrayDeque双端队列完全解析

发表于 | 分类于 | | 热度: 520℃ | 浏览 次

ArrayDeque的基本用法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class DequeDemo {

	public static void main(String[] args) {
		int []arr={1,2,3,4,5,6,7,8};		
		 ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>();
		for(int i=0;i<arr.length;i++)
		{
			if((i&1)==0)
			//如果i是偶数从队头加入，否则从队尾加入
				aDeque.addFirst(arr[i]);
			else
				aDeque.addLast(arr[i]);
			
		}
		while(!aDeque.isEmpty())
		{
			aDeque.pollFirst();
			aDeque.pollLast();//此处不严谨但是由于arr的元素恰好是偶数个，本例中也不会出现问题。
		}
		
	}

}

上面这段程序简单的演示了如果对双端队列的操作，下面给出上面代码的示意图：

这里写图片描述
上图是在执行完往双端队列加元素后，双端队列中元素的存储情况，由上图可以得出以下几点结论：
①ArrayDeque 默认分配16个空间的数组。数组下标从0-15。
②addFirst(arr[i]) 操作是将元素从数组的最后一个位置向前依次存放。
③addLast(arr[i]) 操作是将元素从数组的第一个位置依次向后存放。

这里写图片描述

这里写图片描述
上面的图是分别在执行一次pollFirst() 和 pollLast() 后双端队列中的存储情况。由上图可知一下几点：
①如果单独将addFirst(arr[i]) 和pollFirst() 结合使用的话，先进的元素会后出队，后进的元素反而先队，实现的是栈的功能。
②如果单独将addLast(arr[i]) 和pollLast() 结合使用的话，先进的元素会后出队，后进的元素反而先队，实现的也是栈的功能。

再看下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class DequeDemo {

	public static void main(String[] args) {
		int []arr={1,2,3,4,5,6,7,8};		
		 ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>();
		//从双端队列的头部加元素 
		for(int i=0;i<arr.length;i++)			
			aDeque.addFirst(arr[i]);
		//从双端队列的尾部删元素
		while(!aDeque.isEmpty())
			aDeque.pollLast();		
	}

}

上面代码中依次从队头加入元素，然后在队尾删除元素下面是示意图：
这里写图片描述

使用addFirst(arr[i]) 将元素全部加到双端队列中。

这里写图片描述
进行一次pollLast() 后队列中元素的情况。
这里写图片描述
进行3次pollLast() 后队列中元素的情况。

由上可以得出以下几点：
①如果单独将addFirst(arr[i]) 和pollLast() 结合使用的话，先进的元素会先出队，后进的元素会后出队，实现的是普通队列。
②如果单独将addLast(arr[i]) 和pollFirst() 结合使用的话，先进的元素会先出队，后进的元素会后出队，实现的也是普通队列。

深入了解ArrayDeque

下面从源码来看看ArrayDeque是如何实现上述功能的。

构造函数

默认构造函数新建了一个大小为16的数组。

1
2
3
4
public ArrayDeque() {
        elements = (E[]) new Object[16];
        //默认构造函数新建了一个大小为16的数组。
    }

用户初始化大小的构造函数。

1
2
3
public ArrayDeque(int numElements) {
       allocateElements(numElements);
   }

上面的构造函数中只用到 allocateElements(numElements) 下面看看allocateElements(numElements) 的源码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void allocateElements(int numElements) {
    int initialCapacity = 8;

    if (numElements >= initialCapacity) {
        initialCapacity = numElements;
        initialCapacity |= (initialCapacity >>>  1);
        initialCapacity |= (initialCapacity >>>  2);
        initialCapacity |= (initialCapacity >>>  4);
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
        initialCapacity++;

        if (initialCapacity < 0)   
            initialCapacity >>>= 1;// 最大分配2 ^ 30 空间
    }
    elements = (E[]) new Object[initialCapacity];
}

上面的这段代码做一下几点说明：
①当用户要求分配的数组大小小于8时，分配8个空间，当用户要求分配的数组大小为8时分配16个空间。
②当用户要求分配的数组大小大于8时则分配大于用户需要内存的2的最小幂，比如用户需要分配的数组大小为21时，系统会分配大小为32的数组。
③最大分配2 ^ 30 大小的数组。

传入容器的构造函数

1
2
3
4
5
6
public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    //分配数组
    addAll(c);
    // 将元素加入到 ArrayDeque中
}

下面看看 addAll(c) 的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
public boolean addAll(Collection<? extends E> c) {
        boolean modified = false;
        for (E e : c)
            if (add(e))
                modified = true;
        return modified;
        //将元素全部加到ArrayDeque中。其中add 方法调用了addLast 后面会对addLast源码进行分析
    }
        
public boolean add(E e) {
        addLast(e);
        return true;
    }

下面利用 ArrayDeque(Collection<? extends E> c) 这个构造器来实现一个简单的例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
public class DequeDemo {
	public static void main(String[] args) {
		Integer []arr={1,2,3,4,5,6,7,8};
		List<Integer> list=Arrays.asList(arr);
		//初始化的时候传入一个List的容器。
		ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>(list);
				 
		 while(!aDeque.isEmpty())
			System.out.print(aDeque.pollLast()+" ");
		
	}
	
}

上面代码中初始化时传入一个List的容器，下面示意图看看构造后的ArrayDeque是什么样的。

这里写图片描述
由上图可知：将list的元素加入到ArrayDeque中的时候是调用了addLast 方法，addList 方法是按顺序从前往后加入的。

addFirst

1
2
3
4
5
6
7
8
9
10
public void addFirst(E e) {
        if (e == null)
            throw new NullPointerException();
        //如果加入的元素为null 抛出空指针异常。    
        elements[head = (head - 1) & (elements.length - 1)] = e;
        //head值先减1，然后将元素放到head位置
        if (head == tail)
            doubleCapacity();
            //如果head == tail 将数组大小扩大一倍
    }

上面的tail 和 head到底是啥，还是画图来看看。
这里写图片描述
由上图可知
①addFirst 加一个元素时，head都会先减1，然后再放元素。head初始值为 0。
② (head - 1) & (elements.length - 1) 使head的值在【0， elements.length - 1】范围之内，同时可以循环利用数组里面的空间，head一直围着数组转圈。
③如果tail==head 的时候，由上图可知数组中的元素已经满了，所以会将数组的扩大一倍。初始时tail=0。

addLast

1
2
3
4
5
6
7
8
public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        //将e的值放到tail位置，然后tail+1，如果数组满了扩容一倍。
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

由上面的图可知 addLast 时操作 tail 在tail位置加入元素，如果数组已经满了就扩容一倍。

pollFirst

1
2
3
4
5
6
7
8
9
public E pollFirst() {
        int h = head;
        E result = elements[h]; //将elements[h]赋值给result。
        if (result == null)
            return null;//如果result 为null 直接返回
        elements[h] = null;     // 如果result不为null 将elements[h] 赋值为null
        head = (h + 1) & (elements.length - 1);// head+1.
        return result;
    }

下面是一个使用pollFirst() 的例子。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class DequeDemo {
	public static void main(String[] args) {
		Integer []arr={1,2,3,4,5,6,7,8};
		List<Integer> list=Arrays.asList(arr);
		 ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>(list);
		 for(int i=0;i<3;i++)
			 aDeque.addFirst(arr[i]);
			 //往双端队列中添加元素
		 while(!aDeque.isEmpty())
			aDeque.pollFirst();
		//使用pollFirst()删除。
	}
	
}

下面看看上面代码的流程图：
这里写图片描述
添加完元素后的双端队列。
这里写图片描述
执行一次pollFirst() 后。
这里写图片描述
执行两次pollFirst()之后
这里写图片描述
执行三次pollFirst()之后
这里写图片描述
执行6次pollFirst()之后。
通过上面的图就很好理解pollFirst() 的删除流程了。

pollLast

1
2
3
4
5
6
7
8
9
10
public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        E result = elements[t];
        //tail 先减1然后获取tail中的内容。
        if (result == null)
            return null;//如果result 为null 直接返回
        elements[t] = null;//否则将t位置的元素清空再返回result
        tail = t;
        return result;
    }

还是利用上面的那段代码只不过将pollFirst（） 改为pollLast() 代码如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class DequeDemo {
	public static void main(String[] args) {
		Integer []arr={1,2,3,4,5,6,7,8};
		List<Integer> list=Arrays.asList(arr);
		 ArrayDeque<Integer> aDeque=new ArrayDeque<Integer>(list);
		 for(int i=0;i<3;i++)
			 aDeque.addFirst(arr[i]);
			 //添加元素
		 while(!aDeque.isEmpty())
			aDeque.pollLast();
		//删除元素
	}
	
}

依然上图：
这里写图片描述
添加完元素的队列。
这里写图片描述
执行一次pollLast() 后。
这里写图片描述
执行8次pollLast() 后。
这里写图片描述
执行9次pollLast() 后。
由上面可以总结出：
①每次pollLast()前tail先减1，然后再删除，tail指向的位置在元素的上一个位置。
② pollLast() 也是绕着数组循环删除的。tail一直绕着数组循环转动。

removeFirst()

1
2
3
4
5
6
7
8
public E removeFirst() {
        E x = pollFirst();
        //调用pollFirst()
        if (x == null)
            throw new NoSuchElementException();
            //当pollFirst()返回null抛出null 元素异常。
        return x;
    }

由上面代码可知其实removeFirst() 就是调用pollFirst() 不同之处在于在当pollFirst()返回null removeFirst() 抛出 null 元素异常。

removeLast()

1
2
3
4
5
6
7
public E removeLast() {
        E x = pollLast();
        //调用 pollLast() 当pollLast()返回null抛出null 元素异常。
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

由上面代码可知其实removeLast() 就是调用pollLast() 不同之处在于在当pollLast()返回null removeLast() 抛出 null 元素异常。

add(E e)

1
2
3
4
5
public boolean add(E e) {
//调用 addLast(e); 添加成功返回 true。
       addLast(e);
       return true;
   }

remove()

1
2
3
public E remove() {
       return removeFirst();
   }
-------------本文结束感谢您的阅读-------------
undefined