Java 集合 Queue

摘要：除此之外，还有一个接口，代表一个双端队列，双端队列可以同时从两端删除添加元素，因此的实现类既可当成队列使用，也可当成栈使用。相当于栈方法将一个元素进该双端队列所表示的栈的栈顶。

Queue用于模拟队列这种数据结构，队列通常是指“先进先出”（FIFO）的容器。队列的头部保存在队列中存放时间最长的元素，队列的尾部保存在队列中存放时间最短的元素。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素

Queue接口的方法

void add(Object e)：将指定元素加入此队列的尾部

Object element()：获取队列头部的元素，但是不删除该元素

boolean offer(Object e)：将指定的元素插入此队列的尾部。当使用容量有限的队列时，此方法通常比add(Object e)有效

Object peek()：返回队列头部的元素，但是不删除该元素。如果队列为空，则返回null

Object poll()：返回队列头部的元素，并删除该元素。如果队列为空，则返回null

Object remove()：获取队列头部的元素，并删除该元素

Queue接口有一个PriorityQueue实现类。除此之外，Queue还有一个Deque接口，Deque代表一个“双端队列”，双端队列可以同时从两端删除、添加元素，因此Deque的实现类既可当成队列使用，也可当成栈使用。Java为Deque提供了ArrayDeque实现类和LinkedList两个实现类

PriorityQueue保存队列元素的顺序不是按加入队列的顺序，而是按队列元素的大小进行重新排序。因此当调用peek()或pool()方法取出队列中头部的元素时，并不是取出最先进入队列的元素，而是取出队列中的最小的元素

public class PriorityQueueTest 
{
    public static void main(String[] args)
    {
        PriorityQueue pq = new PriorityQueue();
        pq.offer(6);
        pq.add(-3);
        pq.add(20);
        pq.offer(18);
        //输出：[-3, 6, 20, 18]
        System.out.println(pq);
    }
}

实际上，程序多次调用poll()方法，既可看到元素按从小到大的顺序“移出队列”，PriorityQueue队列对元素的要求与TreeSet对元素的要求基本一致

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

自然排序：采用自然排序的PriorityQueue集合中的元素必须实现Comparator接口，而且应该是一个类的多个实例，否则可能导致ClassCastException异常

定制排序：创建PriorityQueue队列时，传入一个Comparable对象，该对象负责对所有队列中的所有元素进行排序。采用定制排序不要求必须实现Comparator接口

Deque接口是Queue接口的子接口，它代表一个双端队列

void addFirst(Object e)：将指定元素插入到双端队列的头部

void addLast(Object e)：将指定元素插入到双端队列的尾部

Iteratord descendingItrator()：返回该双端队列对应的迭代器，该迭代器以逆向顺序来迭代队列中的元素

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出该双端队列所表示的栈的栈顶元素。相当于removeFirst()

void push(Object e)(栈方法)：将一个元素push进该双端队列所表示的栈的栈顶。相当于addFirst(e)

Object removeFirst()：获取并删除该双端队列的第一个元素

Object removeFirstOccurence(Object o)：获取并删除该双端队列的第一次出现的元素o

Object removeLast()：获取并删除该双端队列的最后一个元素o

Object removeLastOccurence(Object o)：获取并删除该双端队列的最后一次出现的元素o

Deque与Queue的方法对照图

Deque与Stack的方法对照图

ArrayDeque是一个基于数组实现的双端队列，创建Deque时同样可指定一个numElements参数，该参数用于指定Object[]数组的长度；如果不指定numElements参数，Deque底层数组的长度为16

当程序中需要使用“栈”这种数据结构时，推荐使用ArrayDeque，尽量避免使用Stack——因为Stack是古老的集合，性能较差

//把ArrayDeque当成栈使用

import java.util.*;

public class ArrayDequeStack
{
    public static void main(String[] args)
    {
        ArrayDeque stack = new ArrayDeque();
        // 依次将三个元素push入"栈"
        stack.push("金州勇士");
        stack.push("俄克拉荷马雷霆");
        stack.push("克利夫兰骑士");
        // 输出：[克利夫兰骑士, 俄克拉荷马雷霆, 金州勇士]
        System.out.println(stack);
        // 访问第一个元素，但并不将其pop出"栈"，输出：克利夫兰骑士
        System.out.println(stack.peek());
        // 依然输出：[克利夫兰骑士, 俄克拉荷马雷霆, 金州勇士]
        System.out.println(stack);
        // pop出第一个元素，输出：克利夫兰骑士
        System.out.println(stack.pop());
        // 输出：[俄克拉荷马雷霆, 金州勇士]
        System.out.println(stack);
    }
}

