剑指Offer之栈的压入、弹出序列

题目描述

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

基本思路

　　设置两个索引pushIndex和popIndex，分别用于记录入栈元素的处理位置和出栈元素的处理位置，设置一个循环，当入栈元素还未全部入栈的条件下，如果栈为空，或者栈顶的元素不与当前处理的元素相等，则一直进行入栈操作，直到入栈元素全部入栈或者找到一个与栈顶元素相等的元素。如果在上一步入栈过程中找到了与出栈与出栈元素相等的元素。将元素出栈，处理下一个元素。如果没有找到与出栈元素相等的元素，说明这个出栈顺序是不合法的，就返回false。

Java代码

package com.swordOffer.stackPushPopOrder14;import java.util.Scanner; import java.util.Stack;/*** Created by Feng on 2017/5/11.* 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。* 假设压入栈的所有数字均不相等。例如列1、2、3、4、5是某栈的压栈序列，序列5、4、3、2、1* 是该栈对应的一个弹出序列，但4、3、5、1、2就不可能是该压栈序列的弹出序列。*/ public class StackPushPopOrder {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {int n = sc.nextInt();//数组的大小int[] push = new int[n];//表示栈的压入顺序for (int i = 0; i < n; i++) {push[i] = sc.nextInt();}int[] pop = new int[n];//弹出顺序for (int i = 0; i < n; i++) {pop[i] = sc.nextInt();}boolean result = isPopOrder(push, pop);System.out.println(result);}}/*** 判断第二个序列是否为该栈的探春序列** @param push* @param pop* @return*/private static boolean isPopOrder(int[] push, int[] pop) {boolean flag = false;Stack<Integer> stack = new Stack<>();// 输入校验，参数不能为空，并且两个数组中必须有数字，并且两个数组中的数字个数相同// 否则返回falseif (push == null || pop == null || pop.length == 0 || push.length == 0|| push.length != pop.length) {return false;}// 用于记录入栈数组元素的处理位置int pushIndex = 0;// 用于记录出栈数组元素的处理位置int popIndex = 0;// 如果还有出栈元素要处理while (popIndex < pop.length) {// 入栈元素还未全部入栈的条件下，如果栈为空，// 或者栈顶的元素不与当前处理的相等，// 则一直进行栈操作，// 直到入栈元素全部入栈或者找到了一个与当出栈元素相等的元素while (pushIndex < push.length && (stack.isEmpty() ||stack.peek() != pop[popIndex])) {// 入栈数组中的元素入栈 stack.push(push[pushIndex]);// 指向下一个要处理的入栈元素pushIndex++;}//如果在上一步的入栈过程中找到了与出栈的元素相等的元素if (stack.peek() == pop[popIndex]) {// 将元素出栈 stack.pop();// 处理下一个出栈元素popIndex++;}// 如果没有找到与出栈元素相等的元素，说明这个出栈顺序是不合法的// 就返回falseelse {return false;}}return true;} }

 

转载于:https://www.cnblogs.com/lfeng1205/p/6840265.html

总结

以上是生活随笔为你收集整理的剑指Offer之栈的压入、弹出序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。