第十三章《集合》第4节：Queue集合

​Queue是一个接口，它也是Collection接口的子接口。Queue用来模拟队列这种数据结构。队列这种数据结构最明显的特征是元素先入先出，队列的头部的元素是所有元素中最先进入队列的，而队列尾部的元素则是所有元素中最后进入队列的，也就是说，每次新加入的元素都会被放到队列的末尾。通常情况下，不允许随机访问队列中的任意元素。下面的表13-6展示了Queue接口定义的各种方法。

表13-6 Queue接口的方法​

表13-6中的add()方法在把元素e加入队列时，如果元素个数超出队列长度时将抛出异常，此处需要说明：因元素个数超出队列长度而抛出异常的情况只会发生在长度不能自动增长的队列上，有些队列的长度能够自动增长，因此不会产生因加入的元素个数过多而抛出异常的情况。​

Queue最典型的实现类是PriorityQueue，最典型的子接口是Deque，本节将重点讲解它们的使用方法。​

13.4.1 PriorityQueue类

PriorityQueue并不是绝对标准的队列实现，这是因为 PriorityQueue保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序。因此当调用peek()方法或者 poll()方法取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。从这个意义上来看，PriorityQueue已经违反了队列最基本的先进先出规则，此外还需强调：PriorityQueue队列中不允许加入null作为元素。下面【例13_12】展示PriorityQueue 队列的用法。​

【例13_12 PriorityQueue的使用】

Exam13_12.java​

import java.util.PriorityQueue;
public class Exam13_12 {
    public static void main(String[] args) {
        PriorityQueue pq = new PriorityQueue(3);//创建长度为3的队列
        pq.add(10);
        pq.add(2);
        pq.add(4);
        pq.add(6);
        System.out.println("队列中元素的个数："+pq.size());
        System.out.println("整个队列："+pq);
        System.out.println("队列中的第一个元素："+pq.element());
    }
}

【例13_12】的运行结果如图13-17所示。​

图13-17【例13_12】运行结果​

从图13-17可以看出：虽然程序中创建的队列长度为3，但在加入4个元素后仍然没有出现异常，这说明PriorityQueue队列的长度能够自动增长。此外还可以看出：加入队列的元素会自动按照从小到大的降序规律排列。实际上，PriorityQueue也可以自定义排序规则，实现自定义排序的方法与TreeSet实现自定义排序的方法是一样的，都需要一个Comparator接口的实现类对象作为参数，在Comparator接口的实现类中自定义排序的规则。​

13.4.2 Deque接口和ArrayDeque类

Deque接口是Queue接口的子接口，它代表一个双端队列。所谓双端队列就是指两端都可以加入或取出元素的队列。Deque接口里定义了一些双端队列的方法，如表13-7所示。​

表13-7 Deque接口的方法​

从表13-7可以看出：Deque还定义了用于操作栈的方法。栈也是一种数据结构，它与队列不同，栈中的元素需要遵循先入后出的规则。把元素加入栈的方法是push()，而把栈中最顶端(实际上就是最前端)元素取出的方法是pop()。如果只用这两个方法加入或取出元素，那么Deque就是一个栈。实际上，Vector类有一个子类Stack也代表了栈这种数据结构，但Stack的性能较差，所以Java官方并不提倡使用Stack，而是使用Deque的实现类来作为栈这种数据结构。​

Deque有一个典型的实现类ArrayDeque，从这个类的名称可以看出：ArrayDeque是以数组存储元素。ArrayDeque与ArrayList相似，它们的底层都采用一个动态的、可重分配的Object数组来存储集合元素，当集合元素超出了该数组的容量时，系统会在底层重新分配一个Object数组来存储集合元素。下面的【例13_13】展示了把ArrayDeque当作栈来使用的效果。​

【例13_13 ArrayDeque的使用1】

Exam13_13.java​

import java.util.ArrayDeque;
public class Exam13_13 {
    public static void main(String[] args) {
        ArrayDeque<String> stack = new ArrayDeque<String>();
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");
        System.out.println("整个栈："+stack);
        System.out.println("第1次弹出栈顶元素："+stack.pop());
        System.out.println("第2次弹出栈顶元素："+stack.pop());
        System.out.println("第3次弹出栈顶元素："+stack.pop());
    }
}

【例13_13】的运行结果如图13-18所示。​

图13-18【例13_13】运行结果​

从图13-18可以看出：使用push()方法向集合中加入元素时，每次都是加入到集合的头部，而每次使用pop()方法取出集合中的元素时，取出的都是集合头部的元素，这正好符合栈先入后出的特点。专业上，把元素加入栈的操作称为“压入”，而把元素从栈中取出的操作称为“弹出”。​

ArrayDeque也可以被当作队列来使用，如果当作队列来使用，就不要用push()和pop()方法加入或删除元素，因为那都是用于操作栈的方法。下面的【例13_14】展示了把ArrayDeque作为队列使用的效果。​

【例13_14 ArrayDeque的使用2】​

Exam13_14.java​

import java.util.ArrayDeque;
public class Exam13_14 {
    public static void main(String[] args) {
        ArrayDeque<String> queque = new ArrayDeque<String>();
        queque.offer("Java");
        queque.offer("Python");
        queque.offer("C++");
        System.out.println("整个队列："+queque);
        System.out.println("队列头部的元素："+queque.peekFirst());
        System.out.println("队列尾部的元素："+queque.peekLast());
    }
}

【例13_14】的运行结果如图13-19所示。​

图13-19【例13_14】运行结果​

13.4.3线性表性能分析

Java语言用List接口表示线性表，所谓线性表就是元素呈线性排列的数据结构。队列实际上也是线性表，只是它无法像普通线性表那样随机访问元素。因此可以把队列与普通线性表放在一起做性能分析。​

从实现原理来看：线性表可以分为基于数组的线性表和基于链表的线性表。ArrayList、Vector、ArrayDeque都是基于数组的线性表，而LinkedList是基于链表的线性表。线性表的应用也分不同的情况，如果模拟银行的排队机，自然要用代表队列的线性表，因为这样的线性表不能在集合的任意位置插入元素，也不能随机的访问线性表中的任意元素。如果需要对元素进行随机访问或在任意位置插入、删除元素，那么就要用ArrayList、Vector和LinkedList这样的线性表。​

在使用这些线性表时需要知道：由于数组以一块连续内存区来保存所有的数组元素，所以数组在随机访问时性能最好，所有基于数组的线性表在随机访问时性能都比较好。基于链表的线性表在完成插入、删除元素的操作时有较好的性能。但总体来说，ArrayList 的性能比LinkedList的性能要好，因此大部分时候都应该考虑使用ArrayList。​

如果需要遍历List集合元素，对于ArrayList和Vector集合，使用随机访问元素的get()方法速度更快，而对于LinkedList集合采用迭代器(Iterator)来遍历集合元素速度更快。​

如果需要经常执行插入、删除操作可以考虑使用LinkedList集合，因为使用ArrayList、Vector在删除或插入元素时会有大量的元素进行移动，并且可能会重新分配内部数组的大小，因此执行插入、删除操作的速度较慢。如果有多个线程需要同时访问List集合中的元素，开发者可考虑使用Collections将集合包装成线程安全的集合。

本文字版教程还配有更详细的视频讲解，小伙伴们可以​​点击这里​​观看。