队列-我的基础算法刷题之路（六）

在这里插入图片描述

本篇博客旨在整理记录自已对队列的一些总结，以及刷题的解题思路，同时希望可给小伙伴一些帮助。本人也是算法小白，水平有限，如果文章中有什么错误之处，希望小伙伴们可以在评论区指出来，共勉 💪。
本篇文章主要是讲一下基本的队列以及刷题，暂不过多涉及双端、阻塞队列。

文章目录

    • 一、队列的概述
    • 二、Java队列的特性
    • 三、Java 队列的基本操作
    • 四、队列的代码实现
      • 4.1、链表实现
      • 4.2、数组实现
    • 五、刷题
      • 1. 二叉树层序遍历
      • 2. 设计循环队列
    • 最后

一、队列的概述

队列(queue) 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品。队列遵循先入先出、后入后出的基本原则。

队列的基本结构：
1
2
3
4
进队
出队

二、Java队列的特性

队列主要分为阻塞和非阻塞，有界和无界；按功能分：双端队列、优先队列、延迟队列、其他队列
Queue
按阻塞分类
按大小分类
按功能分类
阻塞队列
非阻塞队列
有界队列
无界队列
普通队列
优先队列
双端队列
延迟队列
其他队列

三、Java 队列的基本操作

  • add(E e)：将元素 e 插入到队列末尾，如果插入成功，则返回 true；如果插入失败（即队列已满），则会抛出异常；
  • remove()：移除队首元素，若移除成功，则返回 true；如果移除失败（队列为空），则会抛出异常；
  • remove(Object o)：移除指定的元素，若移除成功，则返回 true；如果移除失败（队列为空），则会抛出异常；
  • offer(E e)：将元素 e 插入到队列末尾，如果插入成功，则返回 true；如果插入失败（即队列已满），则返回 false；
  • poll()：移除并获取队首元素，若成功，则返回队首元素；否则返回 null；
  • peek()：获取队首元素，若成功，则返回队首元素；否则返回 null；
  • isEmpty()：队列是否为空；
  • size()：队列长度；

四、队列的代码实现

定义一个简化的队列接口：

public interface Queue<E> {

    /**
     * 向队列尾插入值
     * @param value 待插入值
     * @return 插入成功返回 true, 插入失败返回 false
     */
    boolean offer(E value);

    /**
     * 从对列头获取值, 并移除
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    E poll();

    /**
     * 从对列头获取值, 不移除
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    E peek();

    /**
     * 检查队列是否为空
     * @return 空返回 true, 否则返回 false
     */
    boolean isEmpty();

    /**
     * 检查队列是否已满
     * @return 满返回 true, 否则返回 false
     */
    boolean isFull();
}

4.1、链表实现

使用单向环形带哨兵链表方式来实现队列

代码：

public class LinkedListQueue<E>
        implements Queue<E>, Iterable<E> {

    private static class Node<E> {
        E value;
        Node<E> next;

        public Node(E value, Node<E> next) {
            this.value = value;
            this.next = next;
        }
    }

    private Node<E> head = new Node<>(null, null);
    private Node<E> tail = head;
    private int size = 0;
    private int capacity = Integer.MAX_VALUE;

    {
        tail.next = head;
    }

    public LinkedListQueue() {
    }

    public LinkedListQueue(int capacity) {
        this.capacity = capacity;
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        Node<E> added = new Node<>(value, head);
        tail.next = added;
        tail = added;
        size++;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        Node<E> first = head.next;
        head.next = first.next;
        if (first == tail) {
            tail = head;
        }
        size--;
        return first.value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return head.next.value;
    }

    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    @Override
    public boolean isFull() {
        return size == capacity;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;
            @Override
            public boolean hasNext() {
                return p != head;
            }
            @Override
            public E next() {
                E value = p.value;
                p = p.next;
                return value;
            }
        };
    }
}

4.2、数组实现

环形数组实现好处：

  1. 对比普通数组，起点和终点更为自由，不用考虑数据移动；
  2. ”环“意味着不会存在【越界】问题；
  3. 数组性能更佳；
  4. 环形数组比较适合实现有界队列、RingBuffer等；

代码：

/* 下标含义：
 * cur 当前指针位置
 * step 前进步数
 * length 数组长度
 */
public class ArrayQueue<E> implements Queue<E>, Iterable<E>{

    private int head = 0;
    private int tail = 0;
    private final E[] array;
    private final int length;

    @SuppressWarnings("all")
    public ArrayQueue(int capacity) {
        length = capacity + 1;
        array = (E[]) new Object[length];
    }

