6. Queue

Queue

队列是一种重要的数据结构，跟人排队购票类似。Java集合中队列相关的类有：

1. LinkedList
LinkedList实现了Queue和Deque接口，所以LinkedList也用来实现普通队列，相关操作有： offer, poll, peek, offerFirst, offerLast, pollFirst, pollLast, peekFirst, peekLast。 具体见LinkedList一节

2. ArrayDeque
ArrayDeque是底层基于数组的队列，操作跟LinkedList的一样

3. PriorityQueue
优先级队列，即插入的元素不是依次从队尾插入，而是保持一定的顺序，出列时队首的先出。

4. ConcurrentLinkedQueue, ConcurrentLinkedDeque
支持并发的队列

5. BlockingQueue: ArrayBlockingQueue, LinkedBlockingQueue, PriorityBlockingQueue, LinkedBlockingDeque etc…
阻塞队列：基于数组的阻塞队列，基于链表的阻塞队列，优先级阻塞队列等。
阻塞队列非常有用，可以非常轻松实现多线程场景下生产消费者模式

PriorityQueue

优先级队列在工作中有很多应用，如OS按优先级队列获取待执行进程。Java中的PriorityQueue是非线程安全的， 底层是数组。 当入列时按优先级插入到指定位置，出列时取头元素。

优先级队列底层用到了基于数组的heap树型数据结构，即大顶堆，小顶堆。

offer, pull操作的时间复杂度是： O(logN)
入列，出列会涉及到堆化，平均时间复杂度就是O(logN)

remove(Object), contains(Object)的时间复杂度是： O(N)
移除指定的元素时需要先遍历数组项，找到目标元素，移除再重新堆化

peek的时间复杂度是： O(1)
这个好理解，只是取队首元素，常量时间即可

BlockingQueue

阻塞队列在后面并发包再讲