Collection与数据结构 Stack与Queue(二):队列与Queue

1. 队列

1.1 概念

只允许在一端进行插入数据操作,在另一端进行删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out) 入队列:进行插入操作的一端称为队尾(Tail/Rear) 出队列:进行删除操作的一端称为队头(Head/Front).
在这里插入图片描述
这样的数据结构有些像我们平时在食堂排队打饭的操作.

1.2 队列的使用

在Java中,Queue是一个接口,底层是通过链表来实现的.所以在实例化的时候,必须用LinkedList来实例化.
在这里插入图片描述

方法功能
boolean offer(E e)入队列
E poll()出队列
peek()获取队头元素
int size()获取队列中有效元素个数
boolean isEmpty()检测队列是否为空
  • offer和poll操作的时间复杂度都是O(1),所以在使用单向链表实现队列的时候,必须使用头插尾插.如果说是尾删头插的话,删掉的时候不知道该结点的pre是谁(因为是单向链表),所以要重新遍历寻找最后一个结点,时间复杂度就不是O(1).
public static void main(String[] args) {Queue<Integer> q = new LinkedList<>();q.offer(1);q.offer(2);q.offer(3);q.offer(4);q.offer(5);                  // 从队尾入队列System.out.println(q.size());System.out.println(q.peek());  // 获取队头元素q.poll();System.out.println(q.poll());  // 从队头出队列,并将删除的元素返回if(q.isEmpty()){System.out.println("队列空");}else{System.out.println(q.size());}
}

1.3 队列的模拟实现

我们根据队列底层的逻辑:使用LinkedList来实现队列.

public class MyQueue {public static class ListNode{ListNode next;ListNode pre;int val;public ListNode(int val) {this.val = val;}}ListNode first;ListNode last;int size = 0;/*** 入队列,在双向链表的尾部插入新结点* @param e*/public void offer (int e){ListNode listNode = new ListNode(e);if (first == null){first = listNode;last = listNode;}else {listNode.pre = last;last.next = listNode;last = listNode;}size++;}/*** 出队列,在链表头部删除结点* @return*/public int poll(){int value = 0;if (first == null){return -1;} else if (first == last) {value = first.val;//需要先把value记录下来,以便最后返回first = null;last = null;//return value;//不可以直接返回first.val,否者空指针异常}else {value = first.val;first = first.next;first.pre.next = null;first.pre = null;//return value;}size --;//在返回之前size--return value;}/*** 返回队头元素* @return*/public int peek(){if (first == null){return -1;}return first.val;}/*** 获取队列大小* @return*/public int size(){return this.size;}/*** 判断队列是否为空* @return*/public boolean isEmpty(){return size == 0;}
}

1.4 环形队列

在实际中,我们经常用的一种队列还有一种,叫做循环队列,环形队列通常由数组实现.
在这里插入图片描述
既然是环形队列,所以我们在存放元素的时候,就要按循环下标的方式来添加元素,数组下标循环公式:
(当前位置+偏移量)%数组大小.
eg:在这里插入图片描述
区分空与满的问题:
在一个队列中,一定会有队头和队尾,在队列空的时候,队列头和尾指向同一位置:
在这里插入图片描述
在队列满的时候,头和尾也会指向同一位置:
在这里插入图片描述
如果按上述的方法,我们就没有办法区别队列是空还是满了,那么我们提供以下解决方案:

