初识java—（四十三）Queue集合

8.5 Queue集合

Queue用于模拟队列数据结构，队列是遵循“先进先出”，“后进后出”的存储规范。第一个存放的元素对象存放在队列队首位置，后进入的元素插入到队尾的位置，队列不允许随机访问队列中元素。

Queue接口定义的方法：

Ø Void add(Object obj)：将指定元素加入此队列的尾部。

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

Ø Boolean offer(Object obj)：将指定元素加入此队列的尾部，当使用有容量限制的队列时，此方法比add()方法更好。

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

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

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

实例1：

创建一个容量有限的队列 ArrayBlockingQueue

ArrayBlockingQueue<String> abq = new ArrayBlockingQueue<String>(2);

abq.add(“hello”);

abq.add(“world”);

System.out.println(abq.size);

System.out.println(abq);

abq.add(“langsin”);

System.out.println(abq.size);

System.out.println(abq);

8.5.1 PriorityQueue实现类

PriorityQueue是一个比较标准的Queue实现类，而不是绝对标准的队列实现，是因为PriorityQueue保存队列元素的顺序并不是按照加入队列的顺序进行保存。而是按照队列元素的大小进行重新一次排序。因此使用peek()或者poll()方法获取元素队列位置时，并不一定就是首先存入的元素对象，而是队列中最小的元素。

举例1：

public static void main(String[] args) throws Exception{

pq = new ();

;

;

;

;

System.out.println(pq.toString()); //

while(pq.size()>0){

System.out.print(pq.poll() + " "); // -3 3 6 9

}

}

注意：PriorityQueue不允许插入null值，它需要对队列元素进行排序，PriorityQueue的元素排序分两种情况，自然排序和定制排序，参照TreeSet。

8.5.2 Deque接口与ArrayDeque实现类

Deque接口是Queue接口的子接口，它代表一个双端队列，Deque接口里定义了一些双端队列的方法，这些方法允许从两端来操作队列元素。

Ø void addFirst(Object obj)：将指定元素插入到该队列的首部。

Ø void addlast(Object obj)：将指定元素插入到该队列的尾部。

Ø Iterator desceningIterator()：返回该双端队列对应的迭代器，该迭代器将以逆向顺序来迭代队列中的元素。

Ø Object getFirst()：获取双端队列的第一个元素。

Ø Object getLast()：获取双端队列的最后一个元素。

Ø Boolean offerFirst(Object obj)：将指定元素插入到双端队列的开头。

Ø Boolean offerLast(Object obj)：将指定元素插入到双端队列的末尾。

Ø Object peekFrist()：获取但不删除双端队列的第一个元素。

Ø Object peekLast()：获取但不删除双端队列的最后一个元素。

Ø Object pollFrist()：获取并删除双端队列的第一个元素。

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

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

Ø void push(Object obj)：将一个元素插入到该双端队列的队首位置，相当于addFrist()

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

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

举例1：

public static void main(String[] args) throws Exception{

deque = new();

;

;//相当于offerLast()

;

System.out.println(deque);

; //相当于offerFirst()

System.out.println(deque);

System.out.println(deque.size());

Object obj = deque.peek(); //相当于peekFirst()

System.out.println(obj);

System.out.println(deque.size());

obj = deque.poll();//相当于pollFist()

System.out.println(obj);

System.out.println(deque.size());

}

8.5.3 LinkedList实现类

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

举例1：

public static void main(String[] args) throws Exception{

list = new();

; abc 789 123 456

;

//System.out.println(list);

;

//System.out.println(list);

;

System.out.println(list);

Object obj = list.pop();

System.out.println(obj);

System.out.println(list.size());

}

LinkedList与ArrayList、ArrayDeque的实现机制不同，ArrayList和ArrayDeque内部以数组的形式来保存集合中元素，因此随机访问集合元素时有较好的性能。而LinkedList内部以链表的形式来保存集合中的元素，因此随机访问集合元素时性能不如ArrayList和ArrayDeque。而插入、删除元素时性能非常出色，只需要改变指针所指向的地址即可。

这里有一个问题，请用LinkedList模拟栈数据结构的集合，并测试。

首先分析这个题目的意思，你自己定义一个集合类，在这个集合类内部可以使用LinkedList模拟。这个集合最终是个栈结构的集合。

public class MyStack{

private LinkedList link;

public MyStack(){

link = new LinkedList();

}

public void add(Object obj){

link.addFirst(obj);

}

public Object get(){

//(1)第一种做法。每次都拿到了，然而，再来拿的时候，还是拿的第一个。而栈内存提取数据的时候是拿到一个踢除一个，剩下的往上移一位。拿一个往上走一位。所以我们用下边的那个方法，拿到第一个了并踢除了。所以你下次拿的时候才会拿到新的内容。要不然你拿到的永远都是第一个。

//return link.getFirst();

return link.removeFirst();

}

//这里要添加这么一个方法，防止你拿数据的时候拿到了空的位置的时候该怎么办。有了这个方法，我们就可以用while()循环来写代码了。

public Boolean isEmpty(){

return link.isEmpty();

}

}