映射Map、队列Queue、优先级队列PriorityQueue

时间:2022-05-24 14:35:21

映射Map

映射Map、队列Queue、优先级队列PriorityQueue

将对象映射到其他对象的能力是解决编程问题的有效方法。例如,考虑一个程序,它被用来检查 Java 的 Random 类的随机性。理想情况下, Random 会产生完美的数字分布,但为了测试这一点,则需要生成大量的随机数,并计算落在各种范围内的数字个数。 Map 可以很容易地解决这个问题。在本例中,键是 Random 生成的数字,而值是该数字出现的次数:

/**
* 利用Map计数
* @author myf
*/
public class Statistics {
public static void main(String[] args) {
Random random = new Random(30);
Map<Integer,Integer> map = new HashMap<>(50);
for (int i = 0; i < 1000; i++) {
int a = random.nextInt(20);
Integer b = map.get(a);
map.put(a,b==null?1:(b+1));
}
System.out.println(map);
//{0=57, 1=53, 2=54, 3=54, 4=60, 5=46, 6=52, 7=46, 8=52, 9=44, 10=40,
// 11=53, 12=40, 13=47, 14=54, 15=52, 16=55, 17=56, 18=51, 19=34}
}
}

通过使用 containsKey() 和 containsValue() 方法去测试一个 Map ,以查看它是否包含某个键或某个值:

// true
System.out.println(map.containsKey(10));
// false
System.out.println(map.containsKey(30));
//不一定视生成情况
System.out.println(map.containsValue(10));
System.out.println(map.containsValue(60));

Map 与数组和其他的 Collection 一样,可以轻松地扩展到多个维度,只需要创建一个值为 Map 的 Map(这些 Map 的值可以是其他集合,甚至是其他 Map)。因此,能够很容易地将集合组合起来以快速生成强大的数据结构。例如,假设你正在追踪有多个宠物的人,只需要一个 Map<Person, List> 即可:
Map 可以返回由其键组成的 Set ,由其值组成的 Collection ,或者其键值对的 Set 。 keySet() 方法生成由在 petPeople 中的所有键组成的 Set ,它在 for-in 语句中被用来遍历该 Map 。

 //[0=57, 1=53, 2=54, 3=54, 4=60, 5=46, 6=52, 7=46, 8=52, 9=44,
// 10=40, 11=53, 12=40, 13=47, 14=54, 15=52, 16=55, 17=56, 18=51, 19=34]
System.out.println(map.entrySet());
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
System.out.println(map.keySet());
// [57, 53, 54, 54, 60, 46, 52, 46, 52, 44, 40, 53, 40, 47, 54, 52, 55, 56, 51, 34]
System.out.println(map.values());

队列Queue

队列是一个典型的“先进先出”(FIFO)集合。 即从集合的一端放入事物,再从另一端去获取它们,事物放入集合的顺序和被取出的顺序是相同的。队列通常被当做一种可靠的将对象从程序的某个区域传输到另一个区域的途径。队列在并发编程中尤为重要,因为它们可以安全地将对象从一个任务传输到另一个任务。
LinkedList 实现了 Queue 接口,并且提供了一些方法以支持队列行为,因此 LinkedList 可以用作 Queue 的一种实现。 通过将 LinkedList 向上转换为 Queue 。

/**
* @author myf
*/
public class QueueDemo {
public static void main(String[] args) {
Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
queue.add(3);
pringQueue(queue);
} public static void pringQueue(Queue<Integer> queue){
while (queue.peek()!=null){
System.out.println(queue.poll());
}
}
}

offer() 是与 Queue 相关的方法之一,它在允许的情况下,在队列的尾部插入一个元素,或者返回 false 。 peek() 和 element() 都返回队头元素而不删除它,但是如果队列为空,则 element() 抛出 NoSuchElementException ,而 peek() 返回 null 。 poll() 和 remove()* 都删除并返回队头元素,但如果队列为空,poll() 返回 null ,而 remove() 抛出 NoSuchElementException 。

自动包装机制会自动将 nextInt() 的 int 结果转换为 queue 所需的 Integer 对象,并将 char c 转换为 qc 所需的 Character 对象。 Queue 接口窄化了对 LinkedList 方法的访问权限,因此只有适当的方法才能使用,因此能够访问到的 LinkedList 的方法会变少(这里实际上可以将 Queue 强制转换回 LinkedList ,但至少我们不鼓励这样做)。

