【JavaSE】十一、Stack Queue Deque PriorityQueue Map Set

Ⅰ. Stack（不推荐使用了☠）

常见方法如下所示：

其中peek()就相当于是std::stack中的top()。

注意事项：

1. 在比较元素相同的时候，要使用equals()，因为就算存储的是整数Stack<Integer>类型，里面仍然是引用类型，不能直接通过==来比较！

2. 因为Stack继承于Vector，而Vector中还有很多实用的方法比如size()方法等，都是可以使用的，但由于Vector比较老，并且这种设计违反了最小接口原则，所以现在不推荐使用Stack，而是用Deque来替代！（如下面代码所示）

   1. Java推荐使用Deque接口的实现类，比如：
      1. ArrayDeque
      2. LinkedList

      Deque<Integer>stack=newArrayDeque<>();// 使用Deque代替Stackstack.push(1);// 入栈stack.pop();// 出栈stack.peek();// 查看栈顶stack.isEmpty();// 是否为空

Ⅱ. Queue

注意事项：

• Queue 是一个接口，要使用实现类来实现，常用LinkedList、ArrayDeque、PriorityQueue来实现！
• 一个队列可以实现栈，但是一个栈实现不了队列！225. 用队列实现栈、232. 用栈实现队列

Ⅲ. Deque

Deque是一个接口，使用时必须创建LinkedList或者ArrayDeque类型的对象。在实际工程中，使用Deque接口是比较多的，栈和队列均可以使用该接口。

Deque<Integer>stack=newArrayDeque<>();// 双端队列的线性实现Deque<Integer>queue=newLinkedList<>();// 双端队列的链式实现

Ⅳ. PriorityQueue

Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，下面主要介绍PriorityQueue。

使用注意事项：

1. 使用时必须导入包：import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出ClassCastException异常。
3. 不能插入null对象，否则会抛出NullPointerException。
4. PriorityQueue默认情况下是小堆。
5. 创建自定义大小堆的比较器写法如下所示：（以Integer为例）

// 推荐使用 Comparator 而不是 Comparable，因为前者比较灵活、侵入性小// 创建小堆classlesscmpimplementsComparator<Integer>{@Overridepublicintcompare(Integero1,Integero2){returno1.compareTo(o2);}}// 创建大堆classgreatercmpimplementsComparator<Integer>{@Overridepublicintcompare(Integero1,Integero2){returno2.compareTo(o1);}}publicstaticvoidmain(String[]args){PriorityQueue<Integer>pq=newPriorityQueue<>();// 默认为小堆pq.add(10);pq.add(20);pq.add(15);while(!pq.isEmpty()){System.out.println(pq.poll());};PriorityQueue<Integer>pq1=newPriorityQueue<>(newgreatercmp());pq1.add(10);pq1.add(20);pq1.add(15);while(!pq1.isEmpty()){System.out.println(pq1.poll());}// 使用lambda表达式创建大堆PriorityQueue<Integer>pq2=newPriorityQueue<>((o1,o2)->{returno1.compareTo(o2)});pq2.add(10);pq2.add(20);pq2.add(15);while(!pq2.isEmpty()){System.out.println(pq2.poll());}}// 运行结果101520201510201510

堆排序

• 升序：建大堆
• 降序：建小堆
• 时间复杂度：O(nlogn)

Ⅴ. Map

Map是一个接口类，该类没有继承自Collection，该类中存储的是<K,V>结构的键值对，并且K一定是唯一的，不能重复。

https://docs.oracle.com/javase/8/docs/api/index.html

☠注意事项：

1. 内置类型不能直接来实例化HashMap，必须要找其对应的包装类型
2. 在TreeMap中的key不能为空，否则就会抛NullPointerException异常，value可以为空；而HashMap的key和value都可以为空。
3. Map中键值对的Key不能直接修改，value可以修改，如果要修改key，只能先将该key删除掉，然后再来进行重新插入。
4. HashMap的底层实现中，当某个桶中链表元素超过8个，并且桶的个数超过64个，此时会将该桶中的链表转化为红黑树维护，降低高度！
5. 采用方法如下所示：

1. 其中getOrDefalut()方法通常用于统计次数的时候简化代码，如下所示：

   publicList<String>topKFrequent(String[]words,intk){// 统计字符串出现个数Map<String,Integer>hash=newHashMap<>();for(inti=0;i<words.length;++i){hash.put(words[i],hash.getOrDefault(words[i],0)+1);// 这样子来简化代码}...}

2. Map（如HashMap、TreeMap等） 自身没有迭代器，即没有实现Iterator接口，但它的视图对象（keySet、entrySet、values）都可以迭代，如下所示：

   // 遍历 keySet()（只要 key）for(Kkey:map.keySet()){System.out.println(key);}// 遍历 values()（只要 value）for(Vvalue:map.values()){System.out.println(value);}// 遍历 entrySet()（需要 key 和 value）⭐⭐⭐⭐⭐⭐⭐（推荐）for(Map.Entry<K,V>entry:map.entrySet()){System.out.println(entry.getKey()+" = "+entry.getValue());}

3. 上述的entrySet()是Map接口中的一个方法，返回一个包含了所有 键值对 的Set集合，这些键值对就是Map.Entry<K, V>对象，它们每一个都包含两个元素：key和value。

   // 也就是说上面的for-each可以转化为迭代器来处理，如下所示：（这里只举例entrySet）Iterator<Map.Entry<String,Integer>>it=map.entrySet().iterator();while(it.hasNext()){System.out.println(it.next().getKey()+" "+it.next().getValue());}

4. TreeMap和HashMap的区别如下图所示。其中因为HashMap在比较内容的时候是根据hashCode()来确定key是在哪个桶中的，而根据equals()来确定是桶中的哪个元素，所以在HashMap中存放自定义类型的时候，需要重写该自定义类型的equals()和hashCode()方法。

Ⅵ. Set

Set与Map主要的区别：

1. Set是继承自Collection的接口类
2. Set中只存储了Key。

但实际上底层源码实现是让Set去调用Map的接口，只不过传入的value是一个默认的Object对象，而只需要关心key即可。

常用方法如下所示：

注意事项：

1. Set最大的功能就是对集合中的元素进行去重
2. 实现Set接口的常用类有TreeSet和HashSet，还有一个LinkedHashSet，LinkedHashSet是在HashSet的基础上维护了一个双向链表来记录元素的插入次序。
3. TreeSet中不能插入null的key，而HashSet可以。