数据结构与算法（队列）~ 介绍队列以及力扣上几道队列题目的方法和套路

 

✿队列的概念以及特点：只允许在表的前端（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;
    }