java算法day9

  • 232.用栈实现队列
    1. 用队列实现栈
    1. 有效的括号
    1. 删除字符串中的所有相邻重复项
    1. 逆波兰表达式求值

解决栈和队列的基本数据结构

Queue(队列)

在java中是一个接口。定义的方法:

//boolean add(E e): 将指定的元素插入此队列(如果立即可行且不会违反容量限制),在成功时返回 true,如果当前没有可用的空间,则抛出 IllegalStateException。
//E remove():获取并移除 此队列的 头 。
//E element() :获取 ,但是不移除此队列的 头 。//boolean offer(E e):将指定的元素 插入 此队列(如果立即可行且不会违反容量限制),当使用有容量限制的队列时,此方法通常要优于 add(E),后者可能无法插入元素,而只是抛出一个异常。
//E poll():获取并移除 此队列的头,如果此队列为空,则返回 null。
//E peek(): 获取但不移除此队列的头;如果此队列为空,则返回 null。

在极端情况下,两组API的表现不一致。极端情况指的是 一组是抛异常,一组是返回特殊值

  • 插入的时候,队列满了
  • 删除或者获取的时候,队列空了。
    在这里插入图片描述

Deque

是个Queue的子接口,是java里面的双端队列。
Deque特点:

  1. Deque是Queue的子接口
  2. 数据结构表现:队列,栈,双端队列
  3. 存储元素有序
  4. 可存储重复元素
  5. 不能存储null(LinkedList除外)

Deque可以说非常的万能,能模拟很多数据结构,下面就是他能模拟的数据结构。

// ------------- 作为Queue的
//        E peek(): 获取队头元素,但不移除它
//        E poll():从队头移除元素
//        boolean offer(E e): 添加一个元素到 队尾// ------------- 作为Stack的
//        E pop(): 从此列表所表示的堆栈处弹出一个元素。
//        void push(E e): 将元素推入此列表所表示的堆栈。// ------------- 作为双端队列
//        boolean offerFirst(E e):  从 第一个位置 插入 指定元素
//        boolean offerLast(E e): 从 最后一个位置 插入 指定元素
//        E peekFirst(): 获取 但是不移除 第一个元素,如果列表为空,返回null
//        E peekLast(): 获取 但是不移除 最后一个元素,如果列表为空,返回null
//        E pollFirst(): 从 第一个位置 移除 元素
//        E pollLast(): 从 最后一个位置 移除 元素,如果列表为空,返回null// -------------- 作为普通List的
//    boolean add(E e):将指定元素添加到此列表的结尾。
//    E remove():获取并移除此列表的头(第一个元素)。//        void addFirst(E e): 将指定元素插入此列表的开头。
//        void addLast(E e): 将指定元素添加到此列表的结尾。
//        E getFirst(): 返回此列表的第一个元素。
//        E getLast(): 返回此列表的最后一个元素。
//        E removeFirst(): 移除并返回此列表的第一个元素。
//        E removeLast(): 移除并返回此列表的最后一个元素。// 这个API,大家觉得应不应该出现在Deque这个接口里面。 
//        boolean removeFirstOccurrence(Object o): 从此列表中移除第一次出现的指定元素
//        boolean removeLastOccurrence(Object o): 从列表中移除最后一次出现的指定元素
//        Iterator<E> descendingIterator():获取一个倒序的迭代器
//        E element():获取元素

他的特点:
在这里插入图片描述

实现类ArrayDeque

特点

  1. ArrayDeque是Deque的子实现
  2. 数据结构表现:队列,栈,双端队列
  3. 底层实现: 循环数组要理解一下循环数组的好处。
  4. 存储元素有序
  5. 存储元素可重复
  6. 不可存储null
    用法都是Deque的api。

现在解决栈和队列的问题基本上不会使用Stack而是推荐使用ArrayDeque。
主要原因:
1.性能问题,Stack继承Vector,而Vector是线程安全的,所以有额外的开销。
2.ArrayDeque提供更全面的功能,既能够用来作为栈,又可以作为队列使用
3.Stack现在被认为是过时了,现在一般用Deque来替代Stack。


实战中ArrayDeque怎么用

ArrayDeque 的主要方法

添加元素

addFirst(E e) / offerFirst(E e): 在前端添加元素
addLast(E e) / offerLast(E e): 在后端添加元素
add(E e) / offer(E e): 在后端添加元素(等同于 addLast/offerLast)
push(E e): 在前端添加元素(等同于 addFirst)

移除元素

