当前位置: 首页 > news >正文

关于队列的简单理解

1.队列(Queue) 

1.1 关于队列

        队列 :只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表, 队列具有先进先出 FIFO(First In First Out)的操作特性(队列是个接口);
        入队列:进行插入操作的一端称为队尾( Tail/Rear )
        出队列:进行删除操作的一端称为队头( Head/Front )

        下图通过图解来了解关于队列入队和出队的操作;

1.2队列与链表

        在Java中,Queue是个接口,底层是通过链表实现的 ,具体情况如下图所示;​​​
        

1.3 队列的基本使用方法

        下图是使用队列时具体的基本方法;

        注意:Queue是个接口,在实例化时该接口时,必须实例化LinkedList的对象,因为LinkedList实现了Queue接口。 

2.用链表实现队列

        我们本次使用的是双向链表;

2.1创建队列

public class MyLLQueue {//创建静态内部类,实例对象作为队列中的节点public static class Node {int value;Node next;Node prev;public Node(int value) {this.value = value;}}public Node front;//双向链表的头结点public Node rear;//双向链表的尾结点public int usedSize = 0;//记录队列中节点个数
}

2.2入队列

        思路:

        1、创建一个要添加的值为value的节点node。

        2.1判断当前队列是否为空?即链表头结点front是否为null,若为null,则该node既是front(队头)和也是rear(队尾)。

        2.2若队头不为null,则将该节点的引用给当前队列的队尾的next,至此队尾就是我们新添加的节点;

        4、队列里面的数据容量加一。

        代码如下:

public boolean offer(int vale) {Node node = new Node(vale);if (isEmpty()) {front = node;rear = node;} else {rear.next = node;node.prev = rear;}rear = node;usedSize++;return true;}

2.3 判断队列是否为空

private boolean isEmpty() {return usedSize == 0;}

 2.4出队列

        1、队列为空,则直接返回队列为空的自定义异常。

public class EmptyException extends RuntimeException{public EmptyException(String msg) {super(msg);}
}

        2、队列此时不为空。

        2.1 此时队列中只有一个元素;(即队头的next域里存放的是空指针null),出队操作之后队列就为空,故此让队头和队尾都指向空指针;

        2.2 此时队列中有多个元素:让队头的后域指向下一个节点,队头的前域指向空指针;

        3、队列里面的数据容量减一;

//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}//用ret记录返回的队头元素的数据int ret = front.value;if (front.next == null) {//当前链表只有一个节点front = null;rear = null;usedSize--;return ret;}front = front.next;front.prev = null;usedSize--;return ret;}

2.5获取队头元素 

        思路类似于2,4部分

//获取队头元素的值,不出队列int peek(){if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}return front.value;}

2.6 双向链表(linkedlist)实现队列的完整代码

public class MyLLQueue {//创建静态内部类,实例对象作为队列中的节点public static class Node {int value;Node next;Node prev;public Node(int value) {this.value = value;}}public Node front;//双向链表的头结点public Node rear;//双向链表的尾结点public int usedSize = 0;//记录队列中节点个数//为了体现队列的先进先出特点,规定从尾入,从头出(也可以头进尾出)//插入操作,原理为双链表的尾插法public boolean offer(int vale) {Node node = new Node(vale);if (isEmpty()) {front = node;rear = node;} else {rear.next = node;node.prev = rear;}rear = node;usedSize++;return true;}private boolean isEmpty() {return usedSize == 0;}//出队列---将双向链表第一个节点删除掉,并返回第一个删除节点的值public int poll() {// 1. 队列为空// 2. 队列中只有一个元素----链表中只有一个节点---直接删除// 3. 队列中有多个元素---链表中有多个节点----将第一个节点删除if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}//用ret记录返回的队头元素的数据int ret = front.value;if (front.next == null) {//当前链表只有一个节点front = null;rear = null;usedSize--;return ret;}front = front.next;front.prev = null;usedSize--;return ret;}//获取队头元素的值,不出队列int peek(){if (isEmpty()) {//队列为空,抛异常,提示不能对空队列进行出队操作throw new EmptyException("队列为空,操作错误!!");}return front.value;}//获取队列的长度public int size(){return usedSize;}public static void main(String[] args) {MyLLQueue myLLQueue = new MyLLQueue();System.out.println(myLLQueue.isEmpty());myLLQueue.offer(1);myLLQueue.offer(2);myLLQueue.offer(3);System.out.println(myLLQueue.size());System.out.println(myLLQueue.peek());System.out.println(myLLQueue.poll());System.out.println(myLLQueue.peek());System.out.println(myLLQueue.size());}
}

        测试结果如下:

           

