java list 作为queue_Java集合(三)—List和Queue集合
公众号： 菜鸡干Java 欢迎关注
Java集合—List集合
与Set集合不同，List集合是有序，可重复的，而且默认以添加顺序设置索引。List子接口是继承了Collection接口，则可以使用其中的方法。
特别的是List增加了根据索引插入、替换、删除集合元素的方法，此外，Java8为List接口添加了两个默认方法：
void replaceAll()：根据指定规则重新设置List集合的所有元素
void sort(Comparator c)：根据参数对List集合的元素排序
List books = new ArrayList();
books.add(new String("ledon"));
books.add(new String("Android"));
books.sort((o1,o2)->((String)o1).length()-((String)o2).length());
//字符串将由短到长排序
System.out.println(books);
books.replaceAll(e->((String)e).length());
System.out.println(e);//[5,7]
值得注意的是：List判断两个对象相等，只要通过equals方法比较返回true即可，不像Set集合，还需要判断哈希值是否相等来避免重复。
删除元素时，List会调用对象的equals方法依次与集合元素比较，如果返回true，则会删除该元素。如果重写了equals方法，使它总是返回true，则List总会删除第一个元素。在使用set(index,object)方法时，index不能超过集合的长度，也不能改变长度。
List不仅有iterator()方法，还有listIterator()方法，该方法返回一个ListIterator对象，ListIterator接口继承了Iterator接口，提供了专门的方法操作List，增加了如下方法(类似Iterator的方法)：
boolean hasPrevious()：返回该集合是否还有上一个元素
Object previous()：返回上一个元素
void add(Object o)：在指定位置插入一个元素
不难发现该接口还能向前迭代，不止能删除元素，并且还能通过add()方法，添加元素。
ArrayList和Vector
它们两个封装了 一个动态的Object[ ]数组，允许再分配。ArrayList及Vector对象使用initialCapacity参数来设置数组的长度，当超出数组容量时，initialCapacity会自动增加，可使用ensureCapacity(int minCapacity)方法一次性增加initialCapacity。如果事先知道元素的个数，可指定初始大小；如果没有指定初始容量，默认为10。
ArrayList和Vector提供了两个方法重新分配Object[]数组：
void ensureCapacity(int minCapacity)：将ArrayList和Vector集合的Object[]数组长度增加到大于或等于minCapacity值
void trimToSize()：调整ArrayList及Vector的数组长度为当前元素个数，减少占用空间
ArrayList和Vector的用法几乎完全相同，Vector也是实现了List接口，从JDK1.0就有了，很古老！此外，ArrayList是线程不安全的，原理一样；但Vector是线程安全的，即无需保证线程的同步性，因而Vector的性能比ArrayList低。但是还是用ArrayList更多，要想线程安全，也可以把ArrayList变成线程安全。
Stack类(Vector的子类)
翻译过来就是“栈”，模拟进栈push，出栈pop等操作。作为集合的一种，它也是储存对象(Object)的，有如下方法：
Object peek()：返回栈顶元素，但并不弹出该元素，元素还会在栈内
Object pop()：返回栈顶元素，并弹出栈
void push(Object item)：推元素进栈
Stack继承了Vector，所以它也非常古老，线程安全、性能较差。后面还会介绍一种“栈”结构——ArrayDeque，它不仅实现了List接口，还实现了Deque接口，如果需要栈结构，可以使用它而不是Stack。
固定长度的List
有一种操作数组的工具类Arrays，该工具类提供了asList()方法，该方法把一个数组或指定个数的对象换成一个List集合，这个集合不是以上所介绍的集合类的实例，不是ArrayList的，不是Vector的，而是Arrays的内部类ArrayList的实例。Arrays.ArrayList是一个固定长度的List集合，不允许添加、删除操作，只能遍历访问，否则程序将出现UnsupportedOperationException异常。
Java集合-Queue集合
在Queue接口中定义了如下的方法：
void add(Object e)：添加元素到队尾
boolean offer(Object e)：将指定元素加入队列的尾部，成功返回true
Object element()：获取队列头部的元素，但不是删除该元素
Object remove()：获取头部元素，并删除该元素
Object peek()：获取队列头部的元素，但不是删除，如果为空返回null
Object poll()：获取并删除头部元素，为空，返回null
Queue有一个PriorityQueue实现类，除此外还有一个Deque接口，代表双端队列，即两端可以添加删除元素。其实现类为ArrayDeque和LinkedList两个实现类。
PriorityQueue类
PriorityQueue并不是一个标准的队列，其保存队列的顺序是重新排序了的(按元素的大小)，显然不符合队列的规则。如果调用poll方法，可以看到元素从小到大移出队列。另外需要注意的是，PriorityQueue不允许插入null元素！
它的排序有两种，自然排序、定制排序，排序规则与TreeSet类似：
自然排序：自然排序时，元素必须实现了Comparable接口，而且是同一类的实例。
定制排序：创建队列时，传入一个Comparator对象，该对象负责排序，但是不要求元素实现Comparable接口
Deque接口与ArrayDeque
Deque接口是Queue的子接口，允许对队列两端进行操作，同时，还可以当作“栈”来使用，因为它还有pop、push方法。典型的实现类是ArrayDeque，一个基于数组的双端队列，在创建Deque时，同样可以指定一个numElement元素个数参数，指定Object[ ]数组的长度；如果不指定，则默认长度为16。
ArrayList与ArrayDeque的实现原理差不多，底层采用一个动态的、可再分配的数组实现，初始化可指定初始长度等，当元素个数超出容量时，系统会重新分配一个Object[]数组储存元素。
LinkedList类
LinkedList实现了List接口，是List集合，还实现了Deque接口，可以当双端队列使用，还能当"栈"使用。 但它的实现机制与ArrayList、ArrayDeque的不一样，它两是用数组实现，而LinkedList是以链表的形式来保存元素，随机访问性能较差，但插入、删除操作比较溜！
线性表性能分析
一般来说，数组由一块连续的内存来保存数据，所以数组随机访问性能好，类似的，以数组为底层实现的类，随机访问性能都比较好；而链表的插入、删除操作性能好。综合来讲，还是用ArrayList比较妥。
如果需要遍历：对于ArrayList，Vector集合，使用随机访问方法遍历即可；对于LinkedList集合，采用Iterator迭代器遍历比较好。
如果经常要执行插入、删除操作，可以使用LinkedList集合，而使用以数组为底层的线性表要重新分配内部数组大小，性能较差。
如果有多个线程同时访问，可以使用工具类包装成线程安全的集合。