判断出栈顺序是否正确
>###输入两个整数序列，第一个序列表示栈的压入顺序，请判断输入的第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列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 判断栈顶元素 是否 等于 出栈元素
// 如果 入栈的下标 < 入栈数组的长度 并且 栈顶元素！= 素组元素说明 入栈没结束。
while( x < n && (stack.isEmpty() || stack.peek() !=popArr)){
stack.push(pushArr); //入栈
x++;
}
//如果栈顶元素 = 素组元素，说明要出栈了
if(stack.peek() == popArr){
stack.pop(); //出栈
}else{
return false; //不满足这个出栈顺序，说明是错误的出栈顺序
}
}
return true;
}
/*
* 首先正常入栈，先让入栈数组第一个元素入栈，入栈后判断 是否 和出栈数组的第一个元素相等，不相等
* 接着入栈。直到碰到一个相等的，然后开始出栈，出栈一个元素，则把出栈顺序向后挪一位，循环压栈出栈
* 压栈完成之后，如果这个栈里还有元素，说明没有完全出栈，则这个出栈顺序不对。
* 如果出栈顺序对，应该全部出栈了
*/
``` 优化了下算法，试试这个
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) {
// 如果入栈元素已经全部入栈了，仍然没有找到栈顶元素等于出栈元素，则出栈序列不是正确的出栈序列
if (index == pushArr.length) {
return false;
}
stack.push(pushArr);
}
// 栈顶元素等于出栈元素，则出栈
stack.pop();
}
// 如果最终栈为空，则出栈序列为正确的出栈序列，否则不是
return stack.isEmpty();
}
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) {
stack.pop(); // 出栈
i++;
}
}
return stack.isEmpty(); // 如果栈为空，则出栈序列可行
}
}
感谢楼主分享 好贴，支持！ 感谢楼主分享 前两天刚做这道题:lol
页:
[1]