ArrayDeque作为队列使用，按“先进先出”的方式操作集合元素

import java.util.*;

public class ArrayDequeQueue
{
    public static void main(String[] args)
    {
        ArrayDeque queue = new ArrayDeque();
        // 依次将三个元素加入队列
        queue.offer("克利夫兰骑士");
        queue.offer("俄克拉荷马雷霆");
        queue.offer("金州勇士");
        // 输出：[克利夫兰骑士, 俄克拉荷马雷霆, 金州勇士]
        System.out.println(queue);
        // 访问队列头部的元素，但并不将其poll出队列"栈"，输出：克利夫兰骑士
        System.out.println(queue.peek());
        // 依然输出：[克利夫兰骑士, 俄克拉荷马雷霆, 金州勇士]
        System.out.println(queue);
        // poll出第一个元素，输出：克利夫兰骑士
        System.out.println(queue.poll());
        // 输出：[俄克拉荷马雷霆, 金州勇士]
        System.out.println(queue);
    }
}

LinkedList是List接口的实现类——这意味着它是一个List集合，可以根据索引来随机访问集合中的元素。此外，LinkedList还实现了Duque接口，可以被当成双端队列来使用，因此既可以被当成“栈”来使用，也可以当成队列使用。

import java.util.*;

public class LinkedListTest
{
    public static void main(String[] args)
    {
        LinkedList teams = new LinkedList();
        // 将字符串元素加入队列的尾部
        teams.offer("克利夫兰骑士");
        // 将一个字符串元素加入栈的顶部
        teams.push("金州勇士");
        // 将字符串元素添加到队列的头部（相当于栈的顶部）
        teams.offerFirst("俄克拉荷马雷霆");
        // 以List的方式（按索引访问的方式）来遍历集合元素
        for (int i = 0; i < teams.size() ; i++ )
        {
            System.out.println("遍历中：" + teams.get(i));
        }
        // 访问、并不删除栈顶的元素
        System.out.println(teams.peekFirst());
        // 访问、并不删除队列的最后一个元素
        System.out.println(teams.peekLast());
        // 将栈顶的元素弹出“栈”
        System.out.println(teams.pop());
        // 下面输出将看到队列中第一个元素被删除
        System.out.println(teams);
        // 访问、并删除队列的最后一个元素
        System.out.println(teams.pollLast());
        // 下面输出：[金州勇士]
        System.out.println(teams);
    }
}

ArrayList与ArrayDeque内部以数组的形式来保存集合中的元素，因此随机访问集合元素时有较好的性能；LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能较差，但在插入、删除元素时性能比较出色（只需改变指针所指的地址即可）。Vector也是以数组的形式来存储集合元素的，但因为它实现了线程同步功能（而且实现机制也不好），所以各方面性能都比较差

对于所有的内部基于数组的集合实现，例如ArrayList与ArrayDeque等，使用随机访问的性能比使用Iterator迭代访问的性能要好，因为随机访问会被映射成对数组元素的访问

ArrayList：基于数组的线性表
LinkedList：基于链的线性表
Queue：队列
Deque：双端队列

数组以一块连续内存区来保存所有的数组元素，所以数组在随机访问时性能最好，所有的内部以数组为底层实现的集合在随机访问时性能都比较好；而内部以链表作为底层实现的集合在执行插入、删除操作时有较好的性能。总体来说，ArrayList的性能比LinkedList的性能要好，因此大部分时候都应该考虑使用ArrayList

使用List集合的建议：

如果需要遍历List集合元素，对于ArrayList、Vector集合，应该使用随机访问方法（get）来遍历集合元素，这样性能更好；对于LinkedList集合，则应该采用迭代器（Iterator）来遍历集合

如果需要经常执行插入、删除操作来改变包含大量数据的List集合的大小，可考虑使用LinkedList集合。使用ArrayList、Vector集合可能需要经常重新分配内部数组的大小，效果可能较差

如果有多个线程需要访问List集合中的元素，开发者可考虑使用Collections将集合包装成线程安全的集合