Java栈和队列·下

news/2024/5/15 3:07:35/文章来源:https://blog.csdn.net/xinhang10/article/details/129642119

Java栈和队列·下

  • 2. 队列(Queue)
    • 2.1 概念
    • 2.2 实现
    • 2.3 相似方法的区别
    • 2.4 循环队列
  • 3. 双端队列 (Deque)
    • 3.1 概念
  • 4.java中的栈和队列
  • 5. 栈和队列面试题

大家好,我是晓星航。今天为大家带来的是 Java栈和队列·下 的讲解!😀

继上一个讲完的栈后,我们这次开始讲解队列!

2. 队列(Queue)

2.1 概念

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

在idea中看Queue(队列的底层逻辑代码)时 按下 alt + 7 可以查看它包含的所有方法:

2.2 实现

队列也可以数组和链表的结构实现,使用链表的结构实现更优一些,因为如果使用数组的结构,出队列在数组头上出数据,效率会比较低。


class Node {public int val;public Node next;public Node(int val) {this.val = val;}}
public class MyQueue {public Node head;public Node last;/*** 尾插法* @param val*/public void offer(int val) {Node node = new Node(val);if (head == null) {head = node;last = node;} else {last.next = node;last = last.next;}}public int poll() {if (isEmpty()) {throw new RuntimeException("队列为空");}int oldVal = head.val;head = head.next;return oldVal;}public boolean isEmpty() {return this.head == null;}public int peek() {if (isEmpty()) {throw new RuntimeException("队列为空");}return head.val;}}

下面为测试代码:

public class TestDemo {public static void main(String[] args) {MyQueue queue = new MyQueue();queue.offer(1);queue.offer(2);queue.offer(3);System.out.println(queue.peek());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());System.out.println(queue.poll());}

Queue中方法总结:
add 增加一个元索 如果队列已满,则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空,则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满,则返回false
poll 移除并返问队列头部的元素 如果队列为空,则返回null
peek 返回队列头部的元素 如果队列为空,则返回null
put 添加一个元素 如果队列满,则阻塞
take 移除并返回队列头部的元素

2.3 相似方法的区别

1、add()和offer()区别:

add()和offer()都是向队列中添加一个元素。一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,调用 add() 方法就会抛出一个 unchecked 异常,而调用 offer() 方法会返回 false。因此就可以在程序中进行有效的判断

2、poll()和remove()区别:

remove() 和 poll() 方法都是从队列中删除第一个元素。如果队列元素为空,调用remove() 的行为与 Collection 接口的版本相似会抛出异常,是新的 **poll() 方法在用空集合调用时只是返回 null。**因此新的方法更适合容易出现异常条件的情况。

3、element() 和 peek() 区别:

element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null。

2.4 循环队列

实际中我们有时还会使用一种队列叫循环队列。如操作系统课程讲解生产者消费者模型时可以就会使用循环队列。环形队列通常使用数组实现。

数组下标循环的小技巧

    1. 下标最后再往后(offset 小于 array.length): index = (index + offset) % array.length
  1. 下标最前再往前(offset 小于 array.length): index = (index + array.length - offset) % array.length

如何区分空与满

  1. 通过添加 size 属性记录 使用size和数组长度比较,确定满或者空
  1. 使用标志位flag,最开始falg = false,

    入队列时,每放一个元素,falg就置为true

    出队列时,每出一个元素,falg就置为false

    当front和rear相遇时,falg为true则队列为满,falg为false则队列为空。

  1. 浪费一个格子来区分空和满,每次存放元素之前,都先检查一下rear的下一个是不是front。如果是,那么就是满的

空:frontNext == rear

满:rearNext == front

3. 双端队列 (Deque)

3.1 概念

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

双端队列的所有方法:

4.java中的栈和队列

栈的方法:

普通队列方法:

双端队列方法:

5. 栈和队列面试题

  1. 括号匹配问题。OJ链接
