文章目录

队列（Queue）是一种经常使用的集合。Queue实际上是实现了一个先进先出（FIFO：First In First Out）的有序表。它和List的区别在于，List可以在任意位置添加和删除元素，而Queue只有两个操作：

把元素添加到队列末尾；
从队列头部取出元素。

超市的收银台就是一个队列：

Queue 用于模拟队列这种数据结构。

Queue 接口中定义了如下几个方法。

void add(Object e): 将指定元素加入此队列的尾部。
Object element() : 获取队列头部的元素，但是不删除该元素。
boolean offer(Object e) : 将指定元素加入此队列的尾部。当使用有容量限制的队列时，此方法通常比add(Object e)方法更好。
Object peek(): 获取队列头部的元素，但是不删除该元素。如果此队列为空，则返回 null 。
Object poll() : 获取队列头部的元素，并删除该元素。如果此队列为空，则返回 null 。
Object remove() : 获取队列头部的元素，并删除该元素。

API:java.util.Queue

PriorityQueue 实现类

PriorityQueue 是一个比较标准的队列实现类。之所以说它是比较标准的队列实现，而不是绝对标准的队列实现，是因为 PriorityQueue 保存队列元的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序。因此当调用 peek()方法或者 poll()方法取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。从这个意义上来看， PriorityQueue 己经违反了队列的最基本规则: 先进先出（ FIFO ) 。

下面程序示范了 PriorityQueue 队列的用法:

PriorityQueueTest.java

public class PriorityQueueTest
{
  public static void main(String[] args)
  {
    PriorityQueue pq = new PriorityQueue();
    // 下面代码依次向pq中加入四个元素
    pq.offer(6);
    pq.offer(-3);
    pq.offer(20);
    pq.offer(18);
    // 输出pq队列，并不是按元素的加入顺序排列
    System.out.println(pq); // 输出[-3, 6, 20, 18]
    // 访问队列第一个元素，其实就是队列中最小的元素：-3
    System.out.println(pq.poll());
  }
}

Prio rityQueue 不允许插入 null 元素，它还需要对队列元素进行排序， PriorityQueue 的元素有两种排序方式 :

自然排序 : 采用自然顺序的 PriorityQueue 集合中的元素必须实现Comparable 接口，而且应该是同一个类的多个实例，否则可能导致 ClassCastException 异常。
定制排序 : 创建 PriorityQueue 队列时，传入一个 Comparator 对象，该对象负责对队列中的所有元素进行排序。采用定制排序时不要求队列元素实现Comparable 接口。

PriortyQueue 队列对元素的要求与 TreeSet 对元素的要求基本一致。

API:java.util.PriorityQueue

Deque 接口与 ArrayDeque 实现类

Deque 接口是 Queue 接口的子接口，它代表一个双端队列， Deque 接口里定义了一些双端队列的方法，这些方法允许从两端来操作队列的元素。

void addFirst(Object e): 将指定元素插入该双端队列的开头。
void addLast(Object e): 将指定元素插入该双端队列的末尾。
Iterator descendingIterator(): 返回该双端队列对应的迭代器，该法代器将以逆向顺序来法代队列
中的元素。
Object getFirst(): 获取但不删除双端队列的第一个元素。
Object getLast(): 获取但不删除双端队列的最后一个元素。
boolean offerFirst(Object e): 将指定元素插入该双端队列的开头。
boolean offerLast(Object e): 将指定元素插入该双端队列的末尾。
Object peekFirst(): 获取但不删除该双端队列的第一个元素:如果此双端队列为空，则返回 null 。
Object peekLast(): 获取但不删除该双端队列的最后一个元素:如果此双端队列为空，则返回 null 。
Object pollFirst(): 获取并删除该双端队列的第一个元素;如果此双端队列为空，则返回 null 。
Object pollLast() : 获取并删除该双端队列的最后一个元素;如果此双端队列为空，则返回 null 。
Object pop() (栈方法) : pop 出该双端队列所表示的校的技顶元素。相当于 removeFirstO 。
void push(Object e) (栈方法) : 将一个元素 push 进该双端队列所表示的拢的技顶。相当于addFirst(e) 。
Object removeFirst（）: 获取并删除该双端队列的第一个元素。
Object removeFirstOccurrence(Object o): 删除该双端队列的第一次出现的元素。
Object removeLast（）: 获取并删除该双端队列的最后一个元素。
boolean removeLastOccurrence(Object o): 删除该双端队列的最后一次出现的元素。