    @Override
    public boolean offer(E value) {
        if (isFull()) {
            return false;
        }
        array[tail] = value;
        tail = (tail + 1) % length;
        return true;
    }

    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        E value = array[head];
        head = (head + 1) % length;
        return value;
    }

    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return array[head];
    }

    @Override
    public boolean isEmpty() {
        return tail == head;
    }

    @Override
    public boolean isFull() {
        return (tail + 1) % length == head;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p];
                p = (p + 1) % array.length;
                return value;
            }
        };
    }
}

五、刷题

1. 二叉树层序遍历

题目：给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

输入输出样例：

示例一：
输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例二：
输入：root = [1]
输出：[[1]]
示例三：
输入：root = [1]
输出：[[1]]

提示：

  • 树中节点数目在范围 [0, 2000] 内
  • -1000 <= Node.val <= 1000

解题代码：

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if(root == null) {
            return result;
        }
        LinkedListQueue<TreeNode> queue = new LinkedListQueue<>();
        queue.offer(root);
        int c1 = 1;		// 本层节点个数
        while (!queue.isEmpty()) {
            int c2 = 0; 	// 下层节点个数
            List<Integer> level = new ArrayList<>();
            for (int i = 0; i < c1; i++) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                    c2++;
                }
                if (node.right != null) {
                    queue.offer(node.right);
                    c2++;
                }
            }
            c1 = c2;
            result.add(level);
        }
        return result;
    }

    // 自定义队列
    static class LinkedListQueue<E> {

        private static class Node<E> {
            E value;
            Node<E> next;

            public Node(E value, Node<E> next) {
                this.value = value;
                this.next = next;
            }
        }

        private final Node<E> head = new Node<>(null, null);
        private Node<E> tail = head;
        int size = 0;
        private int capacity = Integer.MAX_VALUE;

        {
            tail.next = head;
        }

        public LinkedListQueue() {
        }

        public LinkedListQueue(int capacity) {
            this.capacity = capacity;
        }

        public boolean offer(E value) {
            if (isFull()) {
                return false;
            }
            Node<E> added = new Node<>(value, head);
            tail.next = added;
            tail = added;
            size++;
            return true;
        }

        public E poll() {
            if (isEmpty()) {
                return null;
            }
            Node<E> first = head.next;
            head.next = first.next;
            if (first == tail) {
                tail = head;
            }
            size--;
            return first.value;
        }

        public E peek() {
            if (isEmpty()) {
                return null;
            }
            return head.next.value;
        }

        public boolean isEmpty() {
            return head == tail;
        }

        public boolean isFull() {
            return size == capacity;
        }
    }
}

2. 设计循环队列

题目：设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。

你的实现应该支持如下操作：

  • MyCircularQueue(k): 构造器，设置队列长度为 k 。

  • Front: 从队首获取元素。如果队列为空，返回 -1 。

  • Rear: 获取队尾元素。如果队列为空，返回 -1 。

  • enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

  • deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

  • isEmpty(): 检查循环队列是否为空。

  • isFull(): 检查循环队列是否已满。

示例：

MyCircularQueue circularQueue = new MyCircularQueue(3); // 设置长度为 3
circularQueue.enQueue(1);  // 返回 true
circularQueue.enQueue(2);  // 返回 true
circularQueue.enQueue(3);  // 返回 true
circularQueue.enQueue(4);  // 返回 false，队列已满
circularQueue.Rear();  // 返回 3
circularQueue.isFull();  // 返回 true
circularQueue.deQueue();  // 返回 true
circularQueue.enQueue(4);  // 返回 true
circularQueue.Rear();  // 返回 4

提示：

  • 所有的值都在 0 至 1000 的范围内；

  • 操作数将在 1 至 1000 的范围内；

  • 请不要使用内置的队列库。

解题代码：

class MyCircularQueue {
    int k, he, ta;
    int[] nums;

    public MyCircularQueue(int _k) {
        k = _k;
        nums = new int[k];

    }
    
    public boolean enQueue(int value) {
        if (isFull()) return false;
        nums[ta % k] = value;
        return  ++ta >= 0;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        return ++he >= 0;
    }
    
    public int Front() {
        return isEmpty() ?-1 : nums[he % k];
    }
    
    public int Rear() {
        return isEmpty() ? - 1 : nums[(ta - 1) % k];

    }
    
    public boolean isEmpty() {
        return he == ta;
    }
    
    public boolean isFull() {
        return ta - he == k;
    }
}

最后

对各位小伙伴有帮助的话，希望可以点赞❤️+收藏⭐，谢谢各位大佬~~🙌🙌🙌

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/3418.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots

seaborn从入门到精通03-绘图功能实现02-分类绘图Categorical plots总结参考关系-分布-分类分类绘图-Visualizing categorical data图形级接口catplot--figure-level interface导入库与查看tips和diamonds 数据分类散点图参考分布散点图stripplot分布密度散点图-swarmplot&#…
阅读更多...
进程与线程

进程与线程

文章目录进程与线程进程什么是进程进程的组成程序段数据段程序控制块例子线程什么是线程线程的组成线程描述信息程序计数器栈内存例子进程与线程的区别进程与线程 进程 什么是进程 ​ 什么是进程呢&#xff1f;简单来说&#xff0c;进程是程序的一次启动执行。什么是 程序呢…
阅读更多...
【C#进阶】C# 集合类

【C#进阶】C# 集合类

序号系列文章16【C#进阶】C# 索引器17【C#进阶】C# 委托18【C#进阶】C# 事件文章目录前言1、集合类是什么2、动态数组&#xff08;ArrayList&#xff09;3、压缩数组&#xff08;BitArray&#xff09;4、哈希表&#xff08;Hashtable&#xff09;5、队列&#xff08;Queue&…
阅读更多...
【数据结构】链表OJ题

【数据结构】链表OJ题

目录面试题 02.04 分割链表剑指 Offer II 027 回文链表160 相交链表141 环形链表142 环形链表 II138 复制带随机指针的链表面试题 02.04 分割链表 定义lesshead和greaterhead链接小于和大于等于k的值分别设置哨兵位和尾节点指针最后将两表去除哨兵位再链接 struct ListNode* p…
阅读更多...
内存泄漏和内存溢出的区别

内存泄漏和内存溢出的区别

参考答案 内存溢出(out of memory)&#xff1a;指程序在申请内存时&#xff0c;没有足够的内存空间供其使用&#xff0c;出现 out of memory。内存泄露(memory leak)&#xff1a;指程序在申请内存后&#xff0c;无法释放已申请的内存空间&#xff0c;内存泄露堆积会导致内存被…
阅读更多...
论文解读：PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

论文解读：PP-LiteSeg: A Superior Real-Time Semantic Segmentation Model

发表时间&#xff1a;2022 论文地址&#xff1a;https://arxiv.org/abs/2204.02681 项目地址&#xff1a;https://github.com/PaddlePaddle/PaddleSeg PP-LiteSeg&#xff0c;一个新的轻量级实时语义分割任务模型&#xff0c;在分割精度和推理速度之间实现了一种最先进的权衡…
阅读更多...
JVM垃圾回收机制

JVM垃圾回收机制

文章目录JVM垃圾回收机制如何确定该对象是垃圾引用计数可达性分析如何释放对象常用策略JVM垃圾回收机制 以对象为单位来进行回收 如何确定该对象是垃圾 Java 中使用 可达性分析方法 Python 中时使用 引用计数方法 引用计数 使用额外的计数器&#xff0c;来记录某个对象有多少个…
阅读更多...
【致敬未来的攻城狮计划】连续打卡第4天+物联网操作系统概述

【致敬未来的攻城狮计划】连续打卡第4天+物联网操作系统概述

开启攻城狮的成长之旅&#xff01;这是我参与的由 CSDN博客专家 架构师李肯&#xff08;http://yyds.recan-li.cn&#xff09;和 瑞萨MCU &#xff08;https://www.renesas.cn/cn/zh&#xff09; 联合发起的「 致敬未来的攻城狮计划 」的第 4 天&#xff0c;点击查看活动计划详…
阅读更多...
【Vue3】用Element Plus实现列表界面

【Vue3】用Element Plus实现列表界面

&#x1f3c6;今日学习目标&#xff1a;用Element Plus实现列表界面 &#x1f603;创作者&#xff1a;颜颜yan_ ✨个人格言&#xff1a;生如芥子&#xff0c;心藏须弥 ⏰本期期数&#xff1a;第四期 &#x1f389;专栏系列&#xff1a;Vue3 文章目录前言效果图目录简介修改vite…
阅读更多...
基于springboot框架实现心理健康心灵治愈交流平台【源码+论文】展示

基于springboot框架实现心理健康心灵治愈交流平台【源码+论文】展示

基于springboot框架实现心灵心理健康 【源码论文】开发语言&#xff1a;Java 框架&#xff1a;springboot JDK版本&#xff1a;JDK1.8 服务器&#xff1a;tomcat7 数据库&#xff1a;mysql 5.7 数据库工具&#xff1a;Navicat11 开发软件&#xff1a;eclipse/myeclipse/idea Ma…
阅读更多...
CSS 7种居中效果实现原理与案例