removeFirst() / pollFirst(): 移除并返回前端元素
removeLast() / pollLast(): 移除并返回后端元素
remove() / poll(): 移除并返回前端元素(等同于 removeFirst/pollFirst)
pop(): 移除并返回前端元素(等同于 removeFirst)

查看元素(不移除):

getFirst() / peekFirst(): 返回前端元素
getLast() / peekLast(): 返回后端元素
peek(): 返回前端元素(等同于 peekFirst)
其他操作:

size(): 返回元素数量
isEmpty(): 检查是否为空
clear(): 清空所有元素
contains(Object o): 检查是否包含特定元素

算法题中的推荐用法:
当用作栈时

push(E e): 压栈
pop(): 出栈
peek(): 查看栈顶元素
isEmpty(): 检查栈是否为空
示例:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);
int top = stack.pop();
int peek = stack.peek();

当用作队列时

offer(E e): 入队
poll(): 出队
peek(): 查看队首元素
isEmpty(): 检查队列是否为空
示例:

Deque<Integer> queue = new ArrayDeque<>();
queue.offer(1);
int front = queue.poll();
int peek = queue.peek();

当用作双端队列时
offerFirst(E e) / offerLast(E e): 在前/后端添加元素
pollFirst() / pollLast(): 移除并返回前/后端元素
peekFirst() / peekLast(): 查看前/后端元素
isEmpty(): 检查是否为空
示例:

Deque<Integer> deque = new ArrayDeque<>();
deque.offerFirst(1);
deque.offerLast(2);
int front = deque.pollFirst();
int back = deque.pollLast();

推荐使用这些方法的原因:

它们在元素为 null 或双端队列为空时不会抛出异常,而是返回 null 或 false,这样可以简化错误处理。
这些方法名称清晰地表明了它们的用途和操作的位置(前端或后端)。
它们与 Queue 和 Stack 接口的方法名称保持一致,使代码更易读和理解。

所以说ArrayDeque非常万能,当你在做题的时候如果要用到相关的数据结构,就按上面的流程来走。可以模拟队列,栈,双端队列。

232.用栈实现队列

做题前注意:题目说了每个操作都是合法的,所以不要去做不合法的判断了

假设所有操作都是有效的 (例如,一个空的队列不会调用 pop 或者 peek 操作)。所以不用想这些极端情况。

题的本质:
后进先出实现先进先出
凭我们对栈的理解,显然一个栈是不能完成这个任务的,所以解题思路是用两个栈来完成。

解题思路:
一个栈为入队栈,一个栈为出队栈。
出队的逻辑
当出队栈存在内容时,出队栈的栈顶,即为第一个出队的元素。
如果出队栈内无元素,此时又需要出栈,那么入队栈的所有元素逐个弹出装入出队栈,然后弹出栈顶元素即可。
入队的逻辑:直接装入入队栈。

当两个栈都空了,就表示队空了。
下面是模拟的过程请添加图片描述
来看具体解法

class MyQueue {//这是定义接口,然后初始化指定实现类的写法。一般比较推荐这种写法Deque<Integer> stOut,stIn;//指定实现类为ArrayDeque,因为比较万能//ArrayDeque可以用来模拟栈,由于需要两个栈,那就开两个ArrayDeque。public MyQueue() {stIn = new ArrayDeque<>();stOut = new ArrayDeque<>();}public void push(int x) {//push直接放入进队栈stIn.push(x);}public int pop() {//出队就从出队栈出,如果出队栈为空,那就要把入队栈中的元素依次弹出然后压入入队栈。自己模拟一下就懂了。if(stOut.isEmpty()){while(!stIn.isEmpty()){stOut.push(stIn.pop());}}return stOut.pop();}//直接用pop方法,接住了再放回去public int peek() {int res = this.pop();stOut.push(res);return res;}//出队栈和入队栈都没有元素,那就是空。public boolean empty() {return stIn.isEmpty() && stOut.isEmpty();}
}

225. 用队列实现栈

题意:用两个队列实现栈即,用两个前进迁出实现后进先出。
思路:
看完这个图就懂了
请添加图片描述
进栈逻辑
就是直接入队1。
出栈逻辑
把队1里面的元素全部倒出来,然后最后一个元素出队。然后倒出来的元素又逐个入队2。之后又把队2全部出队又进队1中。

