java-集合--queue

2017-01-01 22:54

简介

  • 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来指示队列的头和尾。他们的定义如下:

来自:http://shmilyaw-hotmail-com.iteye.com/blog/1700599