简介 Queue是一种很常见的数据结构类型，在java里面Queue是一个接口，它只是定义了一个基本的Queue应该有哪些功能规约。实际上有多个Queue的实现，有的是采用线性表实现，有的基于链表实现。还有的适用于多线程的环境。java中具有Queue功能的类主要有如下几个：AbstractQueue, ArrayBlockingQueue, ConcurrentLinkedQueue, LinkedBlockingQueue, DelayQueue, LinkedList, PriorityBlockingQueue, PriorityQueue和ArrayDqueue。在本文中，我们主要讨论常用的两种实现：LinkedList和ArrayDeque。
Queue Queue本身是一种先入先出的模型(FIFO)，和我们日常生活中的排队模型很类似。根据不同的实现，他们主要有数组和链表两种实现形式。如下图：
因为在队列里和我们日常的模型很近似，每次如果要出队的话，都是从队头移除。而如果每次要加入新的元素，则要在队尾加。所以我们要在队列里保存队头和队尾。
在jdk里几个常用队列实现之间的类关系图如下：
我们可以看到，Deque也是一个接口，它继承了Queue的接口规范。我们要讨论的LinkedList和ArrayDeque都是实现Deque接口，所以，可以说他们俩都是双向队列。具体的实现我们会在后面讨论。Queue作为一个接口，它声明的几个基本操作无非就是入队和出队的操作，具体定义如下：
Java代码 [url=] [/url]
[url=] [/url]
public interface Queue<E> extends Collection<E> { boolean add(E e); // 添加元素到队列中，相当于进入队尾排队。 boolean offer(E e); //添加元素到队列中，相当于进入队尾排队. E remove(); //移除队头元素 E poll(); //移除队头元素 E element(); //获取但不移除队列头的元素 E peek(); //获取但不移除队列头的元素 } [url=][/url]
有了这些接口定义的规约，我们就可以很容易的在后续的详细实现里察看具体细节。 |
