【P4387 【深基15.习9】验证栈序列 java版本

2024-08-29 01:36

本文主要是介绍【P4387 【深基15.习9】验证栈序列 java版本,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

文章目录

  • 【P4387 【深基15.习9】验证栈序列 java版本
    • 题目描述
    • 输入格式
    • 输出格式
    • 样例 #1
      • 样例输入 #1
      • 样例输出 #1
    • 算法分析
    • 代码实现
  • 结语

【P4387 【深基15.习9】验证栈序列 java版本

题目描述

给出两个序列 pushed 和 poped 两个序列,其取值从 1 到 n ( n ≤ 100000 ) n(n\le100000) n(n100000)。已知入栈序列是 pushed,如果出栈序列有可能是 poped,则输出 Yes,否则输出 No。为了防止骗分,每个测试点有多组数据,不超过 5 5 5 组。

输入格式

第一行一个整数 q q q,询问次数。

接下来 q q q 个询问,对于每个询问:

第一行一个整数 n n n 表示序列长度;

第二行 n n n 个整数表示入栈序列;

第三行 n n n 个整数表示出栈序列;

输出格式

对于每个询问输出答案。

样例 #1

样例输入 #1

2
5
1 2 3 4 5
5 4 3 2 1
4
1 2 3 4
2 4 1 3

样例输出 #1

Yes
No

算法分析

解决这个问题的关键在于理解栈的后进先出(LIFO)特性。我们可以模拟栈的入栈和出栈操作来验证 poped 序列是否可能由 pushed 序列生成。

  1. 使用一个栈来模拟入栈过程。
  2. 遍历 pushed 序列,将元素依次压入栈中。
  3. 在压栈的同时,检查栈顶元素是否与 poped 序列的当前索引位置的元素相同。
  4. 如果相同,弹出栈顶元素,并移动到 poped 序列的下一个元素。
  5. 重复步骤3和4,直到遍历完 pushed 序列。
  6. 如果在任何时候栈顶元素与 poped 序列不匹配,或者在遍历完 pushed 序列后栈不为空,则输出 No;否则输出 Yes

代码实现

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.StreamTokenizer;
import java.util.Stack;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));static StreamTokenizer st = new StreamTokenizer(in);public static void main(String[] args) throws IOException {st.nextToken();int t = (int) st.nval;while (t-- > 0) {st.nextToken();int n = (int) st.nval;int[] arr = new int[n];int[] now = new int[n];for (int i = 0; i < n; i++) {st.nextToken();arr[i] = (int) st.nval;}for (int i = 0; i < n; i++) {st.nextToken();now[i] = (int) st.nval;}Stack<Integer> stack = new Stack<>();int index = 0;for (int i = 0; i < n; i++) {stack.push(arr[i]);while (!stack.isEmpty() && stack.peek() == now[index]) {index++;stack.pop();}}if (stack.isEmpty()) {out.write("Yes\n");} else {out.write("No\n");}}out.flush();}
}

结语

本题是一个典型的栈应用问题,通过模拟栈的操作,我们可以验证两个序列是否匹配。希望这篇博客能帮助你更好地理解栈的工作原理以及如何在实际问题中应用栈。如果你有任何问题或建议,请在下方留言,我会尽快回复。

版权声明:本博客内容为原创,转载请保留原文链接及作者信息。

这篇关于【P4387 【深基15.习9】验证栈序列 java版本的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1116472

相关文章

一文详解SpringBoot中控制器的动态注册与卸载

《一文详解SpringBoot中控制器的动态注册与卸载》在项目开发中,通过动态注册和卸载控制器功能,可以根据业务场景和项目需要实现功能的动态增加、删除,提高系统的灵活性和可扩展性,下面我们就来看看Sp... 目录项目结构1. 创建 Spring Boot 启动类2. 创建一个测试控制器3. 创建动态控制器注

Java操作Word文档的全面指南

《Java操作Word文档的全面指南》在Java开发中,操作Word文档是常见的业务需求,广泛应用于合同生成、报表输出、通知发布、法律文书生成、病历模板填写等场景,本文将全面介绍Java操作Word文... 目录简介段落页头与页脚页码表格图片批注文本框目录图表简介Word编程最重要的类是org.apach

Spring Boot中WebSocket常用使用方法详解

《SpringBoot中WebSocket常用使用方法详解》本文从WebSocket的基础概念出发,详细介绍了SpringBoot集成WebSocket的步骤,并重点讲解了常用的使用方法,包括简单消... 目录一、WebSocket基础概念1.1 什么是WebSocket1.2 WebSocket与HTTP

SpringBoot+Docker+Graylog 如何让错误自动报警

《SpringBoot+Docker+Graylog如何让错误自动报警》SpringBoot默认使用SLF4J与Logback,支持多日志级别和配置方式,可输出到控制台、文件及远程服务器,集成ELK... 目录01 Spring Boot 默认日志框架解析02 Spring Boot 日志级别详解03 Sp

java中反射Reflection的4个作用详解

《java中反射Reflection的4个作用详解》反射Reflection是Java等编程语言中的一个重要特性,它允许程序在运行时进行自我检查和对内部成员(如字段、方法、类等)的操作,本文将详细介绍... 目录作用1、在运行时判断任意一个对象所属的类作用2、在运行时构造任意一个类的对象作用3、在运行时判断

java如何解压zip压缩包

《java如何解压zip压缩包》:本文主要介绍java如何解压zip压缩包问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java解压zip压缩包实例代码结果如下总结java解压zip压缩包坐在旁边的小伙伴问我怎么用 java 将服务器上的压缩文件解压出来,

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具

Spring WebFlux 与 WebClient 使用指南及最佳实践

《SpringWebFlux与WebClient使用指南及最佳实践》WebClient是SpringWebFlux模块提供的非阻塞、响应式HTTP客户端,基于ProjectReactor实现,... 目录Spring WebFlux 与 WebClient 使用指南1. WebClient 概述2. 核心依

Spring Boot @RestControllerAdvice全局异常处理最佳实践

《SpringBoot@RestControllerAdvice全局异常处理最佳实践》本文详解SpringBoot中通过@RestControllerAdvice实现全局异常处理,强调代码复用、统... 目录前言一、为什么要使用全局异常处理?二、核心注解解析1. @RestControllerAdvice2

Spring IoC 容器的使用详解(最新整理)

《SpringIoC容器的使用详解(最新整理)》文章介绍了Spring框架中的应用分层思想与IoC容器原理,通过分层解耦业务逻辑、数据访问等模块,IoC容器利用@Component注解管理Bean... 目录1. 应用分层2. IoC 的介绍3. IoC 容器的使用3.1. bean 的存储3.2. 方法注