Java Queue集合

Queue集合

Queue用于模拟队列数据结构。
通常指先进先出（FIFO）的容器。
新元素插入到队尾， 获取元素会返回队头的元素， 通常，不允许随机访问队列中的元素。
Queue 是继承于 Collection接口。

public interface Queue<E> extends Collection<E> {

}

Queue接口中定义了如下的方法：

• add() ：指定元素加入到队列的尾部
• element(): 获取头部元素，但不删除该元素
• offer（）：指定元素加入到队列尾部，如果发现队列已满无法添加的话，会直接返回false。
• peek(): 获取头部元素， 但是不删除， 队列为空，返回 null
• poll(): 获取头部元素，并删除该元素， 队列为空，返回Null
• remove（）：回去头部元素，并删除该元素

PriorityQueue

PriorityQueue 是 Queue的实现类。

public class PriorityQueue<E> extends AbstractQueue<E>
    implements java.io.Serializable {
}

public abstract class AbstractQueue<E>
    extends AbstractCollection<E>
    implements Queue<E> {
}

PriorityQueue 不是绝对标准的队列实现。
PriorityQueue 保存元素的顺序不是按照加入队列的顺序， 而是按照元素的大小重新排序。

        PriorityQueue priorityQueue = new PriorityQueue();
        priorityQueue.offer(4);
        priorityQueue.offer(-2);
        priorityQueue.offer(8);
        priorityQueue.offer(6);

        System.out.println(priorityQueue);
        System.out.println(priorityQueue.poll());
//Output
[-2, 4, 8, 6]
-2

上面输出并没有完全按照大小排序输出，这只是受到toString()方法返回值的影响， 实际上多次 poll(),元素是按照从小到大移出队列。
PriorityQueue 不允许插入 null元素，需要对元素进行排序，
排序有 自然排序 和 定制排序 两种， 和 TreeSet 基本一致。

Deque集合

Deque接口 是 Queue 接口的子接口。 代表双端队列。

public interface Deque<E> extends Queue<E> {

}

Deque 还可当做栈来使用， 包含了 pop() 出栈 和 push（）入栈两个方法。
主要包括以下方法：

• addFirst() ：插入开头
• addLast(): 插入末尾
• descendingIterator(): 返回对应的迭代器，以逆向顺序来迭代队列
• getFirst(): 获取不删除第一个元素
• getLast(): 获取不删除最后一个元素
• offerFirst(): 插入开头
• offerLast(): 插入末尾
• peekFirst():获取不删除第一个元素
• peekLast(): 获取不删除最后一个元素
• pollFirst(): 获取，删除第一个
• pollLast(): 获取， 删除最后一个
• removeFirst()： 获取， 删除一个
• removeFirstOccurrence(): 删除第一次出现的元素
• removeLast（）:获取，删除最后一个
• removeLastOccurrence(): 删除最后一个出现的元素

ArrayDeque 是 Deque的实现类。是基于数组实现的双端队列。
采用动态，可重分配的Object[]数组来存储元素。
可以指定Object[]数组长度，默认为16.

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
{
     public ArrayDeque() {
        elements = new Object[16];
    }
}

ArrayDeque 当 Stack使用

        ArrayDeque stack = new ArrayDeque();
        stack.push("A");
        stack.push("B");
        stack.push("C");
        System.out.println(stack);
        System.out.println(stack.peek());
        System.out.println(stack.pop());
        System.out.println(stack);
//Output
[C, B, A]
C
C
[B, A]

推荐使用 ArrayDeque代替 Stack，Stack是古老的集合， 性能较差。

ArrayDeque 当做队列使用， 先进先出。

        ArrayDeque queue = new ArrayDeque();
        queue.offer("A");
        queue.offer("B");
        queue.offer("C");
        System.out.println(queue);
        System.out.println(queue.peek());
        System.out.println(queue);
        System.out.println(queue.poll());
        System.out.println(queue);
//Output
[A, B, C]
A
[A, B, C]
A
[B, C]

LinkedList

LinkedList 是 List接口的实现类，可以根据索引随机访问， LinkedList还是实现类 Deque的接口。
可以当做双端队列，即可以当 栈， 也可以当 队列

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
}

LinkedList 与 ArrayList, ArrayDeque 的实现机制不同，
ArrayList, ArrayDeque 内部是数组实现，较好的随机访问。
LinkedList 是 链表形式保存元素，随机访问性能较差， 插入，删除性能较好，只需改变指针地址即可。
Vector 也是以数组形式存储元素，因为实现了线程同步功能，同步机制也不好，所以性能各方面都比较差。

性能分析

List是一个线性表接口。
ArrayList是基于数组的线性表
LinkedList 是基于链表的线性表。
Queue代表队列，Deque代表了双端队列。

由于数组是一块连续内存区保存所有的数组，所以随机访问性能最好。
而链表在插入和删除时性能较好。
因此。 ArrayList 比 LinkedList 性能要好。大部分推荐使用ArrayList。

遍历List， 对 ArrayList, Vector, 应该使用随机访问 get来遍历，这样性能好， 对于LinkedList ，应采用 迭代器 Iterator 来遍历。
对于经常插入，删除的大数据量List集合， 可使用 LinkedList. 因为 ArrayList, Vector经常分配数组大小。

地址： https://blog.csdn.net/yonggang7/article/details/86760530