For investors
股价:
5.36 美元 %For investors
股价:
5.36 美元 %认真做教育 专心促就业
Queue是在两端出入的List,所以也可以用数组或链表来实现。
–普通队列–
LinkedList
是的,以双向链表实现的LinkedList既是List,也是Queue。它是唯一一个允许放入null的Queue。
ArrayDeque
以循环数组实现的双向Queue。大小是2的倍数,默认是16。
普通数组只能快速在末尾添加元素,为了支持FIFO,从数组头快速取出元素,就需要使用循环数组:有队头队尾两个下标:弹出元素时,队头下标递增;加入元素时,如果已到数组空间的末尾,则将元素循环赋值到数组[0](如果此时队头下标大于0,说明队头弹出过元素,有空位),同时队尾下标指向0,再插入下一个元素则赋值到数组[1],队尾下标指向1。如果队尾的下标追上队头,说明数组所有空间已用完,进行双倍的数组扩容。
PriorityQueue
用二叉堆实现的优先级队列,详见入门教程,不再是FIFO而是按元素实现的Comparable接口或传入Comparator的比较结果来出队,数值越小,优先级越高,越先出队。但是注意其iterator()的返回不会排序。
–线程安全的队列–
ConcurrentLinkedQueue/ConcurrentLinkedDeque
无界的并发优化的Queue,基于链表,实现了依赖于CAS的无锁算法。
ConcurrentLinkedQueue的结构是单向链表和head/tail两个指针,因为入队时需要修改队尾元素的next指针,以及修改tail指向新入队的元素两个CAS动作无法原子,所以需要的特殊的算法,篇幅所限见入门教程。
PriorityBlockingQueue
无界的并发优化的PriorityQueue,也是基于二叉堆。使用一把公共的读写锁。虽然实现了BlockingQueue接口,其实没有任何阻塞队列的特征,空间不够时会自动扩容。
更多武汉IT培训班相关资讯,请扫描下方二维码