3. 双端队列 (Deque)

        双端队列(deque):是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。 那就说明元素可以从队头出队和入队,也可以从队尾出队和入队。

        Deque是一个接口,与queue类似在使用时必须创建LinkedList的对象,以下是详细图解:

        在实际工程中,使用Deque接口是比较多的,栈和队列均可以使用该接口,代码如下:

Deque<Integer> stack = new ArrayDeque<>();//双端队列的线性实现
Deque<Integer> queue = new LinkedList<>();//双端队列的链式实现

ps:本次内容就到这里,如果喜欢的话就请一键三连哦!!!

相关文章:

关于队列的简单理解

1.队列(Queue) 1.1 关于队列 队列 &#xff1a;只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c; 队列具有先进先出 FIFO(First In First Out)的操作特性&#xff08;队列是个接口&#xff09;&#xff1b; 入队列&#x…...

加密市场进入牛初阶段?一场新的造富效应即将拉开帷幕!

周一(12月4日)&#xff0c;比特币一度上涨至42000美元&#xff0c;创下自2022年4月以来的最高水平。从目前比特币的走势来看&#xff0c;加密市场无疑已然进入到牛初阶段。 在牛市初期&#xff0c;确实存在人们不相信牛市到来的情况。由于在熊市中亏损的心理阻碍和对市场进一步…...

Superset基础入门

1 Superset概述 Apache Superset 是一个现代的数据探索和可视化平台。它功能强大且十分易用&#xff0c;可对接 各种数据源&#xff0c;包括很多现代的大数据分析引擎&#xff0c;拥有丰富的图表展示形式&#xff0c;并且支持自定义 仪表盘。 2 Superset安装 Superset 是由 P…...

【泛微ecology】将多个字段的数据合并到一个字段

doFieldSQL("select concat(concat(sqr,,),sy) as c from formtable_main_2 where requestid $requestid$ ")...

WebSocket入门介绍及编程实战

HTTP的限制 全双工和半双工&#xff1a; 全双工&#xff1a;全双工&#xff08;Full Duplex&#xff09;是允许数据在两个方向上同时传输。 半双工&#xff1a;半双工&#xff08;Half Duplex&#xff09;是允许数据在两个方向上传输&#xff0c;但是同一个时间段内只允许一个…...

vue3里面生命周期的使用

前言&#xff1a; vue2里面的生命周期和vue3生命周期是非常的相似的&#xff0c;我们通过访问生命周期钩子来处理不同场景之间的应用。 生命周期钩子的函数定义&#xff1a;每一个Vue组件实例在创建时都需要经历一系列的初始化步骤&#xff0c;比如数据侦听&#xff0c;编译模…...

在python的Scikit-learn库中,可以使用train_test_split函数来划分训练集和测试集。

文章目录 一、在Scikit-learn库中&#xff0c;可以使用train_test_split函数来划分训练集和测试集总结 一、在Scikit-learn库中&#xff0c;可以使用train_test_split函数来划分训练集和测试集 在Scikit-learn库中&#xff0c;可以使用train_test_split函数来划分训练集和测试…...

外包干了2个月,技术明显退步了...

先说一下自己的情况&#xff0c;大专生&#xff0c;19年通过校招进入广州某软件公司&#xff0c;干了接近5年的功能测试&#xff0c;今年11月份&#xff0c;感觉自己不能够在这样下去了&#xff0c;长时间呆在一个舒适的环境会让一个人堕落!而我已经在一个企业干了四年的功能测…...

数据结构:链表应用:第9关:删除链表中满足区间值的结点

任务描述编程要求 输入输出测试说明来源 任务描述 本关任务&#xff1a;利用单链表表示一个递增的整数序列&#xff0c;删除链表中值大于等于mink且小于等于maxk的所有元素&#xff08;mink和maxk是给定的两个参数&#xff0c;其值可以和表中的元素相同&#xff0c;也可以不同…...

了解 ignore_above 参数对 Elasticsearch 中磁盘使用的影响

在 Elasticsearch 中&#xff0c;ignore_above 参数允许你忽略&#xff08;而不是索引&#xff09;长于指定长度的字符串。 这对于限制字段的大小以避免性能问题很有用。 在本文中&#xff0c;我们将探讨 “ignore_above” 参数如何影响 Elasticsearch 中字段的大小&#xff0c…...

C#中的async/await异步编程模型

前言 当谈到异步编程时&#xff0c;C#中的async/await是一个强大且方便的工具。它使得编写并发和异步操作变得更加简单和可读&#xff0c;同时提供良好的可维护性。本文将详细解释async/await的使用&#xff0c;以及如何在C#中有效地利用它来实现异步操作。 目录 前言1. async…...