import java.util.Stack;
class Solution {public boolean isValid(String s) {Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char ch = s.charAt(i);if (ch == '(' || ch == '[' || ch == '{' ) {//如果是左括号直接入栈stack.push(ch);} else {//如果是右括号if (stack.empty()) {//右括号多System.out.println("右括号多!");return false;}char top = stack.peek();if (top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}') {//如果左括号和右括号匹配 则弹出这个左括号stack.pop();} else {//左右括号不匹配System.out.println("左右括号不匹配");return false;}}}if (!stack.empty()) {//左括号多System.out.println("左括号多!");return false;}return true;}
}

题目描述的很清楚,左右括号如果不匹配,无非是以下几种情况:

1、左括号多余右括号

2、右括号多余左括号

3、左右括号顺序不想匹配

在使用代码将这几种情况考虑完全后,便可轻易通过测试。

思路如下:

如果是左括号我们直接使其进栈,如果是右括号我们先判断右括号是否比左括号多,再看其是否相匹配,匹配则弹出相对应的左括号继续下一个括号的判断,如果不匹配则返回不匹配错误,在右括号全部判断完毕后,我们判断一下栈此时是否为空,如果为空则我们所有的括号都匹配成功即正确,如果不为空则是左括号比右括号要多,我们就返回false。

  1. 用队列实现栈。OJ链接
public class MyStack {private Queue<Integer> qu1;private Queue<Integer> qu2;public MyStack() {qu1 = new LinkedList<>();qu2 = new LinkedList<>();}public void push(int x) {if (!qu1.isEmpty()) {qu1.offer(x);} else if (!qu2.isEmpty()){qu2.offer(x);} else {qu1.offer(x);}}public int pop() {if (empty()) {return -1;}if (!qu1.isEmpty()) {int size = qu1.size();for (int i = 0; i < size - 1; i++) {int val = qu1.poll();qu2.offer(val);}return qu1.poll();}if (!qu2.isEmpty()) {int size = qu2.size();for (int i = 0; i < size - 1; i++) {int val = qu2.poll();qu1.offer(val);}return qu2.poll();}return -1;}public int top() {if (empty()) {return -1;}if (!qu1.isEmpty()) {int val = -1;int size = qu1.size();for (int i = 0; i < size; i++) {val = qu1.poll();qu2.offer(val);}return val;}if (!qu2.isEmpty()) {int val = -1;int size = qu2.size();for (int i = 0; i < size; i++) {val = qu2.poll();qu1.offer(val);}return val;}return -1;}public boolean empty() {return qu1.isEmpty() && qu2.isEmpty();}
}

1、入栈的时候,入到不为空的队列,刚开始都为空指定入到一个队列。

2、出栈的时候,找到不为空的队列,出size-1个元素到另一个队列,剩下这个元素就是出栈的元素。

注意:这里有一个小问题我们很容易疏忽,就是在使用top和pop方法进行移动时我们qu1和qu2中的元素个数时变化的,因此我们的qu1.size() qu2.size()也会跟着变化,为了避免这个情况,我们在for循环的外面自己定义一个Int size = qu1.size(); int size = qu2.size();在之后的for循环中我们只需要让i小于size即可,此时的size就不是一个会变动的值了。

  1. 用栈实现队列。OJ链接
class MyQueue {public Stack<Integer> stack1;public Stack<Integer> stack2;public MyQueue() {stack1 = new Stack<>();stack2 = new Stack<>();}public void push(int x) {stack1.push(x);}public int pop() {if (empty()) {return -1;}if (stack2.empty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.pop();}public int peek() {if (empty()) {return -1;}if (stack2.empty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());}}return stack2.peek();}public boolean empty() {return stack1.isEmpty() && stack2.isEmpty();}
}

思路:1、入队的时候,统一入到第1个栈

2、出队的时候,同一出第2个栈里面的元素,如果第2个为空,那么把第一个栈里面所有的元素,全部倒过来,然后再出栈顶的元素。