class MyStack {Deque<Integer> que1; // 和栈中保持一样元素的队列Deque<Integer> que2; // 辅助队列public MyStack() {que1 = new ArrayDeque<>();que2 = new ArrayDeque<>();}public void push(int x) {que1.offerLast(x);}public int pop() {int size = que1.size();size--;while (size-- > 0) {que2.offerLast(que1.peekFirst());que1.pollFirst();}int res = que1.pollFirst();que1 = que2;que2 = new ArrayDeque<>();return res;}public int top() {return que1.peekLast();}public boolean empty() {return que1.isEmpty();}
}

本题总结:这个题不难,对于我来说难的是不知道这么多api用哪个比较好,混用有没有风险。
因此这里做个总结:
队列(Queue)风格操作: 添加:offer(E e) 删除:poll() 查看:peek()

这组方法适合当你想要实现一个标准的队列(先进先出)时使用。它们在操作失败时不会抛出异常,而是返回特殊值。

双端队列(Deque)风格操作: 添加:offerFirst(E e), offerLast(E e) 删除:pollFirst(), pollLast() 查看:peekFirst(), peekLast()

当你需要在队列的两端进行操作时,这组方法很有用。它们也不会在操作失败时抛出异常。

抛出异常的操作: 添加:addFirst(E e), addLast(E e), add(E e) 删除:removeFirst(), removeLast(), remove() 查看:getFirst(), getLast()

这组方法在操作失败时会抛出异常(如 NoSuchElementException)。如果你希望立即捕获和处理异常,可以使用这组方法。

List风格操作: 添加:add(E e), add(int index, E element) 删除:remove(int index), remove(Object o) 查看:get(int index)

虽然 ArrayDeque 不是 List,但这些方法使其在某些情况下可以像 List 一样使用。

栈(Stack)风格操作: 添加:push(E e) (等同于 addFirst(E e)) 删除:pop() (等同于 removeFirst()) 查看:peek() (等同于 peekFirst())

当你使用 ArrayDeque 实现栈时,这组方法最为合适。

推荐的使用方式:

如果你在实现一个标准队列,使用 offer(), poll(), peek()。
如果你需要双端队列功能,使用 offerFirst(), offerLast(), pollFirst(), pollLast(), peekFirst(), peekLast()。
如果你在实现一个栈,使用 push(), pop(), peek()。
如果你希望操作失败时抛出异常,使用 add…, remove…, get… 系列方法。
记住,保持一致性是关键。选择一组方法后,尽量在整个实现中坚持使用这组方法,这样可以使你的代码更加清晰和易于理解。


20. 有效的括号

我的非常直观的写法:

class Solution {public boolean isValid(String s) {Deque<Character> stack = new ArrayDeque<>();for (char c : s.toCharArray()) {if (c == '(' || c == '[' || c == '{') {// 如果是左括号,入栈stack.push(c);} else {// 如果是右括号if (stack.isEmpty()) {// 如果栈为空,说明没有匹配的左括号,返回 falsereturn false;}// 检查栈顶元素是否匹配char top = stack.pop();if (c == ')' && top != '(') return false;if (c == ']' && top != '[') return false;if (c == '}' && top != '{') return false;}}// 最后检查栈是否为空,如果为空说明所有括号都匹配了return stack.isEmpty();}
}

1047. 删除字符串中的所有相邻重复项

class Solution {public String removeDuplicates(String s) {char[] str = s.toCharArray();Deque<Character> st = new ArrayDeque<>();for(int i = 0;i<str.length;i++){if(st.isEmpty()){st.push(str[i]);}else{char top = st.peek();if(str[i]==top){st.pop();}else{st.push(str[i]);}}}StringBuilder res = new StringBuilder();while(!st.isEmpty()){char c = st.pollLast();res.append(c);}return res.toString();}
}

今天做题刚总结的,也是我恶心了好久的问题:
ArrayDeque模拟这些结构的时候,光知道api有啥用还不够,方向更是恶心人。

重点

对于 ArrayDeque:双端队列

左边是队首(First)
右边是队尾(Last)

这意味着:

当用作队列时
左边是队首,右边是队尾
从右边(队尾)添加元素:offer(), add(), addLast()
从左边(队首)移除元素:poll(), remove(), removeFirst()

当用作栈时
右边是栈底,左边是栈顶。
从左边(队首)添加和移除元素:push() (等同于 addFirst()), pop() (等同于 removeFirst())
查看栈顶元素:peek() 或 peekFirst()

当做双端队列时:
左边时队首,右边时队尾

左边(队首/First)对应的方法
添加元素:
addFirst(e)
offerFirst(e)
push(e) (当用作栈时)

移除元素:
removeFirst()
pollFirst()
pop() (当用作栈时)

查看元素(不移除):
getFirst()
peekFirst()
peek() (当用作栈或队列时)

右边(队尾/Last)对应的方法
添加元素:
addLast(e)
offerLast(e)
add(e) (当用作队列时)
offer(e) (当用作队列时)

移除元素:
removeLast()
pollLast()

查看元素(不移除):
getLast()
peekLast()

另一组方法:poll和offer
左边(队首/First)对应的方法

添加元素:
offerFirst(e)

移除元素:
pollFirst()

查看元素(不移除):
peekFirst()

右边(队尾/Last)对应的方法

添加元素:
offerLast(e)
offer(e) (当用作队列时,等同于 offerLast(e))

移除元素:
pollLast()

查看元素(不移除):
peekLast()

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

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

研华工控机 UNO-2473G WIN7专业版系统下安装网卡驱动异常

基本配置&#xff1a;UNO-2473G、Windows 7 Pro 64bit 常规型嵌入式工控机&#xff0c;搭配Intel Atom™ E3845/Celeron J1900 处理器 第四代Intel Atom/Celeron J1900处理器&#xff0c;最高可达1.91/2.0 GHz&#xff0c;4GB DDR3L存储4/2 x GbE, 3 x USB 2.01 x USB 3.0或4…

OZON生活家居用品爆款新品

OZON生活家居用品爆款新品涵盖了多个方面&#xff0c;这些产品不仅满足了消费者对生活品质的追求&#xff0c;也反映了当前市场的热门趋势。以下是一些在OZON平台上备受关注的生活家居用品爆款新品&#xff1a; OZON生活家居用品爆款新品工具&#xff1a;D。DDqbt。COm/74rD T…

哪里有主机游戏店收费系统,佳易王电玩ps5ps4计时计费系统操作教程

哪里有主机游戏店收费系统&#xff0c;佳易王电玩ps5ps4计时计费系统操作教程 以下软件操作教程以&#xff0c;佳易王计时计费管理系统为例说明 软件文件下载可以点击最下方官网卡片——软件下载——试用版软件下载 一、软件程序图文讲解 1、主机游戏计时软件、电玩店计费软…

如何解决群晖Docker注册表查询失败/无法拉取镜像等问题

文章目录 📖 介绍 📖🏡 演示环境 🏡📒 问题概述 📒📒 解决方案 📒🔖 方法一🔖 方法二🔖 方法三⚓️ 相关链接 🚓️📖 介绍 📖 在群晖(Synology)NAS设备上使用Docker时,我们可能会遇到查询Docker注册表失败,无法拉取Docker镜像的问题。这种情况…

Error:sql: expected 1 arguments, got 2

一 背景 在测试一个API接口时&#xff0c;看到日志里面突然抛出一个错误&#xff1a;Error:sql: expected 1 arguments, got 2 看了下&#xff0c;对应的表里面是有相关数据的&#xff0c;sql语句放在mysql里面执行也是没问题&#xff01;那奇了怪了&#xff0c;为啥会产生这样…

商业地产规划vr实景还原系统更直观生动

在今日的建筑行业论坛中&#xff0c;众多业界专家深入探讨了建筑设计与展示的未来趋势。我们作为VR建筑展示领域的领军企业&#xff0c;始终秉持着对城市规划与发展的深度思考。多年来&#xff0c;我们积极参与并助力了无数城市片区的规划与建设。 回首2015年&#xff0c;我们与…

工业一体机为数字化工厂带来高效作业指导

随着工业4.0的浪潮席卷全球&#xff0c;数字化工厂的概念深入人心。在这一背景下&#xff0c;工业一体机作为数字化转型的重要一环&#xff0c;凭借其强大的功能和灵活的应用&#xff0c;为工厂实现高效作业指导提供了强大的助力。 一、工业一体机的优势&#xff1a;赋能数字化…

记录在Windows上安装Docker

在Windows上安装Docker时&#xff0c;可以选择使用不同的后端。 其中两个常见的选择是&#xff1a;WSL 2&#xff08;Windows Subsystem for Linux 2&#xff09;和 Hyper-V 后端。此外&#xff0c;还可以选择使用Windows容器。 三者的区别了解即可&#xff0c;推荐用WSL 2&…

汇川CodeSysPLC教程03-2-14 与HMI通信

硬件连接 PLC与HMI连接采用何种连接方式&#xff0c;通常是参考双方支持哪些接口。PLC&#xff08;可编程逻辑控制器&#xff09;与HMI&#xff08;人机界面&#xff09;之间的通讯方式主要有以下几种&#xff1a; 串行通讯&#xff08;Serial Communication&#xff09;&…

NVIDIA RTX 4090解析:卓越的性能表现带来全新的AI探索高度

前言 NVIDIA GeForce RTX 4090 在性能、效率和 AI 驱动的图形领域实现了质的飞跃。这款 GPU 采用 NVIDIA Ada Lovelace 架构&#xff0c;配备 24 GB 的 GDDR6X 显存。此外&#xff0c;RTX 4090还引入了多项创新技术。例如&#xff0c;它支持 DirectX12Ultimate&#xff0c;能够…

Linux基本命令的使用示例

目录 1实现效果&#xff1a;在downloads目录下创建1个空文件夹empty&#xff0c;创建1个空文件lake.txt&#xff0c;输入任意数据保存后退出 2实现效果&#xff1a;搜索包含关键字"泉眼"的行 3实现效果&#xff1a;重命名文件夹empty为full&#xff0c;复制文件cc…

利用 Python 解析pcap文件

1、问题背景 当面对处理网络数据包分析时&#xff0c;pcap文件作为一个常见的文件格式存储了网络数据包的详细记录&#xff0c;它常常被用来进行网络故障排查或安全分析。为了充分利用这些数据&#xff0c;我们需要对其进行解析并提取出有价值的信息&#xff0c;例如数据包类型…

AI自动生成PPT怎么用?5种提升演示效果的方法

随着#7月份我的同事一个个消失了#的话题热议&#xff0c;职场中的效率与变革再次成为焦点。 在忙碌的工作节奏中&#xff0c;AI自动生成PPT的软件悄然兴起&#xff0c;成为不少职场人的新宠。它们不仅简化了繁琐的PPT制作流程&#xff0c;更以高效、专业的姿态&#xff0c;助力…

Word文件打开密码设置:掌握这两种方法,保护你的文档安全

在日常工作和学习中&#xff0c;我们经常会使用Microsoft Word来创建和编辑文档。有时候&#xff0c;为了保护文档内容不被未经授权的人员查看或修改&#xff0c;我们通常会采用加密的方式来增加其安全性。那么Word文档怎么加密&#xff1f; 方法一&#xff1a;使用Word软件内置…

c++语法之函数重载

引例 我们在C语言里面写add函数的时候&#xff0c;只能支持一种类型的相加&#xff0c;除非我们创建多个add函数&#xff1a; 但是这样写并不方便&#xff0c;于是就有了c的函数重载。 函数重载 函数重载就是可以将多个参数类型、顺序、数量不同&#xff0c;实现逻辑相同的函…

Androidstudio开发,天气预报APP

1.项目功能思维导图 2. 项目涉及到的技术点 数据来源&#xff1a;和风天气API使用okhttp网络请求框架获取api数据使用gson库解析json数据使用RecyclerViewadapter实现未来7天列表展示和天气指数使用PopupMenu 实现弹出选项框使用动画定时器实现欢迎页倒计时和logo动画使用Text…

2023-2024华为ICT大赛中国区 实践赛网络赛道 全国总决赛 理论部分真题

Part1 数通模块(10题)&#xff1a; 1、如图所示&#xff0c;某园区部署了IPv6进行业务测试&#xff0c;该网络中有4台路由器&#xff0c;运行OSPFv3实现网络的互联互通&#xff0c;以下关于该OSPFv3网络产生的LSA的描述&#xff0c;错误的是哪一项?(单选题) A.R1的LSDB中将存在…

6.824/6.5840 的Debugging by Pretty Printing配置

TA的原文在&#xff1a;Debugging by Pretty Printing (josejg.com) 为了在WSL2中配置好打印运行日志&#xff0c;我可是忙活了一下午。可恶的log配置 首先是安装rich库Textualize/rich: Rich is a Python library for rich text and beautiful formatting in the terminal. …

Spring源码二十:Bean实例化流程三

上一篇Spring源码十九&#xff1a;Bean实例化流程二中&#xff0c;我们主要讨论了单例Bean创建对象的主要方法getSingleton了解到了他的核心流程无非是&#xff1a;通过一个简单工厂的getObject方法来实例化bean&#xff0c;当然spring在实例化前后提供了扩展如&#xff1a;bef…

arp缓存中毒实验

文章目录 一、相关知识1.什么是arp&#xff08;地址解析协议&#xff09;2.什么是免费arp&#xff08;1&#xff09;简介&#xff08;2&#xff09;主要应用&#xff08;3&#xff09;代码 3.什么是arp缓存中毒&#xff08;1&#xff09;简介&#xff08;2&#xff09;过程&…