数据结构与算法（队列）~ 介绍队列以及力扣上几道队列题目的方法和套路
✿队列的概念以及特点：只允许在表的前端（front）进行删除操作，在表的后端（rear）进行插入操作的线性表。特点: 先进先出
1，队列的数据结构：
（1）实现队列特点（使用 双端队列 Deque （实现了 Queue），Deque 的子类 LinkedList 双向链表 便可完美实现 队列 的功能特性）】
（2）队列主要的功能（增删改查）：定义一些接口方法：
2，队列的力扣算法题：
总结一些小套路吧 （没有通用的套路，就讲一下方法哈）：
（1）232_用栈实现队列 的方法和套路 ：
方法一：用俩个栈即可（同理，用队列 实现栈，用俩个队列即可）~ 原材料可以多份嘛（而且栈特点：后进先出，队列特点：先进先出）~双份即可实现。
（2）239_滑动窗口最大值 的方法和套路 ：
套路一：① 整个题目对于范围（窗口范围都需要进行判断）~而且给的又是一个数组，就直接利用索引！
② 这个窗口会进行移动【原先的最大值，不在这个窗口范围式，就不考虑它，pop 掉，考虑新进来的（可以使用 队列~ 移动过程中可以从尾巴进入数据，从头pop 掉不再范围内的原先最大值 ~ 这个队列还是一个从头到尾是头部最大~ 尾部最小的队列（单调队列））】
思路：有一个 一直维持是 单调递减的队列；然后咱先形成 k 区间的 窗口； 然后，
剩下的一步一个新窗口，需要考虑当前存储在队列队头的最大值（索引），是否还在新的窗口的左边（不在就pop掉它）
public int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; //创建双端队列 Deque<Integer> deque = new LinkedList<Integer>(); //先初始化前K个元素 for (int i = 0; i < k; i++) { //判断队列是否为空 或者当前入队元素是否大于队尾元素 大于则出队 while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } //当前元素入队 //由于需要判断当前元素是否在窗口中，所以实际上队列中存储的为当前元素的下标 //根据下标找元素比根据元素找下标方便 deque.offerLast(i); } int[] ans = new int[n - k + 1]; //添加当前最大元素 ans[0] = nums[deque.peekFirst()]; for (int i = k; i < n; i++) { //判断队列是否为空 或者当前入队元素是否大于队尾元素 大于则出队 while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) { deque.pollLast(); } //当前元素入队 deque.offerLast(i); //循环判断队首元素是否在窗口中，窗口的左边界为i-k while (deque.peekFirst() <= i - k) { deque.pollFirst(); } //添加答案 ans[i - k + 1] = nums[deque.peekFirst()]; } return ans; }
✿ 优先队列套路--------举例：215_数组中的第K个最大元素
套路：使用小根堆【当海量数据进行筛选之后，都是比较大的数，堆顶是这些比较大的数中最小的数】
//小根堆 PriorityQueue<Integer> pQueue = new PriorityQueue<Integer>();//默认比较器就是升序的【小根堆】 //逻辑：先存储进去 k容量数据【小根堆】，跟堆顶比【堆顶太小了，抛弃，【调整一个新的最小值于堆顶】，当前值进入维持容量k】 //每次都抛弃掉最小的【堆顶】，更换进入大的，剩下的就是大的数据呀