CSS 7种居中效果实现原理与案例

目录 1.标准盒子居中 2.定位-绝对定位实现居中 3.表格方式实现垂直居中 4.弹性盒子&#xff1a;实现垂直居中 5.通过行高line-height实现垂直居中 6.变形定位实现居中 7.网格实现垂直居中 1.标准盒子居中 不需要设置display&#xff0c;只能实现水平居中 效果&#xff1…
阅读更多...
代码随想录算法训练营第五十二天| ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

代码随想录算法训练营第五十二天| ● 300.最长递增子序列 ● 674. 最长连续递增序列 ● 718. 最长重复子数组

300.最长递增子序列 看完题后的思路 dp[i] [0,i]子数组中,以nums[i]结尾的子序列的长度 dp[i]dp[j]1 j从i-1向0遍历,在所有nums[j]<nums[i]中dp[j]最大 初始化 dp[0]1 代码 class Solution {public int lengthOfLIS(int[] nums) {if (nums.length0){return 0;}int[] dpne…
阅读更多...
Gateway服务网关

Gateway服务网关

Spring Cloud Gateway为微服务架构提供一种简单有效的统一的 API 路由管理方式。Gateway网关是所有微服务的统一入口。网关的核心功能特性&#xff1a;请求路由和负载均衡&#xff1a;一切请求都必须先经过gateway&#xff0c;但网关不处理业务&#xff0c;而是根据某种规则&am…
阅读更多...
vue3自定义svg图标组件

vue3自定义svg图标组件

可参考&#xff1a; 未来必热&#xff1a;SVG Sprites技术介绍 懒人神器&#xff1a;svg-sprite-loader实现自己的Icon组件 在Vue3项目中使用svg-sprite-loader 前置知识 在页面中&#xff0c;虽然可以通过如下的方式使用img标签&#xff0c;来引入svg图标。但是&#xff0c;…
阅读更多...
架构的容错性设计

架构的容错性设计

面对程序故障&#xff0c;我们该做些什么 “容错性设计”&#xff08;Design for Failure&#xff09;是微服务的另一个核心原则&#xff0c;也是架构反复强调的开发观念的转变。 流量治理 流量治理所要解决的问题 1.某一个服务的崩溃&#xff0c;会导致所有用到这个服务的…
阅读更多...
Unity --- 三维数学 --- Vector类 --- 向量部分

Unity --- 三维数学 --- Vector类 --- 向量部分

1.注意每一个数字都表示一段有向位移 --- 有方向的距离 1.从尾到头那一段称为向量的模长 --- magnitude (direction对应的是向量的方向) 2.一个向量有大小 -- 模长(magnitude) &#xff0c; 有方向&#xff08;direction&#xff09; 1.向量的模长等于各分量的平方和的平方根…
阅读更多...
IO流你了解多少

IO流你了解多少

IO流你了解多少 &#x1f3e0;个人主页&#xff1a;shark-Gao &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是shark-Gao&#xff0c;一个想要与大家共同进步的男人&#x1f609;&#x1f609; &#x1f389;目前状况&#xff1a;23届毕业生&#xff0c;目前在某公…
阅读更多...
国产化大趋势下学习linux的必要性

国产化大趋势下学习linux的必要性

由于国际上的一些国家的制裁和威胁。最近几年国产化大趋势慢慢的兴起&#xff0c;我们国产化硬件的需求越来越大。对国产操作系统的需求也越来越多&#xff0c;那么我们一直用的Windows系统为什么不用了呢&#xff1f;众所周知的原因&#xff0c;不管是最新的Windows11还是正值…
阅读更多...
【Python入门第三十六天】Python丨文件写入

【Python入门第三十六天】Python丨文件写入

写入已有文件 如需写入已有的文件&#xff0c;必须向 open() 函数添加参数。 “a” - 追加 - 会追加到文件的末尾“w” - 写入 - 会覆盖任何已有的内容 实例 打开文件 “demofile2.txt” 并将内容追加到文件中&#xff1a; f open("demofile2.txt", "a&qu…
阅读更多...
主动学习相关论文、代码

主动学习相关论文、代码

文章目录Object Detection2019Learning Loss for Active LearningAn Adaptive Supervision Framework for Active Learning in Object Detection2021Active Learning for Deep Object Detection via Probabilistic ModelingMultiple Instance Active Learning for Object Detec…
阅读更多...
最新文章

Copyright @ 2022~2023