【刷题-牛客】出栈、入栈的顺序匹配 (代码+动态演示)

简介: 【刷题-牛客】出栈、入栈的顺序匹配 (代码+动态演示)

【刷题-牛客】出栈、入栈的顺序匹配 (代码+动态演示)


💗题目描述 💗:

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

  1. 0<=pushV.length == popV.length <=1000
  2. -1000<= pushV [i]<=1000
  3. pushV 的所有数字均不相同

💗解释 : 其实这个题目的意思就是把通常经常遇见的判断题 已知入栈顺序(入栈的同时可以出栈),判断不可能的出栈顺序 ,封装成一个方法,然后我们通过此方法,传入 入栈顺序可能的出栈顺序,方法返回 true 代表 该出栈顺序是可能的, 返回false 代表 该出栈顺序是不可能的 .

解题思路

遍历入栈顺序进行压栈,压栈之后遍历可能的出栈顺序,如果遍历到的元素若与此时栈顶元素相同则表示应该出栈,然后继续后移判断;若不相同则表示此时不用出栈,转而继续进行压栈操作.

接下来我将通过动态图演示具体的过程,同时会将伪代码先写出来

例子
入栈顺序 : 1  2  3  4  5 
可能的出栈顺序 : 4  3   5  1  2

动图演示


  • 可能出现的bug

我们通过观察伪代码中的while循环语句的条件,我们并没有考虑如果栈为空和 j 下标越界的情况 , 为什么要考虑这两种情况呢 ?

原因 : 我们在需要对这个代码进行测试 , 也就是看这个代码是否满足所有测试用例可能出现的情况.


当入栈顺序和可能的出栈顺序是相反的 : 
可能的出栈顺序② : 5  4  3  2  1
入栈顺序  : 1  2  3  4  5

当栈为空的时候,我们就不能再进入while循环的条件语句去执行s.peek()==popV[j]了,所以我们可以在while条件

中增加一个条件 && != s.empty()


当入栈顺序和可能的出栈顺序是相同的 :
可能的出栈顺序③ : 1  2  3  4  5
入栈顺序  : 1  2  3  4  5

此时在while循环中执行完s.pop() 之后,需要继续执行 j++ ,那么 j 就变成了popV.length了. 所以此时我们不能进入while循环的条件语句去执行s.peek() == popV[j] 了,因为此时的 j 会出现下标越界异常,所以我们可以增加一个条件&& j<popV.length


  • 继续完善

由于题目要求 0<=pushV.length == popV.length <=1000 那么我们给方法传入的两个数组参数是可能为空的,为了提升代码的健壮性,我们可以可再继续加一个 if 条件语句 <font color=‘red’ return false;`


完整代码

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
     *
     * 
     * @param pushV int整型一维数组 
     * @param popV int整型一维数组 
     * @return bool布尔型
     */
    public boolean IsPopOrder (int[] pushV, int[] popV) {
        Stack<Integer> stack = new Stack<>();
        int j = 0;
        if(pushV.length == 0 || popV.length == 0) return false;
        for (int i = 0; i < pushV.length; i++) {
            stack.push(pushV[i]);
                while(j<popV.length&& !stack.empty() && stack.peek().equals(popV[j])){
                    stack.pop();
                    j++;
                }
        }
      return stack.empty();
    }
}

多组测试

  • 测试一

  • 测试二

  • 测试三

  • 测试四


求三连!!!

目录
相关文章
|
2月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
264 9
|
2月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
42 1
|
4天前
|
存储 C语言 C++
【C++数据结构——栈与队列】顺序栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现顺序栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 1.初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储
114 75
|
4天前
|
存储 C++ 索引
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
【数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】初始化队列、销毁队列、判断队列是否为空、进队列、出队列等。本关任务:编写一个程序实现环形队列的基本运算。(6)出队列序列:yzopq2*(5)依次进队列元素:opq2*(6)出队列序列:bcdef。(2)依次进队列元素:abc。(5)依次进队列元素:def。(2)依次进队列元素:xyz。开始你的任务吧,祝你成功!(4)出队一个元素a。(4)出队一个元素x。
25 13
【C++数据结构——栈与队列】环形队列的基本运算(头歌实践教学平台习题)【合集】
|
4天前
|
存储 C语言 C++
【C++数据结构——栈与队列】链栈的基本运算(头歌实践教学平台习题)【合集】
本关任务:编写一个程序实现链栈的基本运算。开始你的任务吧,祝你成功!​ 相关知识 初始化栈 销毁栈 判断栈是否为空 进栈 出栈 取栈顶元素 初始化栈 概念:初始化栈是为栈的使用做准备,包括分配内存空间(如果是动态分配)和设置栈的初始状态。栈有顺序栈和链式栈两种常见形式。对于顺序栈,通常需要定义一个数组来存储栈元素,并设置一个变量来记录栈顶位置;对于链式栈,需要定义节点结构,包含数据域和指针域,同时初始化栈顶指针。 示例(顺序栈): 以下是一个简单的顺序栈初始化示例,假设用C语言实现,栈中存储整数,最大
28 9
|
4天前
|
C++
【C++数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】
【数据结构——栈和队列】括号配对(头歌实践教学平台习题)【合集】(1)遇到左括号:进栈Push()(2)遇到右括号:若栈顶元素为左括号,则出栈Pop();否则返回false。(3)当遍历表达式结束,且栈为空时,则返回true,否则返回false。本关任务:编写一个程序利用栈判断左、右圆括号是否配对。为了完成本关任务,你需要掌握:栈对括号的处理。(1)遇到左括号:进栈Push()开始你的任务吧,祝你成功!测试输入:(()))
23 7
|
2月前
|
存储 缓存 算法
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
79 5
|
2月前
|
存储 算法 Java
数据结构的栈
栈作为一种简单而高效的数据结构,在计算机科学和软件开发中有着广泛的应用。通过合理地使用栈,可以有效地解决许多与数据存储和操作相关的问题。
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
73 1
|
2月前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境,每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用,每当调用一个函数,就会在栈中添加一个新的执行上下文。