与 Queue 相关的方法提供了完整而独立的功能。 也就是说,对于 Queue 所继承的 Collection ,在不需要使用它的任何方法的情况下,就可以拥有一个可用的 Queue 。
映射Map、队列Queue、优先级队列PriorityQueue

优先级队列PriorityQueue

映射Map、队列Queue、优先级队列PriorityQueue

先进先出(FIFO)描述了最典型的队列规则(queuing discipline)。队列规则是指在给定队列中的一组元素的情况下,确定下一个弹出队列的元素的规则。先进先出声明的是下一个弹出的元素应该是等待时间最长的元素。
优先级队列声明下一个弹出的元素是最需要的元素(具有最高的优先级)。例如,在机场,当飞机临近起飞时,这架飞机的乘客可以在办理登机手续时排到队头。如果构建了一个消息传递系统,某些消息比其他消息更重要,应该尽快处理,而不管它们何时到达。在Java 5 中添加了 PriorityQueue ,以便自动实现这种行为。
当在 PriorityQueue 上调用 offer() 方法来插入一个对象时,该对象会在队列中被排序。[^5]默认的排序使用队列中对象的自然顺序(natural order),但是可以通过提供自己的 Comparator 来修改这个顺序。 PriorityQueue 确保在调用 peek() , poll() 或 remove() 方法时,获得的元素将是队列中优先级最高的元素。

/**
* 优先级队列
* @author myf
*/
public class PriorityQueueDemo {
public static void main(String[] args) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
for (int i = 0; i < 10; i++) {
priorityQueue.offer(i);
}
PriorityQueueDemo.pringQueue(priorityQueue); List<Integer> ints = Arrays.asList(25, 22, 20,
18, 14, 9, 3, 1, 1, 2, 3, 9, 14, 18, 21, 23, 25);
priorityQueue = new PriorityQueue<>(ints);
PriorityQueueDemo.pringQueue(priorityQueue);
priorityQueue = new PriorityQueue<>(
ints.size(), Collections.reverseOrder());
priorityQueue.addAll(ints);
PriorityQueueDemo.pringQueue(priorityQueue); String fact = "EDUCATION SHOULD ESCHEW OBFUSCATION";
List<String> strings =
Arrays.asList(fact.split(""));
PriorityQueue<String> stringPQ =
new PriorityQueue<>(strings);
PriorityQueueDemo.pringQueue2(stringPQ);
stringPQ = new PriorityQueue<>(
strings.size(), Collections.reverseOrder());
stringPQ.addAll(strings);
PriorityQueueDemo.pringQueue2(stringPQ); Set<Character> charSet = new HashSet<>();
for(char c : fact.toCharArray()) {
charSet.add(c);
}
PriorityQueue<Character> characterPQ =
new PriorityQueue<>(charSet);
PriorityQueueDemo.pringQueue3(characterPQ);
} public static void pringQueue(Queue<Integer> queue){
while (queue.peek()!=null){
System.out.print(queue.poll()+" ");
}
System.out.println();
} public static void pringQueue2(Queue<String> queue){
while (queue.peek()!=null){
System.out.print(queue.poll()+" ");
}
System.out.println();
} public static void pringQueue3(Queue<Character> queue){
while (queue.peek()!=null){
System.out.print(queue.poll()+" ");
}
System.out.println();
}
}

PriorityQueue 是允许重复的,最小的值具有最高的优先级(如果是 String ,空格也可以算作值,并且比字母的优先级高)。为了展示如何通过提供自己的 Comparator 对象来改变顺序,第三个对 PriorityQueue 构造器的调用,和第二个对 PriorityQueue 的调用使用了由 Collections.reverseOrder() (Java 5 中新添加的)产生的反序的 Comparator 。
最后一部分添加了一个 HashSet 来消除重复的 Character。

Integer , String 和 Character 可以与 PriorityQueue 一起使用,因为这些类已经内置了自然排序。如果想在 PriorityQueue 中使用自己的类,则必须包含额外的功能以产生自然排序,或者必须提供自己的 Comparator 。