code学习

初识java—(四十三)Queue集合

作者:IT研究僧

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();

}

}

继续阅读