Java中是有Stack类进行栈操作的,但是在很多文档和博客上已经不推荐使用Stack类,而另一方面,Java中没有Queue的类(只有一个接口),Deque接口继承了Queue接口,而有两个类实现了Deque接口,它们是LinkedList和ArrayDeque,也就是这两个类可以实现栈和队列的功能,但是最推荐的用来实现栈和队列的类是ArrayDeque。
要讲ArrayDeque,便要先提一下Deque接口,Deque的含义是“double ended queue”,即双端队列,它继承了Queue接口,既可以当队列使用,也可以当栈使用,ArrayDeque便是实现了这个接口以及接口中的方法。
从名字不难看出,ArrayDeque底层是使用数组实现的,为了满足队列可以两端进行添加删除操作的需求,该数组还需要使用循环数组,需要注意的是,ArrayDeque是非线程安全的,多个线程同步使用的时候需要程序员手动同步。
ArrayDeque原理图如下:
ArrayDeque向头部添加元素的方法如下:
|
|
首先可以看到,对ArrayDeque元素的操作不允许有null存在,这个对ArrayDeque的其他方法也一样。后面是元素的插入,而在元素的插入中解决了下标的越界问题。head = (head - 1) & (elements.length - 1)相当于取余,因为elements.length必需是2的指数倍,elements - 1就是二进制低位全1,跟head - 1相与之后就起到了取模的作用。
再往后,如果循环数组的头和尾撞到了一起,则说明现在这个数组已经被填满,于是就调用扩容方法doubleCapacity:
|
|
其实整个过程就是获取一个原数组的两倍长度的新数组,然后将原数组的元素复制到新数组中,复制时先复制头部右侧的元素,再复制头部左侧的元素,其实也就是从head往tail的顺序将元素拷贝到新数组的从0开始的各个位置上。
与addFirst相对应的,ArrayDeque还有addLast方法,可以实现在尾部添加元素,其中对下标的处理,以及扩容的处理与addFirst中相同,其他方法的处理也大同小异,这里不再赘述,只标注各个方法的作用。
- addFirst()在头部添加元素
- addLast()在尾部添加元素
- pollFirst()删除并获取头部元素
- pollLast()删除并获取尾部元素
- peekFirst()获取但不删除头部元素
- peekLast()获取但不删除尾部元素