网站页面优化分析,电子商务网站的运营一般需要做哪些准备,优化网站做什么的,保定网站开发公司Collection的其它两大分支#xff1a;List和Set在前面已近分析过#xff0c;这篇来分析一下Queue的底层实现。
前三篇关于Java容器类的文章#xff1a;
java容器类1#xff1a;Collection,List,ArrayList,LinkedList深入解读
java容器类2#xff1a;Map及HashMap深入解…
Collection的其它两大分支List和Set在前面已近分析过这篇来分析一下Queue的底层实现。
前三篇关于Java容器类的文章
java容器类1Collection,List,ArrayList,LinkedList深入解读
java容器类2Map及HashMap深入解读
java容器类3set/HastSet/MapSet深入解读
Queue public interface QueueE extends CollectionE {boolean add(E var1);boolean offer(E var1);E remove();E poll();E element();E peek();
} 这就是Queue接口的代码相比于List或者Set简洁明了很多。下面介绍一下它里面接口的含义
在处理元素前用于保存元素的 collection。除了基本的 Collection 操作外队列还提供其他的
插入、提取和检查
操作。每个方法都存在两种形式
一种抛出异常操作失败时另一种返回一个特殊值null 或 false具体取决于操作。
插入操作的后一种形式是用于专门为有容量限制的 Queue 实现设计的在大多数实现中插入操作不会失败。 AbstractQueue AbstractQueue中实现了queue和Collection中部分函数比较简单源码如下 public abstract class AbstractQueueE extends AbstractCollectionEimplements QueueE { protected AbstractQueue() {} public boolean add(E e) {if (offer(e))return true;elsethrow new IllegalStateException(Queue full);}public E remove() {E x poll();if (x ! null)return x;elsethrow new NoSuchElementException();}public E element() {E x peek();if (x ! null)return x;elsethrow new NoSuchElementException();}public void clear() {while (poll() ! null);}public boolean addAll(Collection? extends E c) {if (c null)throw new NullPointerException();if (c this)throw new IllegalArgumentException();boolean modified false;for (E e : c)if (add(e))modified true;return modified;}
}从上面的调用关系可以看出来Queue的解释中哪些是会抛出异常的调用哪些是不会抛出异常的调用接口。
Deque 一个线性 collection支持在两端插入和移除元素。名称 deque 是“double ended queue双端队列”的缩写通常读为“deck”。大多数 Deque 实现对于它们能够包含的元素数没有固定限制但此接口既支持有容量限制的双端队列也支持没有固定大小限制的双端队列。java 1.6版本中的家扣1.8中接口有变动但是大概含义相似 在Java容器类1中介绍了LinkedList链表类其实实现了 Deque的接口所以链表支持从头部和尾部添加和移除元素。
ArrayDeque 因为链表的存储结构可能比较简单这里介绍一下ArrayDeque它的里面存储元素使用一个数组。 作为一个双端队列的数组涉及到扩容和元素的拷贝的逻辑可能比较复杂些。
看一下里面的几个构造函数 public ArrayDeque() {elements
new Object[16]; }public ArrayDeque(int numElements) {
allocateElements(numElements); }public ArrayDeque(Collection? extends E c) {allocateElements(c.size());addAll(c);} 从构造函数可以看出默认的会分配一个长度为16的数组。同时也支持指定大小的队列这里的allocateElements函数之前在
java容器类2Map及HashMap深入解读 中已经深入分析过是个非常精妙的函数。下面看一下到底是如何实现插入又是如何自动扩充数组的?
ArrayQueue中维护了两个成员变量head和tail分别代表 队列的头和尾在数组中的下标。 /*** The index of the element at the head of the deque (which is the* element that would be removed by remove() or pop()); or an* arbitrary number equal to tail if the deque is empty.*/transient int head;/*** The index at which the next element would be added to the tail* of the deque (via addLast(E), add(E), or push(E)).*/transient int tail; 在队列的首部添加元素 public void addFirst(E e) {if (e null)throw new NullPointerException();
elements[head (head - 1) (elements.length - 1)] e; if (head tail)
doubleCapacity(); }
public void
addLast(E e) {
if (e
null
)
throw new NullPointerException();elements[tail] e;
if ( (tail (tail 1) (elements.length - 1)) head)doubleCapacity();
} 由构造函数和数组分配的函数可以知道数组的长度肯定是一个2的幂次方的一个整数。
当head为大于0的整数时在头部插入很简单将head前一个元素赋值为e就可以了。那么当head为0时怎么计算的由上面可以看出会插入到数组的尾部。所以ArrayDeque相当于在一个圆环上规定一个头一个尾作为队列的前后将数组的首位相连。
在最后位置添加元素的原理和在首部添加相似。注意判断是否已满的 判断这里不再分析。
当队列已经满后会将数组的长度double。由于数组是不能自由扩张的所以doubleCapacity函数应该是分配一个更大的数组并将原来的元素拷贝进去这里不再分析。
总的来说双端队列ArrayDeque是在数组的基础之上实现原理和实现都不算复杂但是很多边界调节等细节可以斟酌。
BlockingQueue BlockingQueue是concurrent包下面的后续打算写一个系列文章专门分析concurrent包下面的类及一些多线程相关的东西。
PriorityQueue 优先级队列是一个可以排序的队列。内部是一个最大堆大部分人应该了解堆排序所以对最大堆应该不会陌生。
每次读取元素都是读取最大的元素默认情况下。
对外的接口有如下
方法名功能描述add(E e)添加元素clear()清空contains(Object o)检查是否包含当前参数元素offer(E e)添加元素peek()读取元素不删除poll()取出元素删除remove(Object o)删除指定元素size()返回长度
PriorityQueue 默认是一个最大堆结构如果想构造一个最小堆 private static final int DEFAULT_INITIAL_CAPACITY 11;
PriorityQueueInteger maxHeapnew PriorityQueueInteger(DEFAULT_INITIAL_CAPACITY, new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2-o1;}}); 关于堆的数据结构部分这里不再分析可以参考https://www.cnblogs.com/tstd/p/5125949.html
c版的优先级队列分析优先级队列用法详解priority_queue
由于是通过数组保存数据所以优先级队列也会涉及到容量的扩充等和HashMap/Setting/Collection的扩容原理相同甚至更简单不再分析。PriorityQueue内部的操作都是在最大堆的基础上展开的阅读堆的数据结构相关资料便可了解。
参考
http://tool.oschina.net/uploads/apidocs/jdk-zh/java/util/Deque.html
http://www.cnblogs.com/NeilZhang/p/5650226.html
