输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
例如序列 1,2,3,4,5 是某栈的压入顺序,序列 4,5,3,2,1 是该压栈序列对应的一个弹出序列,但 4,3,5,1,2 就不可能是该压栈序列的弹出序列。
用一个栈来模拟栈的入和出
先进第一个数字,判断此字段是否属于弹出的字段第一个,不是的话就进第二个数字
以此类推,在第n位置处找到了弹出字段的首字段,弹出,判断倒数第二个字段是否是弹出
字段的第二个字段是的话继续弹出,不是的话,继续add字符
import java.util.Stack;
public class Stackpath {
public static void main(String[] args) {
Stackpath stackpath=new Stackpath();
int[]num={1,2,3,4,5};
int []path={4,5,3,2,1};
boolean x=stackpath.getpath(num,path);
System.out.println(x);
}
public boolean getpath(int []num,int []path){
int n=num.length;
Stack<Integer> stack=new Stack<>();
for (int pushIndex=0, popIndex=0;pushIndex<n;pushIndex++){
stack.push(num[pushIndex]);
while (popIndex<n&&!stack.isEmpty()&&stack.peek()==path[popIndex]){
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}