  1. 实现一个最小栈。OJ链接
class MinStack {private Stack<Integer> stack;private Stack<Integer> minStack;public MinStack() {stack = new Stack<>();minStack = new Stack<>();}public void push(int val) {stack.push(val);if (!minStack.empty()) {int top = minStack.peek();//比较 小于等于的话 也要放进来if (val <= top) {minStack.push(val);}} else {minStack.push(val);}}public void pop() {int popVal = stack.pop();if (!minStack.empty()) {int top = minStack.peek();if (top == popVal) {minStack.pop();}}}public int top() {return stack.peek();}public int getMin() {return minStack.peek();}
}

思路:这里我们采取了使用两个栈(一个普通栈 一个最小栈)来比较的方法,例如我们在push元素时,普通栈我们是直接放进去的,而最小栈我们则是通过比较,如果要放的元素比我们最小栈栈顶的元素小或等于我们便在最小栈也放入一份。

在pop弹出栈顶元素时我们同样是直接弹出普通栈的栈顶元素,然后比较这个弹出的元素和最小栈栈顶元素的大小是否相等,如果相等我们则还需要再pop一次最小栈的栈顶元素。

top方法和我们stack栈中的peek方法一样,我们直接返回stack的peek方法即可。

getMin方法是返回栈中最小元素,我们这里有两个栈,而最小栈的原理就是将最小的元素通过压栈(头插)的方式进入最小栈,因此我们最小栈的最小值永远是栈顶的元素,我们直接返回最小栈的栈顶元素即可。

