判断出栈顺序是否正确

dxxbjl

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

整理题目要求 1、输入两个数组，一个代表入栈 ，另一个代表出栈 2、这两个数组各自没有重复的数据 3、要求判断第二个数组是否可为正确的出栈序列 思路： 每次入栈一个元素，就对比出栈序列的元素，如果入栈的这个元素 = 出栈 数组的元素，说明要出栈了。如果不等于的话就接着入栈。

 //给两个数组，一个是入栈的顺序，另一个是出栈的顺序
public boolean IsPopOrder(int [] pushArr, int [] popArr) {
    int n = pushA.length; //入栈的数组的长度
    int x =0; //入栈的下标

    //创建一个栈
    Stack<Integer> stack = new Stack<>();

    for(int i=0;i<n ;i++){   //入栈

        //stack.isEmpty()判断是否为空栈
        //stack.peek() !=popArr[i] 判断栈顶元素 是否 等于 出栈元素
        // 如果 入栈的下标 < 入栈数组的长度 并且 栈顶元素！= 素组元素  说明 入栈没结束。
        while( x < n && (stack.isEmpty() || stack.peek() !=popArr[i])){
            stack.push(pushArr[x]);   //入栈
            x++;
        }

        //如果栈顶元素 = 素组元素，说明要出栈了
        if(stack.peek() == popArr[i]){
            stack.pop();    //出栈
        }else{
            return false;   //不满足这个出栈顺序，说明是错误的出栈顺序
        }
    }
    return true;
}

/*
*   首先正常入栈，先让入栈数组第一个元素入栈，入栈后判断 是否 和出栈数组的第一个元素相等，不相等
*   接着入栈。直到碰到一个相等的，然后开始出栈，出栈一个元素，则把出栈顺序向后挪一位，循环压栈出栈
*   压栈完成之后，如果这个栈里还有元素，说明没有完全出栈，则这个出栈顺序不对。
*   如果出栈顺序对，应该全部出栈了
*/

lyimore

优化了下算法，试试这个
public boolean isPopOrder(int[] pushArr, int[] popArr) {
    Stack<Integer> stack = new Stack<>();
    int index = 0; // 入栈元素的下标
    for (int i = 0; i < popArr.length; i++) {
        // 如果栈顶元素不等于出栈元素，则一直将入栈序列中的元素入栈，直到栈顶元素等于出栈元素
        while (stack.isEmpty() || stack.peek() != popArr[i]) {
            // 如果入栈元素已经全部入栈了，仍然没有找到栈顶元素等于出栈元素，则出栈序列不是正确的出栈序列
            if (index == pushArr.length) {
                return false;
            }
            stack.push(pushArr[index++]);
        }
        // 栈顶元素等于出栈元素，则出栈
        stack.pop();
    }
    // 如果最终栈为空，则出栈序列为正确的出栈序列，否则不是
    return stack.isEmpty();
}

17689207110

[Java] 纯文本查看 复制代码

import java.util.*;

public class StackSequence {
    public static void main(String[] args) {
        int[] pushSequence = {1, 2, 3, 4, 5}; // 入栈序列
        int[] popSequence = {4, 5, 3, 2, 1}; // 出栈序列
        boolean isPossible = checkStackSequence(pushSequence, popSequence);
        System.out.println(isPossible); // 输出 true
    }

    public static boolean checkStackSequence(int[] pushSequence, int[] popSequence) {
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        for (int num : pushSequence) {
            stack.push(num); // 入栈
            while (!stack.isEmpty() && stack.peek() == popSequence[i]) {
                stack.pop(); // 出栈
                i++;
            }
        }
        return stack.isEmpty(); // 如果栈为空，则出栈序列可行
    }
}

zha3750

感谢楼主分享

WSSHH

好贴，支持！

13607065647

感谢楼主分享

nextlevel

前两天刚做这道题