239. 滑动窗口最大值
题目链接：https://leetcode.cn/problems/sliding-window-maximum/
解答：https://programmercarl.com/0239.%E6%BB%91%E5%8A%A8%E7%AA%97%E5%8F%A3%E6%9C%80%E5%A4%A7%E5%80%BC.html
本题为队列的应用。
每次窗口移动的时候，调用que.pop(滑动窗口中移除元素的数值)，que.push(滑动窗口添加元素的数值)，然后que.front()就返回我们要的最大值——我们需要自己实现这个队列
然后再分析一下，队列里的元素一定是要排序的，而且要最大值放在出队口，要不然怎么知道最大值呢
队列没有必要维护窗口里的所有元素，只需要维护有可能成为窗口里最大值的元素就可以了，同时保证队列里的元素数值是由大到小的。那么这个维护元素单调递减的队列就叫做单调队列，即单调递减或单调递增的队列。
设计单调队列的时候，pop，和push操作要保持如下规则：
1. pop(value)：如果窗口移除的元素value等于单调队列的出口元素，那么队列弹出元素，否则不用任何操作
2. push(value)：如果push的元素value大于入口元素的数值，那么就将队列入口的元素弹出，直到push元素的数值小于等于队列入口元素的数值为止
保持如上规则，每次窗口移动的时候，只要问que.front()就可以返回当前窗口的最大值。
347.前 K 个高频元素
题目链接：https://leetcode.cn/problems/top-k-frequent-elements/
解答：https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html
题目内容：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
条件：
1. 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
2. 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
大顶堆和小顶堆：底层数据结构是二叉树
优先级队列的底层实现就是堆，可以使用优先级队列实现大顶堆和小顶堆。
Java 优先级队列介绍：https://blog.csdn.net/sheng0113/article/details/123140959
优先级队列可以保证每次取出来的元素都是队列中的最小或最大的元素，即小顶堆和大顶堆（Java优先级队列默认每次取出来的为最小元素）
PriorityQueue是Queen接口的一个实现类，而Queen接口是Collection接口的一个实现类，因此其拥有Collection接口的基本操作（add，remove，element），此外，队列还提供了其他的插入（offer），移除（poll）和查询（peek）的操作。
注意⚠️：优先级队列中不可以存储null
优先级队列默认每次获取队列中最小的元素，也可以通过comparator比较器来自定义每次获取为最小还是最大。
Java 优先级队列详解：https://blog.csdn.net/m0_51013067/article/details/126521551
PriorityQueue <Integer> heap = new PriorityQueue<>( (n1,n2) -> n1-n2; //这一句加不加结果是一样的
如果改成n2-n1，就会变成大顶堆：
优先队列内部是按照比较器返回的结果进行处理的，一般认为a,b两个值，比较结果大于0就是a大于b，a下沉；等于0就是a等于b；小于0就是a小于b，b下沉；现在我们知道当比较n1,n2的时候，如果结果大于0(也就是默认的n1-n2>0)，那么要把n1下沉(默认的小根堆)，当我们改成n2-n1的时候，结果大于0，证明n2大于n1，但还是n1（值较小的元素）下沉，于是这个堆就成了大顶堆。
自定义comparator比较器：
就像TreeSet一样，一个priority queue要么存储的是实现了Comparable接口的元素，要么在构造函数中传入一个Comparator对象。
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
//自定义比较类，升序排列
static Comparator<ListNode> cLNode = new Comparator<ListNode>() {
public int compare(ListNode o1, ListNode o2) {
return o1.val-o2.val; }
};
public static void main(String[] args) {
//自定义类的优先队列需要重写比较类作为传入参数
Queue<ListNode> que = new PriorityQueue<>(cLNode);
//简单写法
// Queue<ListNode> que = new PriorityQueue<>((v1, v2) -> v1.val - v2.val);
}
Comparable接口：
public interface Comparable<T> {
public int compareTo (T o);
}
该接口只存在一个public int compareTo(T o);方法，该方法表示所在的对象和o对象进行比较，返回值分三种：
1： 表示当前对象大于o对象
0： 表示当前对象等于o对象
-1： 表示当前对象小于o对象
在优先级队列中或者具有比较特征的集合中存储的对象需要实现Comparable接口。
例子🌰：
需求： 在优先级队列中存储对象学生，每个学生有id，name，age三个属性，并且使优先级队列每次按照学生的id从小到大取出。
Student类： 当前类实现了Comparable接口，即当前类提供了默认的比较方法。
public class Student implements Comparable{
private int id;
private String name;
private int age;
public Student(int id, String name, int age) {
this.id = id;
this.name = name;
this.age = age;
}
@Override
public int compareTo (Object o) {
Student o1 = (Student)o;
return this.id - o1.id;
}
}
优先队列 pq 中的元素个数最多是 k，所以一次 poll 或者 add 方法的时间复杂度是 O(logk)；所有的链表节点都会被加入和弹出 pq，所以算法整体的时间复杂度是 O(Nlogk)，其中 k 是链表的条数，N 是这些链表的节点总数。
栈与队列总结：https://programmercarl.com/%E6%A0%88%E4%B8%8E%E9%98%9F%E5%88%97%E6%80%BB%E7%BB%93.html
用队列模拟栈 优化版：
其实这道题目就是用一个队列就够了
思路：
一个队列在模拟栈弹出元素的时候只要将队列头部的元素（除了最后一个元素外） 重新添加到队列尾部，此时再去弹出元素就是栈的顺序了
