java 集合- queue
2016-12-21 本文已影响44人
望月成三人
简介
- Queue是一种很常见的数据结构类型，在java里面Queue是一个接口，它只是定义了一个基本的Queue应该有哪些功能规约。实际上有多个Queue的实现，有的是采用线性表实现，有的基于链表实现。还有的适用于多线程的环境。java中具有Queue功能的类主要有如下几个：AbstractQueue, ArrayBlockingQueue, ConcurrentLinkedQueue, LinkedBlockingQueue, DelayQueue, LinkedList, PriorityBlockingQueue, PriorityQueue和ArrayDqueue。在本文中，我们主要讨论常用的两种实现：LinkedList和ArrayDeque。
Queue
- Queue本身是一种先入先出的模型(FIFO)，和我们日常生活中的排队模型很类似。根据不同的实现，他们主要有数组和链表两种实现形式
- 因为在队列里和我们日常的模型很近似，每次如果要出队的话，都是从队头移除。而如果每次要加入新的元素，则要在队尾加。所以我们要在队列里保存队头和队尾。
在jdk里几个常用队列实现之间的类关系图如下：
Paste_Image.png
Deque
按照我们一般的理解，Deque是一个双向队列，这将意味着它不过是对Queue接口的增强。如果仔细分析Deque接口代码的话，我们会发现它里面主要包含有4个部分的功能定义。
- 双向队列特定方法定义。
- Queue方法定义。
- Stack方法定义。
- Collection方法定义。
第3，4部分的方法相当于告诉我们，具体实现Deque的类我们也可以把他们当成Stack和普通的Collection来使用。这也是接口定义规约带来的好处。这里我们就不再赘述。
ArrayDeque
有了我们前面几篇分析的基础，我们可以很容易猜到ArrayDeque的内部实现机制。它的内部使用一个数组来保存具体的元素，然后分别使用head, tail来指示队列的头和尾。他们的定义如下：
