免费做网站通栏广告,兼职制作网站开发,建设网站需要学习什么语言,网站规划与开发专业前言#xff1a;
1.对Queue接口进行实现
2.底层的数据结构还是数组#xff0c;同时还是双向的#xff0c;有前后指针
3.不是线程安全的
4.可以当作队列和栈来使用#xff0c;选择使用队列时#xff0c;ArrayDeque推荐首选
5.不可以添加null数据#xff0c;会抛异常 …前言
1.对Queue接口进行实现
2.底层的数据结构还是数组同时还是双向的有前后指针
3.不是线程安全的
4.可以当作队列和栈来使用选择使用队列时ArrayDeque推荐首选
5.不可以添加null数据会抛异常
一些重要变量和常量 //元素数组transient Object[] elements; //头指针指向头部的第一个元素的位置transient int head;//尾指针将下一个元素添加到尾部的索引也就是指向尾端第一个可以插入元素的空位transient int tail;//最小容量同时必须时2的倍数private static final int MIN_INITIAL_CAPACITY 8;
部分源码分析
1.初始化对象 //还是分配16的空间内存 public ArrayDeque() {elements new Object[16];}
2.添加头节点 /*** 在首部添加节点*/public void addFirst(E e) {//如果插入值为空则抛出异常if (e null)throw new NullPointerException();//这里定位和之前hashmap中定位table的位置差不多ArrayDeque本身是一个循环数组//head (head - 1) (elements.length - 1)//在这里相当于取余操作同时也保证了下标不为负值elements[head (head - 1) (elements.length - 1)] e;//添加元素之后如果头指针和尾指针相同才会进行扩容看名字就晓得扩大两倍if (head tail)doubleCapacity();}//也是添加头节点的方法这里是返回是否添加成功public boolean offerFirst(E e) {addFirst(e);return true;}
3.扩容 /*** 扩容操作 扩大两倍*/private void doubleCapacity() {assert head tail;int p head;int n elements.length;// 头节点右边元素的个数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;}
4、添加尾节点 /*** 插入节点到尾部*/public void addLast(E e) {if (e null)throw new NullPointerException();//直接添加即可因为tail指向尾端第一个可以插入元素的空位elements[tail] e;//添加之后再做是否需要扩容的判断if ( (tail (tail 1) (elements.length - 1)) head)doubleCapacity();}//也是另外一个添加尾节点的方法返回成功与否public boolean offerLast(E e) {addLast(e);return true;}
5.删除头结点 /*** 删除头结点返回删除的元素如果删除的元素为null,返回null*/public E pollFirst() {int h head;SuppressWarnings(unchecked)E result (E) elements[h];// 如果队列为空if (result null)return null;//删除头结点将头结点这个位置设为null为了GCelements[h] null; // Must null out slot//头指针前移head (h 1) (elements.length - 1);return result;}/*** 这个也是删除头节点但如果删除的元素为null,抛出异常*/public E removeFirst() {E x pollFirst();if (x null)throw new NoSuchElementException();return x;}
6.删除尾节点 /*** 删除尾结点返回删除的元素如果删除的元素为null,返回null*/public E pollLast() {//tail是指向尾端第一个可以插入元素的空位所以他前面就是尾节点的索引//这里进行-1即可获取尾节点的索引地址int t (tail - 1) (elements.length - 1);SuppressWarnings(unchecked)E result (E) elements[t];if (result null)return null;elements[t] null;//将尾指针设在当前位置也就是被删除尾节点的位置tail t;return result;}/*** 这个也是删除尾节点但如果删除的元素为null,抛出异常*/public E removeLast() {E x pollLast();if (x null)throw new NoSuchElementException();return x;}
还有些获取某个节点实现代码都差不多这里就不一一列出来了到这ArrayDeque也结束了。