Deque 不仅可以当成双端队列使用，而且可以被当成栈来使用，因为该类

里还包含了 pop ( 出栈)、 push (入栈)两个方法。

Deque 的方法与 Queue 的方法对照表

Deque 的方法与 Stack 的方法对照表

API:java.util.Deque

Deque 接口提供了一个典型的实现类: ArrayDeque ，从该名称就可以看出，它是一个基于数组实现的双端队列，创建 Deque 时同样可指定一个 numElements 参数，该参数用于指定 Object[]数组的长度 :如果不指定 numElements 参数， Deque 底层数组的长度为 16 。

ArrayList 和 ArrayDeque 两个集合类的实现机制基本相似，它们的底层都采用一个动态的、可重分配的 Object[]数纽来存储集合元素，当集合元素超出了该数组的容量时，系统会在底层重新分配一个 Object[]数组来存储集合元素。

下面程序示范了把 ArrayDeque 当成"栈"来使用 :

ArrayDequeStack.java

public class ArrayDequeStack
{
  public static void main(String[] args)
  {
    ArrayDeque stack = new ArrayDeque();
    // 依次将三个元素push入"栈"
    stack.push("疯狂Java讲义");
    stack.push("轻量级Java EE企业应用实战");
    stack.push("疯狂Android讲义");
    // 输出：[疯狂Android讲义, 轻量级Java EE企业应用实战, 疯狂Java讲义]
    System.out.println(stack);
    // 访问第一个元素，但并不将其pop出"栈"，输出：疯狂Android讲义
    System.out.println(stack.peek());
    // 依然输出：[疯狂Android讲义, 疯狂Java讲义, 轻量级Java EE企业应用实战]
    System.out.println(stack);
    // pop出第一个元素，输出：疯狂Android讲义
    System.out.println(stack.pop());
    // 输出：[轻量级Java EE企业应用实战, 疯狂Java讲义]
    System.out.println(stack);
  }
}

ArrayDeque也可以当成队列使用，此处 AπayDeque 将按"先进先出"的方式操作集合元素。例如如下程序：

ArrayDequeQueue.java

public class ArrayDequeQueue
{
  public static void main(String[] args)
  {
    ArrayDeque queue = new ArrayDeque();
    // 依次将三个元素加入队列
    queue.offer("疯狂Java讲义");
    queue.offer("轻量级Java EE企业应用实战");
    queue.offer("疯狂Android讲义");
    // 输出：[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
    System.out.println(queue);
    // 访问队列头部的元素，但并不将其poll出队列"栈"，输出：疯狂Java讲义
    System.out.println(queue.peek());
    // 依然输出：[疯狂Java讲义, 轻量级Java EE企业应用实战, 疯狂Android讲义]
    System.out.println(queue);
    // poll出第一个元素，输出：疯狂Java讲义
    System.out.println(queue.poll());
    // 输出：[轻量级Java EE企业应用实战, 疯狂Android讲义]
    System.out.println(queue);
  }
}

LinkedList 也实现了 Deque 接口，可以被当成双端队列来使用，因此既可以被当成"栈"来使用，也可以当成队列使用。

API:java.util.ArrayDeque

各种线性表的性能分析

Java 提供的 List 就是一个线性表接口，而ArrayList、LinkedList 又是线性表的两种典型实现 : 基于数组的线性表和基于链的线性表。 Queue 代表了队列， Deque 代表了双端队列(既可作为队列使用，也可作为栈使用) 。

一般来说，

由于数组以一块连续内存区来保存所有的数组元素，所以数组在随机访问时性能最好，所有的内部以数组作为底层实现的集合在随机访问时性能都比较好;
而内部以链表作为底层实现的集合在执行插入、删除操作时有较好的性能。

但总体来说， ArrayList 的性能比 LinkedList 的性能要好，因此大部分时候都应该考虑使用ArrayList。

关于使用 List 集合有如下建议：

如果需要遍历 List 集合元素，对于 ArrayList 、 Vector 集合，应该使用随机访问方法 (get) 来遍历集合元素，这样性能更好;对于 LinkedList 集合，则应该采用法代器 (Iterator ) 来遍历集合元素。
如果需要经常执行插入、删除操作来改变包含大量数据的 List 集合的大小,可考虑使用LinkedList 集合。使用 ArrayList 、 Vector 集合可能需要经常重新分配内部数组的大小，效果可能较差。
如果有多个线程需要同时访问 List 集合中的元素，开发者可考虑使用 Collections 将集合包装成线程安全的集合。