  1. 设计循环队列。OJ链接
class MyCircularQueue {public int[] elem;public int front;//队头下标public int rear;//队尾下标public MyCircularQueue(int k) {this.elem = new int[k + 1];}/*** 入队操作* @param value* @return*/public boolean enQueue(int value) {if (isFull()) {return false;}this.elem[rear] = value;//rear++;rear = (rear + 1) % elem.length;return true;}/*** 出队操作* @return*/public boolean deQueue() {if (isEmpty()) {return false;}front = (front + 1) % elem.length;return true;}/*** 得到队头元素* @return*/public int Front() {if (isEmpty()) {return -1;}return elem[front];}public int Rear() {if (isEmpty()) {return -1;}int index = -1;if (rear == 0) {index = elem.length - 1;} else {index = rear - 1;}return elem[index];}public boolean isEmpty() {return front == rear;}public boolean isFull() {//rear的下一个是frontif ((this.rear + 1) % elem.length == front) {return true;}return false;}
}

解答思路:我们这里的数组元素为k个,但是所能用的位置只有k-1个,为了满足题目要求我们将数组大小改为了k+1,故我们所能用的元素变为了k个。这里因为我们是循环队列,因此当数组为空时,或者数组占满时我们的front和rear是相等的,为了避免数组占满,而要计算rear要循环回我们的首元素地址0时,我们采取了rear = (rear + 1) % elem.length的操作,如果rear的下标已经时数组下标的最大值,再加1就会自动归为首元素的下标0。

感谢各位读者的阅读,本文章有任何错误都可以在评论区发表你们的意见,我会对文章进行改正的。如果本文章对你有帮助请动一动你们敏捷的小手点一点赞,你的每一次鼓励都是作者创作的动力哦!😘

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

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

相关文章

视听场景理解经典任务

文章目录1. 视听场景理解简介2. 主要任务2.1 Audio-visual Event Localization (AVE) 2.2 Audio-visual Video Parsing &#xff08;AVVP&#xff09;2.3 Audio-visual Question Answering &#xff08;AVQA&#xff09;2.4 Audio-visual Segmentation &#xff08;AVS&#xf…

STM32中systick中断的优先级

1、systick中断的优先级 systick为内核外设中断&#xff0c;与普通外设中断的优先级有些区别&#xff0c;并没有抢占优先级和子优先级的说法。 对于M3来说内核外设的中断优先级由内核SCB这个外设的寄存器&#xff1a;SHPRx&#xff08;x1.2.3&#xff09;来配置。 内核外设的中…

佳明安夺(Garmin Enduro)续航简单测试

文章目录&#xff08;一&#xff09;结论&#xff08;二&#xff09;测试条件&#xff08;2.1&#xff09;Garmin Connect APP 日历&#xff08;2.2&#xff09;具体运动记录&#xff08;2.3&#xff09;步数情况&#xff08;三&#xff09;补充和探讨&#xff08;3.1&#xff…

信捷PLC通过EtherCat与松下伺服通讯时的断电重启时会产生巨大异响的Bug原因及解决办法

信捷PLC支持ethercat通讯协议,可以和支持ethercat的从站通讯,像伺服驱动器或IO站点等。 其中,信捷XLH系列PLC在与松下伺服驱动器通讯时,有一个比较严重的问题,就是PLC断电再上电时,有时候会出现bug,这个bug的现象是,使用PLC的指令方式去控制伺服轴动作时,会产生巨大的…

kali内置超好用的代理工具proxychains

作者&#xff1a;Eason_LYC 悲观者预言失败&#xff0c;十言九中。 乐观者创造奇迹&#xff0c;一次即可。 一个人的价值&#xff0c;在于他所拥有的。所以可以不学无术&#xff0c;但不能一无所有&#xff01; 技术领域&#xff1a;WEB安全、网络攻防 关注WEB安全、网络攻防。…

Mybatis的课程总结

1.mybatis Mybatis主要是对代码进行少写&#xff0c;分别加入核心配置文件和mapper映射文件&#xff0c; 核心配置文件主要是为了连接数据库&#xff0c;mapper映射文件是为了编写sql语句 1.如何配置mybatis ①先创建一个moudle ②然后配置jar包 ③然后进行mybatis的分层 bean…

pcb成型板aoi检测,6种PCB板常用的检测方法

6种PCB板常用的检测方法&#xff0c;主要包括&#xff1a;PCB板人工目测、PCB板在线测试、PCB板功能测试、自动光学检测、自动X光检查、激光检测系统1、PCB板人工目测使用放大镜或校准的显微镜&#xff0c;利用操作人员视觉检查来确定电路板合不合格&#xff0c;并确定什么时候…

我们再次看看 ARB 女巫空投策略,做到知彼知己,不敢说百战不殆

女巫检测选项该项目旨在从 Arbitrum 空投中删除 Sybil 地址&#xff0c;确保只有合法用户才能收到空投代币。方法我们使用链上数据来识别同一用户拥有的相关地址&#xff0c;并使用来自 Nansen、Hop 和 OffChain Labs 的数据删除实体地址&#xff0c;例如网桥、交易所和智能合约…

Verilog学习之触发器与modelsim仿真

目录 一、前言 二、触发器介绍 三、测试文件代码 一、前言 ​ ​本文将学习常见类型触发的verilog编写&#xff0c;结合仿真结果来熟悉。 二、触发器介绍 ​ ​触发器在verilog中的作用主要是具有存储作用&#xff0c;由时钟信号来触发改变存储内容&#xff0c;较常见…

银河麒麟v10系统硬盘挂载

一、查看磁盘 近期由于centos系统停止更新用户服务器要更换银河麒麟v10&#xff0c;拿到服务器后使用lsblk -f或fdisk -l命令查看磁盘名称 可以看到sdb200G就是要挂载的硬盘&#xff0c;还没有uuid需要初始化才可以挂载。 二、分区 分区命令&#xff1a; fdisk /dev/【你的…

【LeetCode每日一题】——面试题17.21.直方图的水量

文章目录一【题目类别】二【题目难度】三【题目编号】四【题目描述】五【题目示例】六【解题思路】七【时间频度】八【代码实现】九【提交结果】一【题目类别】 双指针 二【题目难度】 困难 三【题目编号】 面试题17.21.直方图的水量 四【题目描述】 给定一个直方图(也称…

Java解题--练习解题阶段(无序阶段)-ALGO-1006 拿金币

题目算法训练 拿金币资源限制内存限制&#xff1a;256.0MB C/C时间限制&#xff1a;1.0s Java时间限制&#xff1a;3.0s Python时间限制&#xff1a;5.0s问题描述有一个N x N的方格,每一个格子都有一些金币,只要站在格子里就能拿到里面的金币。你站在最左上角的格子里,每次可以…

什么是装箱?什么是拆箱?装箱和拆箱的执行过程?常见问题?

参考答案 1、什么是装箱&#xff1f;什么是拆箱&#xff1f; 装箱&#xff1a;基本类型转变为包装器类型的过程。 拆箱&#xff1a;包装器类型转变为基本类型的过程。 //JDK1.5之前是不支持自动装箱和自动拆箱的&#xff0c;定义Integer对象&#xff0c;必须 Integer i new…

MATLAB | R2023a更新了哪些好玩的东西

R2023a来啦&#xff01;&#xff01;废话不多说看看新版本有啥有趣的玩意和好玩的特性叭&#xff01;&#xff01;把绘图放最前面叭&#xff0c;有图的内容看的人多。。 1 区域填充 可以使用xregion及yregion进行区域填充啦&#xff01;&#xff01; x -10:0.25:10; y x.^…

<Linux>环境变量

环境变量 文章目录环境变量一、基本概念二、常见环境变量三、查看环境变量的方法四、测试PATH五、测试HOME六、测试SHELL七、环境变量相关的命令八、环境变量的组织方式九、命令行参数十、通过代码获得环境变量十一、通过系统调用获取环境变量十二、环境变量通常是具有全局属性…

Docker简单上手

Docker 笔记 文章目录Docker 笔记[toc]一、Docker简介docker版本docker 架构二、Docker常用命令docker镜像命令docker容器命令提交docker镜像到阿里云仓库搭建私有docker镜像库三、容器数据卷四、阿里云容器部署1.Tomcat部署2.MySQL部署3.Redis部署一、Docker简介 ​ Docker是…

Linux- 系统随你玩之--玩出花活的命令浏览器-双生姐妹花

文章目录1、背景2、命令浏览器-双生姐妹花2.1、姐妹花简介2.2 、验名正身2.3、常用功能选项3、常用实操3.1、发送请求获取文件3.1.1、抓取页面内容到一个文件中3.1.2、多个文件下载3.1.3、下载ftp文件3.1.4、断点续传3.1.5、上传文件3.1.6、内容输出3.2 、利用curl测试接口3.3 …

Oracle导出AWR报告

一、使用root用户登录Linux服务器 二、切换至oracle用户 执行命令&#xff1a;su – oracle&#xff0c;然后回车 三、使用管理员权限连接数据库 执行命令&#xff1a;sqlplus / as sysdba&#xff0c;然后回车 四、生成报告快照 执行脚本&#xff1a;exec DBMS_WORKLOAD_RE…

达梦数据库(dm8)管理工具不会自动提交执行sql的几种方式

大多数数据库管理工具&#xff0c;默认情况下&#xff0c;是开启了自动事务提交的&#xff0c;即执行了一句 Select 、Insert 、 Delete 、Update 之后会自动执行 commit 操作&#xff0c; 但达梦数据库管理工具不会&#xff0c;无论是命令行工具disql&#xff0c;还是可视化管…

Java Web 实战 15 - 计算机网络之网络编程套接字

文章目录一 . 网络编程中的基本概念1.1 网络编程1.2 客户端(client) / 服务器(server)1.3 请求(request) / 响应(response)1.4 客户端和服务器之间的交互数据1.4.1 一问一答1.4.2 多问一答1.4.3 一问多答1.4.4 多问多答二 . socket 套接字2.1 UDP 的 Socket API2.1.1 引子2.1.2…