  • 通过添加size属性
  • 保留一个位置(牺牲空间法)
  • 使用标记

在下面,我们只以第二种方法为例:我们令头为front,尾为rear
在这里插入图片描述
在满的时候,我们通过把最后一个位置空出来,以front = (rear+1)%array.length来表示队列满.
下面我们来通过上述方式设计循环队列:

OJ链接

class MyCircularQueue {public int front;//队头public int rear;//队尾public int[] elem;public MyCircularQueue(int k) {front = 0;rear = 0;elem = new int[k+1];//使用牺牲空间法来区分满和空,初始化空间的时候就要多一个空间}public boolean enQueue(int value) {if(isFull()){return false;//队列为满,返回false}else{elem[rear] = value;rear = (rear+1)%elem.length;}return true;}public boolean deQueue() {if(front == rear){return false;//队列为空,删除失败}else{elem[front] = 0;front = (front+1)%elem.length;}return true;}public int Front() {if(rear == front){return -1;}else{return elem[front];}}public int Rear() {if(rear == front){return -1;}else{return rear == 0? elem[elem.length-1]:elem[rear-1];}//分两种情况,一种是rear为0,一种是不为0的时候,为0返回数组的最后一个元素,否者返回rear指向的前一个元素}//队尾放的最后一个元素总是比rear指针向前一个位置,因为在插入操作的时候,最后进行了rear = (rear+1)%elem.length操作public boolean isEmpty() {if(rear == front){return true;//头和尾重合的时候,就是空}else{return false;}}public boolean isFull() {if(front == (rear+1)%elem.length){return true;//中间空出一个空间的时候,就是满}return false;}}
}

2. 双端队列

双端队列(deque)是指允许两端都可以进行入队和出队操作的队列,deque 是 “double ended queue” 的简称。那就说明元素可以从队头出队和入队,也可以从队尾出队和入队
在这里插入图片描述
Deque是一个接口,必须使用LinkedList实例化对象.
在这里插入图片描述

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

3. 队列与栈的综合

3.1 用栈实现队列

在用栈实现队列的时候,核心思想把握住一句话:出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素.
在这里插入图片描述

OJ链接

class MyQueue2 {//需要用两个栈来实现一个队列Stack<Integer> stack1;Stack<Integer> stack2;public MyQueue2() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);//入队列的时候就入第一个栈就可以}public int pop() {int value = 0;if (stack2.empty()){//如果stack2为空的时候,就把stack1的元素全部倒到2中//是因为出队列的顺序和出栈的顺序相反,对头的元素对应栈底的元素while(!stack1.empty()){stack2.push(stack1.pop());}value = stack2.peek();stack2.pop();//出2的栈顶元素}else {//如果不为空,直接出栈顶元素value = stack2.peek();stack2.pop();}return value;}public int peek() {int value = 0;if (stack2.empty()){while(!stack1.empty()){stack2.push(stack1.pop());}value = stack2.peek();}else {value = stack2.peek();}return value;//和pop原理一样,只不过没有元素出栈}public boolean empty() {//两个栈都为空的时候,队列为空if (stack1.empty() && stack2.empty()){return true;}else {return false;}}}

3.2 用队列实现栈

这道题的核心是:队列中最后一个元素对应栈顶的元素,所以要让队尾的元素露出来.
在这里插入图片描述
OJ链接

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;//使用两个队列来完成栈的实现public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}public void push(int x) {if (empty()){//空就往任意一个队列中添加queue1.offer(x);return;//记得返回}if (!queue1.isEmpty()){//谁不为空,就往谁添加queue1.offer(x);}else {queue2.offer(x);}}public int pop() {if (empty()){return -1;}if (queue1.isEmpty()){while(queue2.size() != 1){//poll到队列中只有1个元素,目的是让队列中的元素与栈顶元素对应起来queue1.offer(queue2.poll());}return queue2.poll();//弹出只剩一个元素的队列}else {while(queue1.size() != 1){queue2.offer(queue1.poll());}return queue1.poll();}}public int top() {if (empty()){return -1;}int value = 0;//利用vlaue保存peek的值if (queue1.isEmpty()){while(queue2.size() != 1){queue1.offer(queue2.poll());}value = queue2.peek();queue1.offer(queue2.poll());//先peek保存,再poll到另一个队列中return value;}else {while(queue1.size() != 1){queue2.offer(queue1.poll());}value = queue1.peek();queue2.offer(queue1.poll());return value;}}public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

免费https详细教程

简单叙述一下https的定义和实现https的一些基本作用&#xff0c;然后会给到申请SSL证书的方式以及安装部署流程&#xff0c;最终实现网站的https访问。 随着互联网的快速发展&#xff0c;网络安全问题日益凸显。在互联网上传输敏感信息、进行在线交易和共享个人数据时&#xf…

09 Php学习:数组和排序

数组概念 在PHP中&#xff0c;数组是一种复合数据类型&#xff0c;用于存储多个值。以下是关于PHP数组的详细解释&#xff1a; 索引数组&#xff1a;索引数组是最基本的数组类型&#xff0c;其中每个元素都有一个唯一的数字索引&#xff0c;从0开始递增。 关联数组&#xff…

Qt for MCUs 2.7正式发布

本文翻译自&#xff1a;Qt for MCUs 2.7 released 原文作者&#xff1a;Qt Group高级产品经理Yoann Lopes 翻译&#xff1a;Macsen Wang Qt for MCUs的新版本已发布&#xff0c;为Qt Quick Ultralite引擎带来了新功能&#xff0c;增加了更多MCU平台的支持&#xff0c;并且我们…

概率论基础——拉格朗日乘数法

概率论基础——拉格朗日乘数法 概率论是机器学习和优化领域的重要基础之一&#xff0c;而拉格朗日乘数法与KKT条件是解决优化问题中约束条件的重要工具。本文将简单介绍拉格朗日乘数法的基本概念、应用以及如何用Python实现算法。 1. 基本概念 拉格朗日乘数法是一种用来求解…

Golang 开发实战day08 - Multiple Return values

&#x1f3c6;个人专栏 &#x1f93a; leetcode &#x1f9d7; Leetcode Prime &#x1f3c7; Golang20天教程 &#x1f6b4;‍♂️ Java问题收集园地 &#x1f334; 成长感悟 欢迎大家观看&#xff0c;不执着于追求顶峰&#xff0c;只享受探索过程 Golang 教程08 - Multiple R…

第⑬讲:OSD硬盘故障处理实战:从诊断到恢复的全流程指南

文章目录 1.OSD坏盘更换操作2.判断OSD是否出现故障的思路3.模拟osd.5故障4.OSD故障更换硬盘流程4.1.将故障的osd.5从集群中删除4.1.1.从OSD Map中将故障的OSD删除4.1.2.从Crush Map中将故障的OSD删除4.1.3.在OSD列表中将故障的OSD删除4.1.4.将故障的OSD认证信息删除4.1.5.验证集…

羊大师带你了解春季喝羊奶有什么好处

在春季&#xff0c;随着大自然的苏醒&#xff0c;人们的生活方式也逐渐转向更加活跃和健康的模式。在众多健康习惯中&#xff0c;饮用羊奶成为了一个流行的选择&#xff0c;因其独特的营养价值和健康益处受到了广泛关注。羊奶不仅富含高质量的蛋白质和必需氨基酸&#xff0c;还…

用html实现一个动态的文字框

<!DOCTYPE html> <html lang"en" > <head><meta charset"UTF-8"><title>一个动态的文字框动画</title><link rel"stylesheet" href"./style.css"></head> <body> <link rel…

计算机视觉 | 基于 ORB 特征检测器和描述符的全景图像拼接算法

Hi&#xff0c;大家好&#xff0c;我是半亩花海。本项目实现了基于 ORB 特征检测器和描述符的全景图像拼接算法&#xff0c;能够将两张部分重叠的图像拼接成一张无缝连接的全景图像。 文章目录 一、随机抽样一致算法二、功能实现三、代码解析四、效果展示五、完整代码 一、随机…

MySQL-创建和管理表:基础知识、创建和管理数据库、创建表、修改表、重命名表、删除表、清空表、拓展

创建和管理表 1. 基础知识1.1 一条数据存储的过程1.2 标识符命名规则1.3 MySQL中的数据类型 2. 创建和管理数据库2.1 创建数据库2.2 使用数据库2.3 修改数据库2.4 删除数据库 3. 创建表3.1 创建方式13.2 创建方式23.3 查看数据表结构 4. 修改表4.1 追加一个列4.2 修改一个列4.3…

卷积神经网络(CNN)的数学原理解析

文章目录 前言 1、介绍 2、数字图像的数据结构 3、卷积 4、Valid 和 Same 卷积 5、步幅卷积 6、过渡到三维 7、卷积层 8、连接剪枝和参数共享 9、卷积反向传播 10、池化层 11、池化层反向传播 前言 本篇主要分享卷积神经网络&#xff08;CNN&#xff09;的数学原理解析&#xf…

解决 OpenERP v7 中的报告问题

在 OpenERP v7 中&#xff0c;报告问题可能涉及多个方面&#xff0c;包括报告模板的设计、数据源的配置、报告生成的逻辑等。然后再我们日常使用中还是会遇到各种各样的问题&#xff0c;那么如果出现下面的错误&#xff0c;可以尝试用我的解决方案。 1、问题背景 在使用 OpenE…

微服务-2 Eureka

Eureka 启动页面&#xff1a; 同理再注册完order-service后&#xff0c;刷新启动页面&#xff1a; userservice 启动多台服务&#xff1a; [ 代码 ]&#xff1a;orderService.java&#xff08;用 RestTemplate 调其他服务&#xff0c;用 userservice 代替 localhost:8081&…

LiveGBS流媒体平台GB/T28181常见问题-系统服务日志如何配置日志个数日志路径日志时长web操作日志操如何配置保留天数及过滤

LiveGBS系统服务日志如何配置日志个数日志路径日志时长web操作日志操如何配置保留天数及过滤 1、系统服务日志1.1、日志目录1.2、配置日志文件个数及记录时间1.3、配置日志文件路径 2、Web 操作日志2.1、配置保留天数2.2、配置不记录操作日志2.1.1、不记录所有2.1.2、不记录指定…

基于SSM+Jsp+Mysql的弹幕视频网站

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

Mybatis分页查询用PageHelper插件

首先看接口文档需求 看响应数据样例&#xff0c;那么咱们先自定义一个bean来满足这个需求&#xff0c;这里定义PageBean实体类 package com.itheima.pojo;import lombok.AllArgsConstructor; import lombok.Data; import lombok.NoArgsConstructor;import java.util.List;//分…

JRT高效率开发

得益于前期的基础投入&#xff0c;借助代码生成的加持&#xff0c;本来计划用一周实现质控物维护界面&#xff0c;实际用来四小时左右完成质控物维护主体&#xff0c;效率大大超过预期。 JRT从设计之初就是为了证明Spring打包模式不适合软件服务模式&#xff0c;觉得Spring打包…

【论文精读】集合级指导攻击:提高视觉语言预训练模型的对抗性可迁移性

文章目录 一、前言&#xff08;一&#xff09;对抗攻击概念&#xff08;二&#xff09;对抗攻击分类&#xff08;三&#xff09;VLP模型&#xff1a;视觉语言预训练模型 二、文章概览&#xff08;一&#xff09;研究动机&#xff08;二&#xff09;主要工作 三、对抗可迁移性的…

探探各个微前端框架

本文作者为 360 奇舞团前端开发工程师 微前端架构是为了在解决单体应用在一个相对长的时间跨度下&#xff0c;由于参与的人员、团队的增多、变迁&#xff0c;从一个普通应用演变成一个巨石应用(Frontend Monolith)后&#xff0c;随之而来的应用不可维护的问题。这类问题在企业级…

第十一届能源与环境研究国际会议-可再生能源走向脱碳化(ICEER 2024)即将召开!

能源和环境是当今世界至关重要的研究和教育领域&#xff0c;持续的气候危机和对可持续发展战略的迫切需求&#xff0c;需要从能源科学到地球工程等广泛领域的变革性工程解决方案和创新。ICEER 2024为来自学术界&#xff0c;研究中心和全球工业界的工程师&#xff0c;研究人员和…