【Java—–Queue集合详解】

Queue集合概述

Queue用于模拟队列这种数据结构，队列通常是指先进先出的容器。新元素插入（offer）到队列的尾部，访问元素（poll）操作会返回队列头部的元素。通常，队列不允许随机访问队列中的元素。Queue继承于Collection接口，Queue接口中定义了如下方法：

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

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

boolean offer(Object e)：将指定元素加入该队列的尾部，当使用有容量限制的队列时，此方法通常比void add(Object e)方法更好，使用此方法时，如果发现队列已满无法添加时，会直接返回false

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

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

Object remove()：获取队列头部的元素，并删除该元素，队列为空时抛出异常NoSuchElementException

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

PriorityQueue实现类

PriorityQueue实现类保存队列元素的顺序并不是按加入队列的顺序，而是按队列元素的大小进行重新排序，因此当调用peek()或poll()方法取出队列中的元素时，并不是取出最先进入队列的元素，而是取出队列中最小的元素。注意：因为PriorityQueue是进行排序的，所以不允许插入的元素为null。示例代码如下：

public class Queuetest {
	public static void main(String[] args) {
		PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
		queue.offer(3);
		queue.offer(9);
		queue.offer(2);
		queue.offer(-1);
		System.out.println(queue);
		System.out.println(queue.poll());
		System.out.println(queue.poll());
	}
}
/*输出：[-1, 2, 3, 9]
        -1
        2
*/

Deque接口

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

void push(Object e)（栈方法）：将指定元素push进该双端队列所表示的栈的栈顶，相当于addFirst(Object e)

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

Object removeFirstOccurrence(Object 0)：删除该双端队列的第一次出现的元素

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

boolean removeLastOccurrence(Object 0)：删除该双端队列的最后一次出现的元素

ArrayDeque

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

ArrayDeque当Stack使用

public class Queuetest {
	public static void main(String[] args) {
		ArrayDeque<String> stack=new ArrayDeque<String>();
		stack.push("a");
		stack.push("b");
		stack.push("c");
		System.out.println(stack);
		System.out.println(stack.pop());
		System.out.println(stack.peek());
		System.out.println(stack);
		
	}
}
/*输出：[c, b, a]
        c
        b
        [b, a]
*/

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

ArrayDeque当作队列使用，先进先出

public class Queuetest {
	public static void main(String[] args) {
		ArrayDeque<String> queue=new ArrayDeque<String>();
		queue.offer("x");
		queue.offer("y");
		queue.offer("z");
		System.out.println(queue);
		System.out.println(queue.poll());
		System.out.println(queue.peek());
		System.out.println(queue);
	}
}
/*输出：[x, y, z]
        x
        y
        [y, z]
*/

LinkedList

LinkedList是List接口的实现类，可以根据索引随机访问集合中的元素，LinkedList还实现了Deque接口，可以被当成双端队列来使用，因此既可以被当成栈来使用，也可以当成队列使用。

public class Queuetest {
	public static void main(String[] args) {
		LinkedList<Integer> list=new LinkedList<Integer>();
		list.offer(1);//将数字1加入队列的尾部
		list.push(2);//将数字2加入栈顶
		list.offerFirst(3);//将数字3添加到队列的头部（相当于栈的顶部）
		System.out.println(list);
		list.pop();//弹出栈顶的元素
		System.out.println(list);
		System.out.println(list.pollLast());//访问并删除队列的最后一个元素
		System.out.println(list);
		
	}
}
/*输出：[3, 2, 1]
        [2, 1]
        1
        [2]
*/

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