专栏首页大闲人柴毛毛剑指offer代码解析——面试题22栈的压入、弹出序列

剑指offer代码解析——面试题22栈的压入、弹出序列

本题的详细分析过程均在代码的注释中:

import java.util.Stack;

/**
 * 题目:输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为栈的弹出顺序。
 * PS:设所有数字均不想等。
 * @author 大闲人柴毛毛
 * @date 2016年3月15日
 */
public class StackSequence {
	/**
	 * 栈的特点是不管入栈还是出栈,都只能对栈顶元素进行操作。
	 * 一个序列如果依次入栈,再依次出栈的话,序列将会被逆序输出。
	 * 但如果在入栈的过程中随机停止入栈操作,紧接着随机出栈n个元素,这样出栈顺序将会千变万化。
	 * 本题就是要求判断某一个数组是否属于指定入栈序列的出栈序列。
	 */
	
	/**
	 * 通过上述分析,最直观的方法就是穷举法,将一个入栈序列的所有出栈序列均罗列出来,然后判断这些序列中是否含有指定的出栈序列。
	 * 由于穷举法需要大量的时间、空间开销,因此要尽量避免。下面介绍更加高效的算法。
	 */
	
	/**
	 * 假设入栈序列为a,出栈序列为b。我们需要用一个全局变量count来记录当前匹配出栈序列的最大长度。
	 * 我们需要两个指针i和j分别指向序列a和b。
	 * 准备工作完毕,下面开始算法:
	 * 首先将a[i]入栈,
	 * 然后判断栈顶元素与b[j]是否相等,若二者相等,则该元素出栈,并count++表示已匹配到一位出栈元素,并使j++,然后重复上述操作,直到i扫描完序列a。
	 * 最后判断下匹配到的出栈元素个数是否与序列a的长度相同。
	 */
	
	/**
	 * 判断出栈序列是否符合指定入栈序列的某一种出栈顺序
	 * @param a 入栈序列
	 * @param b 出栈序列
 	 * @return 返回执行结果
	 */
	public static boolean isStackSequence(int[] a,int[] b){
		//若序列为空
		if(a==null || b==null || a.length<=0 || b.length<=0){
			System.out.println("序列为空!");
			return false;
		}
		
		//若入栈序列和出栈序列长度不等
		if(a.length != b.length){
			System.out.println("入栈序列与出栈序列长度不等!");
			return false;
		}
		
		//开始判断
		{
			//创建栈
			Stack<Integer> stack = new Stack<Integer>();
			int i=0,j=0;
			while(i<a.length){
				//若栈为空,则a[i]入栈
				stack.add(a[i++]);
				//判断栈顶元素和b[j]是否相等
				if(stack.peek()==b[j]){
					//栈顶元素出栈
					stack.pop();
					//j向后一位
					j++;
				}
			}
			
			//若栈中还有元素,则依次出栈,判断出栈序列与b剩余的序列是否相同
			while(!stack.isEmpty()){
				if(stack.pop()!=b[j])
					return false;
				else
					j++;
			}
			
			//判断栈是否为空,若为空表示成功匹配,若不为空表示失败
			if(!stack.isEmpty())
				return false; 
		}
		
		return true;
	}
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		//入栈序列
		int[] a = {1,2,3,4,5};
		//出栈序列
		int[] b = {4,3,5,1,2};
		System.out.println(isStackSequence(a,b));
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剑指offer代码解析——面试题24二叉搜索树的后序遍历序列

    本题有bug,欢迎大神指教! /** * 题目:输入一个整数数组,判断该数组书不是某二叉搜索数的后序遍历的结果。如果是返回true,否则返回false。假设输...

    大闲人柴毛毛
  • 0基础教你搭建一套可自动化构建的微服务框架(SpringBoot+Dubbo+Docker+Jenkins)

    本文你将学到什么? 本文将以原理+实战的方式,首先对“微服务”相关的概念进行知识点扫盲,然后开始手把手教你搭建这一整套的微服务系统。 项目完整源码下载 h...

    大闲人柴毛毛
  • 剑指offer代码解析——面试题21包含min函数的栈

    题目:实现一个栈,要求使用O(1)时间获取栈中最小值,O(1)执行pop、push操作。    分析:要获取栈的最小值,我们首先想到的思路就是使用一个全局...

    大闲人柴毛毛
  • 浏览器的UI线程

    所有用于更新用户界面的操作都是由浏览器的UI线程来完成 UI线程维护一个队列,把每个要更新UI的操作都做为一个任务添加到队列中,然后等UI线程空闲时再按顺序进...

    dys
  • Git与SVN的区别

    鉴于最近某些公司,某些人用着git做着svn的模式,觉得有意思,就随便找了篇帖子拿出来

    用户3765803
  • python操作文件写入内容

    py3study
  • 函数防抖和函数节流的简单实现和探讨

    上面有个问题就是如果再场景2那种情况,用户提交数据请求是发不出去的。而且不停点击,请求就一直不发,这显然是不科学的,我们就要改进这个函数了。

    flytam
  • 【项目.源码】深度学习视觉计算辅助良品检验,如何做布匹疵点识别?

    项目基于阿里云天池平台,提供数千份精标注布样数据,以“视觉计算辅助良品检验”为主题,聚焦布匹疵点智能识别,开展大数据与人工智能技术在布匹疵点识别上的应用探索,助...

    机器学习AI算法工程
  • kubeadm快速部署kubernetes(十九)

    安装完成后配置启动时的命令,否则docker会将iptables FORWARD chain的默认策略设置为DROP

    yuezhimi
  • Python自学成才之路 线程间协作 lock,condition,event的使用

    多线程并发时会出现线程安全问题,如果不解决线程并发安全问题可能会让程序出现不可预料的情况。python提供了一些工具包来解决多线程安全问题,下面介绍其中常见的工...

    我是李超人

扫码关注云+社区

领取腾讯云代金券