【原创】提升MybatisPlus分页便捷性,制作一个属于自己的分页插件,让代码更加优雅

前言 MybatisPlus的分页插件有一点非常不好&#xff0c;就是要传入一个IPage&#xff0c;别看这个IPage没什么大不了的&#xff0c;最多多写一两行代码&#xff0c;可这带来一个问题&#xff0c;即使用xml的查询没法直接取对象里面变量的值了&#xff0c;得Param指定xml中的变…...

pythonselenium自动化测试实战项目

说明&#xff1a;本项目采用流程控制思想&#xff0c;未引用unittest&pytest等单元测试框架 一.项目介绍 目的 测试某官方网站登录功能模块可以正常使用 用例 1.输入格式正确的用户名和正确的密码&#xff0c;验证是否登录成功&#xff1b; 2.输入格式正确的用户名和不…...

智能优化算法应用:基于瞬态优化算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于瞬态优化算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于瞬态优化算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.瞬态优化算法4.实验参数设定5.算法结果6.参考…...

springMVC 三大组件解析

springMVC组件概述 DispatcherServlet&#xff08;调度器Servlet&#xff09;&#xff1a; DispatcherServlet 是 Spring MVC 的前端控制器&#xff08;Front Controller&#xff09;。它负责接收来自客户端的请求&#xff0c;然后将请求分发给相应的处理器&#xff08;Control…...

聊聊nginx的keepalive_time参数

序 本文主要研究一下nginx的keepalive_time参数 keepalive_time Syntax: keepalive_time time; Default: keepalive_time 1h; Context: http, server, location This directive appeared in version 1.19.10.nginx的1.19.10版本新增了keepalive_time参数&#xff0c;用于限…...

沐风老师3DMAX键盘球建模方法详解

3DMAX键盘球建模教程 本教程给大家分享一个3dMax键盘球的建模方法过程。在学习本教程之前&#xff0c;大家需要对3dMax基本操作及建模知识有所掌握&#xff0c;还是那句话&#xff1a;做实例的前提是选学习基础知识和掌握3dMax的基本操作。 下面就给大家一步一步讲解演示3dMax…...

算法通关村第一关—白银挑战—链表高频面试算法题—查找两个链表的第一个公共子节点

文章目录 查找两个链表的第一个公共子节点&#xff08;1&#xff09;暴力求解法&#xff08;2&#xff09;使用哈希Hash⭐&#xff08;3&#xff09;使用集合⭐ - 与Hash类似&#xff08;4&#xff09;使用栈⭐&#xff08;5&#xff09;仍有更多方法&#xff0c;作者尚未理解&…...

C/C++ 发送与接收HTTP/S请求

HTTP&#xff08;Hypertext Transfer Protocol&#xff09;是一种用于传输超文本的协议。它是一种无状态的、应用层的协议&#xff0c;用于在计算机之间传输超文本文档&#xff0c;通常在 Web 浏览器和 Web 服务器之间进行数据通信。HTTP 是由互联网工程任务组&#xff08;IETF…...

【算法集训】基础数据结构:一、顺序表(下)

由于今天的题目是昨天剩下的&#xff0c;所以只有两道题&#xff0c;也非常简单&#xff0c;刷完下班~~~嘿嘿 第六题 2656. K 个元素的最大和 https://leetcode.cn/problems/maximum-sum-with-exactly-k-elements/description/ 很简单的思路&#xff0c;要得到得分最大的&…...

Chapter03-Authentication vulnerabilities

文章目录 1. 身份验证简介1.1 What is authentication1.2 difference between authentication and authorization1.3 身份验证机制失效的原因1.4 身份验证机制失效的影响 2. 基于登录功能的漏洞2.1 密码爆破2.2 用户名枚举2.3 有缺陷的暴力破解防护2.3.1 如果用户登录尝试失败次…...

在软件开发中正确使用MySQL日期时间类型的深度解析

在日常软件开发场景中&#xff0c;时间信息的存储是底层且核心的需求。从金融交易的精确记账时间、用户操作的行为日志&#xff0c;到供应链系统的物流节点时间戳&#xff0c;时间数据的准确性直接决定业务逻辑的可靠性。MySQL作为主流关系型数据库&#xff0c;其日期时间类型的…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

【项目实战】通过多模态+LangGraph实现PPT生成助手

PPT自动生成系统 基于LangGraph的PPT自动生成系统&#xff0c;可以将Markdown文档自动转换为PPT演示文稿。 功能特点 Markdown解析&#xff1a;自动解析Markdown文档结构PPT模板分析&#xff1a;分析PPT模板的布局和风格智能布局决策&#xff1a;匹配内容与合适的PPT布局自动…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...