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

本文主要是介绍数据结构与算法（队列）~ 介绍队列以及力扣上几道队列题目的方法和套路，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

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

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

这篇关于数据结构与算法（队列）~ 介绍队列以及力扣上几道队列题目的方法和套路的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！