今天我要分享的是java里面比较常见的数据结构队列的源码分析,队列,先进先出模式,即FIFO的特点,日常生活中队列的特点也随处可见,超市购物排队,餐厅排队买饭等一系列都满足了队列的先进先出的特点,java作为一门高级语言,自然提供了队列这种成熟的数据结构供我们使用了。
今天我就以自己的理解进行分析了,首先先说下或者先讲述下我为什么要写这篇文章吧?工作中用到了?没有,那你为什么要写?炫技?也不是,主要是之前我自己分析了ArrayList,LinkedList以及Stack的源码文章了,到这里就理所应当的应该分析队列的这种数据结构了,满足一下学生时代心心念的数据结构吧。
数据结构,数组,链表,栈,队列等在我们的开发中很常见,但是我没有用队列的特点做过业务的需求开发,所以这篇文章的讲述自然就涉及不到工作的内容了。
说了这么多,接下来就逐渐去分析队列的源码吧,写到这时下起了小雨,对,这个时间段是晚上十点左右,这篇文章是自己继五一放假来的第一篇文章,自己玩着玩着手机就突然想起了要写这篇文章了,索性就过来写了,要是学生时代这么努力多好,其实我不后悔学生时期的贪玩,即使那个时间段努力增进自己的技术又能怎样?谁也不知道未来会怎样,不后悔,便值得。
关于读源码,如何进行梳理整个过程,每个人都有着自己的一套,在这里我就以自己的一套来进行分析好了。絮叨了这么多,接下来就是示例程序的展示了,今天看了一位作者的说法,他说写一篇文章,代码不易过多,每个人都有着自己的写作方式,见仁见智吧,适合自己的才是最好的,好怀念写代码的那段日子,没日没夜。
这里要分析的是下面这个队列,所以这里暂时下贴出一点这个类的继承结构,便于自己分析。
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{}
一,首先我们先看下ArrayDequeue队列的构造函数吧。
/**
* Constructs an empty array deque with an initial capacity
* sufficient to hold 16 elements.
*/
public ArrayDeque() {
elements = new Object[16];
}
构造一个内存容量为16大小的数组,用于存储数据元素,即队列的初始大小容量为16,可以容纳16个数据元素。
二,ArrayDequeue也支持自定义容量的构造函数的设置,和ArrayList集合差不多的意思,这样减少了数组元素的拷贝,提高了性能,一般面试的时候都会问到这一点的。
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
步骤一:
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
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;
}
elements = new Object[initialCapacity];//暂时先看这部分好了,就是内存空间的开辟,上面的内容暂时先不理解也没事,不影响我们的分析
}
写到这里,写到了内存空间的分配的字样,想到了自己学习c语言的模样,那个拿着大部书《C语言程序设计》前往机房的少年,由于兴趣使然,逐渐走上了javaWeb的开发了,不过这里说明一点,学习c语言对于你理解高级语言java大有裨益,这是自己的理解。
三,一般写到这里就会去分析数据结构的基本方法,添加方法add了,这里当然是顺势而为分析一下add方法了。
public boolean add(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();
}
首先进行前置校验,判断元素e是否为null,若是null直接抛出空指针异常,说起前置校验,其实你在做javaWeb的开发时一定会遇到的,基于aop的方式或者手动判断都是要的,因为我们要去校验不可信数据即外部输入的数据,关于如何校验,这里暂时说一下,自己后面会单独写上一篇关于参数校验的文章了,然后将元素e放置到数据的末尾,然后判断队列是否满了,若满了则进行扩容,这也是为什么叫动态扩容机制了,现在谁还在使用静态扩容呢?何况java作为一门高级语言呢,顺势而为成就了这个语言令人喜欢的特点吧。
四,队列既然有入队,想必就会想到队列出队的方法,即poll方法,接下来我们继续看下队列出队的方法时间吧。
public E poll() {
return pollFirst();
}
步骤一:
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) 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;
}
首先将队头元素赋值给局部变量h,即int h=head,这也是一贯写代码的习惯,然后根据数组下标值进行元素的定位,即时间复杂度为O(1)这也是数组作为查找比较快的原因之一吧,写到这写到了hash函数的特性了,时间复杂度也很小,后面若是有需要可以分享一下关于hash相关的内容,毕竟数据结构map的特点就是结合hash加上树,链表,数组组成了优秀的源码。然后将队列的队头元素置为null,这样便于垃圾收集器进行资源的回收,但是这里没有写到let's gc ,怎么和集合不一样呢,然后队列元素前置一位,并且判断队列是否在整个队列的范围内,这是比较重要的,将获取的元素进行返回。
五,有了入队,出队,接下来我们在看下如何获取元素个数
public int size() {
return (tail - head) & (elements.length - 1);
}
队尾元素位置减去队首元素位置进行队列元素个数的确定,是不是很简单,写到这是不是有点激动可以写自己的队列了,其实造轮子固然令人兴奋,但是为时尚早,慢慢来,需要的时候自然要造轮子的。
六,一般集合都会有判空操作,不然在操作元素时发现是空的,也没有什么意义了,这也是算前置校验的一种吧。
public boolean isEmpty() {
return head == tail;
}
队首位置等于队尾位置就表示这个队列为空,是不是很容易理解。
七,一般集合数据结构我们都会去判断某个元素是否存在,这样便于我们的查找,说到这没有数据库我们一样可以去操作数据,不过都是基于内存来操作的,数据库的出现可以将数据永远存储到存储介质中,保证了断电不易丢失的特性,这也是它广泛的用途吧。
public boolean contains(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x))
return true;
i = (i + 1) & mask;
}
return false;
}
首先,先将元素元素o与null进行比对,若为null则直接返回false,因为队列不允许添加元素为null的值,所以这里又做了一下前置校验,加快校验的速度,然后循环判断元素o和队列的每一个元素进行比较,此时时间复杂度为O(n),相等则返回true,否则返回false。
八,队列这个数据结构可以像栈一样只返回队列的队首元素,但是不出队。
public E peek() {
return peekFirst();
}
步骤一:
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
这里只返回数组的第一个元素,但是不出队,是不是很巧妙,这是设计的构思,欣赏一下。
九,队列的操作其实也是增删改查操作,这里介绍最后一个方法,如何清空队列的元素。
public void clear() {
int h = head;
int t = tail;
if (h != t) { // clear all cells
head = tail = 0;
int i = h;
int mask = elements.length - 1;
do {
elements[i] = null;
i = (i + 1) & mask;
} while (i != t);
}
}
首先使用两个局部变量h,t进行队首,队尾元素位置的确定,使用do...while语句进行判断队首是否等于队尾来判断队列是否为空,然后将数组的每一个元素置为null,然后等jvm垃圾收集器进行收集元素为null,这样队列的元素就被清空了。
十,到这里就结束了自己对队列的源码分析,其实你会发现我这里没有对队列的每一个方法进行分析,其实都差不多,这里起到一个开头作用就可以了,下面的每个分析方法都差不多。
时间也不早了,也快到晚上十一点了,到这里就结束了,自己写文章的风格渐渐变了,变得文字稍微多了一点。