java数据结构队列（Queue）之个人理解

1. 队列定义

队列（Queue）是只允许在一端进行插入，而在另一端进行删除的运算受限的线性表。
（1）允许删除的一端称为队头（Front）。
（2）允许插入的一端称为队尾（Rear）。
（3）当队列中没有元素时称为空队列。
（4）队列亦称作先进先出（First In First Out）的线性表，简称为FIFO表。
在Java编程中，Queue的实现都是用LinkedList

2. 具体分析

Java中Queue是一个接口，具有以下方法：

操作	说明
boolean add（E e）	插入元素到队尾，若超出队列容量抛异常
boolean offer(E e)	插入元素到队尾，若超出队列容量返回false
E remove()	移除队头元素
E poll()	移除队头元素，若队列为空返回null
E element()	返回队头元素，若队列为空抛异常
E peek()	返回队头元素，若队列为空返回null

Queue的实现类（2大类）：

未实现BlockingQueue接口的不阻塞队列：

a.LinkedList（实现了java.util.Deque接口）
Deque接口是Queue接口的子接口，代表一个双端队列。同时Deque不仅可以作为双端队列使用，而且可以被当成栈来使用，所以可以使用出栈，入栈的方法。

b.PriorityQueue （实现了java.util.AbstractQueue抽象类和java.util.Queue接口）

PriorityQueue是个基于优先级堆的极大优先级队列。此队列按照在构造时所指定的顺序对元素排序，既可以根据元素的自然顺序来指定排序（参阅 Comparable），也可以根据 Comparator 来指定，这取决于使用哪种构造方法。优先级队列不允许 null 元素。依靠自然排序的优先级队列还不允许插入不可比较的对象（这样做可能导致 ClassCastException）
源码分析：
```
  public PriorityQueue (int initialCapacity,Comparator<? super E >comparator){
if(initialCapacity < 1)
throw new 　IllegalArgumentException();
this.qurue = new Object [initialCapacity ];
this.compatator = comparator;   
}
public PriorityQueue(Collection<? extends E> c) {
    initFromCollection(c);
if (c instanceof SortedSet)
        comparator = (Comparator<? super E>)
            ((SortedSet<? extends E>)c).comparator();
else if (c instanceof PriorityQueue)
        comparator = (Comparator<? super E>)
            ((PriorityQueue<? extends E>)c).comparator();
else {
        comparator = null;
        heapify();
 }
// 若要转换为PriorityQueue的Collection类必须实现SortedSet接口，此接口主要用于排序操作，即实现此接口的子类都属于排序的子类
```
SortedSet接口中定义的方法：

方法	描述
public Comparator< ? super E>comparator()	返回与排序有关联的比较器
public E first()	返回集合中的第一个元素
public SortedSet< E > headset(E toElement)	返回从开始到指定元素的集合
public E last()	返回最后一个元素
public SortedSet< E > subSet(E fromElement,E toElement)	返回指定对象间的元素
public SortedSet< E> tailSet(E fromElement)	从指定元素到最后

PriorityQueue深入解析:
http://blog.csdn.net/kobejayandy/article/details/46832797

c.ConcurrentLinkedQueue（实现了java.util.AbstractQueue抽象类和java.util.Queue接口）

2.实现阻塞接口的队列：

新 的 java.util.concurrent 包在 Collection Framework 中可用的具体集合类中加入了 BlockingQueue 接口和五个阻塞队列类。它实质上就是一种带有一点扭曲的 FIFO 数据结构。不是立即从队列中添加或者删除元素，线程执行操作阻塞，直到有空间或者元素可用。

五个队列所提供的各有不同：

* ArrayBlockingQueue ：一个由数组支持的有界队列。
* LinkedBlockingQueue ：一个由链接节点支持的可选有界队列。
* PriorityBlockingQueue ：一个由优先级堆支持的*优先级队列。
* DelayQueue ：一个由优先级堆支持的、基于时间的调度队列。
* SynchronousQueue ：一个利用 BlockingQueue 接口的简单聚集（rendezvous）机制。

前两个类 ArrayBlockingQueue 和 LinkedBlockingQueue 几乎相同，只是在后备存储器方面有所不同， LinkedBlockingQueue 并不总是有容量界限。无大小界限的 LinkedBlockingQueue 类在添加元素时永远不会有阻塞队列的等待（至少在其中有Integer.MAX_VALUE 元素之前不会）。
PriorityBlockingQueue 是具有*限容量的队列，它利用所包含元素的 Comparable 排序顺序来以逻辑顺序维护元素。可以将它看作 TreeSet 的可能替代物。不过对 PriorityBlockingQueue 有一个技巧。从 iterator() 返回的 Iterator 实例不需要以优先级顺序返回元素。如果必须以优先级顺序遍历所有元素，那么让它们都通过 toArray() 方法并自己对它们排序，像 Arrays.sort(pq.toArray())。
新的 DelayQueue 实现可能是其中最有意思（也是最复杂）的一个。加入到队列中的元素必须实现新的 Delayed 接口（只有一个方法 —— long getDelay(java.util.concurrent.TimeUnit unit) ）。因为队列的大小没有界限，使得添加可以立即返回，但是在延迟时间过去之前不能从队列中取出元素。如果多个元素完成了延迟，那么最早失效/失效时间最长的元素将第一个取出。实际上没有听上去这样复杂。
SynchronousQueue 类是最简单的。它没有内部容量。它就像线程之间的手递手机制。在队列中加入一个元素的生产者会等待另一个线程的消费者。当这个消费者出现时，这个元素就直接在消费者和生产者之间传递，永远不会加入到阻塞队列中。

秒客网

java数据结构队列（Queue）之个人理解

1. 队列定义

2. 具体分析

相关文章