集合框架之队列

小tips：本文通过Java语言实现，希望你尽量知道一些关于集合框架的知识点，如果不太清楚也可以访问我的入门文章：集合框架

集合框架中的队列 Queue

接口方法

Queue用于模拟队列这种数据结构，队列通常是指先进先出的容器

方法 描述
void add(Object e) 将指定元素加入此队列的尾部
Object element() 获取队列头部的元素，但是不删除该元素
boolean offer(Object e) 将指定元素加入队列的尾部。当使用有容积限制的队列时，此方法比add要好
Object peek() 获取队列头部的元素，但是不删除。如果队列为空则返回null
Object poll() 获取队列头部的元素并删除。如果队列为空则返回null
Object remove() 获取队列头部的元素并删除。

PriorityQueue实现类

PriorityQueue是一个比较标准的队列实现类，不过它保存队列元素的顺序并不是按加入队列的顺序，而是按照、队列的大小进行重新排序过后的。该类类似于TreeSet的标准，不允许插入null元素，排序规则可以通过实现Comparable接口。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.PriorityQueue;

public class PriorityQueueTest {
	public static void main(String[] args) {
		PriorityQueue pg = new PriorityQueue();
		
		//下面依次向pg中加入四个元素
		pg.offer(6);
		pg.offer(-3);
		pg.offer(20);
		pg.offer(18);
		
		//输出pg队列，并不是按照元素的加入顺序排列
		System.out.println(pg);
		
		System.out.println(pg.poll());
	}
}

Deque接口与ArrayDeque实现类

Deque接口是Queue接口的子接口，它代表一个双端队列。

方法 描述
void addFirst(Object e) 将指定元素加入此队列的开头
void addLast(Object e) 将指定元素加入此队列的末尾
Iterator descendingIterator() 返回该双端队列对应的迭代器，该迭代器将以逆向顺序来迭代队列中的元素
boolean offer(Object e) 获取但不删除双端队列的第一个元素
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(e)
Object removeFirst() 获取并删除该双端队列的第一个元素
Object removeFirstOccurrence(Object e) 删除双端队列的第一次出现的元素o
Object removeLast() 获取并删除该双端队列的最后一个元素
boolean removeLastOccurrence(Object o) 删除该双端队列的最后一次出现的元素o

看见那么多方法不要害怕，很多都是取出前端或是取出最后一个的。而且该接口既可以当作栈来使用，也可以用来当队列使用。下面是把该实现类 ArrayDeque 当做栈使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.ArrayDeque;

public class ArrayDequeStack {
    public static void main(String[] args) {
        ArrayDeque stack = new ArrayDeque();
        
        //依次将三个元素push入栈
        stack.push("鲁班大师");
        stack.push("吕布");
        stack.push("安其拉");

        //输出栈的所有内容
        System.out.println(stack);
        //访问第一个元素，但是不将其pop出栈
        System.out.println(stack.peek());
        //访问第一个元素，并出栈
        System.out.println(stack.pop());
        //重新打印栈内容
        System.out.println(stack);
    }
}

下面是把 ArrayDeque 实现类当作队列使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
import java.util.ArrayDeque;
import java.util.Deque;

public class ArrayDequeQueue {
	public static void main(String[] args) {
		
		Deque queue = new ArrayDeque();
		//依次将三个元素加入队列
		queue.offer("鲁班大师");
		queue.offer("吕布");
		queue.offer("安其拉");
		
		//输出队列内容
		System.out.println(queue);
		
		//访问头部元素
		System.out.println(queue.peek());
		
		//poll第一个元素，弹出队列
		System.out.println(queue.poll());
		
		//输出队列内容
		System.out.println(queue);
	}
}

ArrayList和ArrayDeque两个集合类的实现机制基本相似，它们的底层都采用一个动态的、可重分配的Object[] 数组来存储集合元素，当集合元素超过了容积时，系统会重新分配一个Object[] 数组来储存集合元素。

LinkedList实现类

LinkedList类是List接口的实现类，这说明他可以用索引来随机访问集合中的元素，除此之外LinkedList还实现了Deque接口，所以也可以当成双端队列来使用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.util.LinkedList;

public class LinkedListTest {
	public static void main(String[] args) {
		LinkedList books = new LinkedList();
		
		//将字符串加入尾部
		books.offer("鲁班大师");
		
		//将字符串加入顶部
		books.push("吕布");
		
		//将字符串添加到队列的头部，相当于栈的顶部
		books.offerFirst("亚瑟");
		
		//以List的方式遍历
		for(int i=0;i<books.size();i++) {
			System.out.println("List方式遍历:"+books.get(i));
		}
		
		//访问并不删除栈顶的元素
		System.out.println(books.peekFirst());
		
		//访问并不删除队列的最后一个元素
		System.out.println(books.peekLast());
		
		//将栈顶的元素弹出栈
		System.out.println(books.poll());
		
		//下面队列中第一个元素被删除
		System.out.println(books);
		
		//访问并删除最后一个元素
		System.out.println(books.pollLast());
		
		//重新打印队列
		System.out.println(books);
	}
}

LinkedList是一个功能非常强大的集合类

各种线性表的性能比较

一般来说，由于数组以是用连续的内存空间来报错所有的数组元素，所有数组在随机访问时性能最好，所以内部以数组为底层实现的集合在随机访问的性能上都比较好；而内部以链表为底层实现的集合在执行插入，删除操作时有较好的性能。但总体来说：ArrayList（也包括底层用Array的，后面一样）的性能比LinkedList的性能更好，因此大部分时候都应该考虑用ArrayList。

如果需要遍历List集合元素，对于ArrayList，应该使用随机访问（get）这样性能更好。对于LinkedList集合，则应该采用迭代器来遍历集合元素。

如果需要经常插入，删除包含大量数据的List集合的大小，可考虑使用LinkedList集合。

如果有多个线程需要同时访问List集合中的元素，可考虑使用Collections将集合包装成线程安全的集合。