题目:栈的压入,弹出序列
要求:输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
模拟入栈和出栈的过程，查看是否一致。详细思路如下：
举例：入栈序列为1,2,3,4,5 某一序列为 2,3,1,4,5 。首先选择1 入栈，然后查看序列2 是否相同，不同说明没有出栈，继续入栈2，继续查看 相同，说明2出栈，然后继续查看是否相同1和3不同，继续入栈3，查看和序列2中的头元素3一致，出栈，继续查看序列1中的1，和序列2中的1 一致，然后出栈。。。直到最终序列2为空；如果最后发现序列1为空的时候序列2中仍然有元素，则说明不是合法出栈序列；
1 import java.util.ArrayList; 2 import java.util.Stack; 3 public class Solution { 4 public boolean IsPopOrder(int [] pushA,int [] popA) { 5 //先考虑特殊情况 6 if(pushA.length != popA.length) return false; 7 if(pushA.length==0 || popA.length==0) return false; 8 //模拟堆栈的过程 9 Stack temp = new Stack(); 10 int length = pushA.length; 11 int popindex =0; 12 for(int i=0;i<length;i++){ 13 temp.push(pushA[i]); 14 while((!temp.empty()) && ((int)temp.peek() == popA[popindex])){ 15 temp.pop(); 16 popindex++; 17 } 18 } 19 //最终判断堆栈是否为空即可 20 return temp.empty(); 21 } 22 }
本地编译代码:
1 import java.util.*; 2 import java.util.Stack; 3 public class Solution516Day1 { 4 public static boolean IsPopOrder(int [] pushA,int [] popA) { 5 //先考虑特殊情况 6 if(pushA.length != popA.length) return false; 7 if(pushA.length==0 || popA.length==0) return false; 8 //模拟堆栈的过程 9 Stack<Integer> temp = new Stack<Integer>(); 10 int length = pushA.length; 11 int popindex =0; 12 for(int i=0;i<length;i++){ 13 temp.push(pushA[i]); 14 while((!temp.empty()) && ((int)temp.peek() == popA[popindex])){ 15 temp.pop(); 16 popindex++; 17 } 18 } 19 //最终判断堆栈是否为空即可 20 return temp.empty(); 21 } 22 public static void main(String [] args){ 23 Scanner sc = new Scanner(System.in); 24 System.out.println("请输入两个整数序列的长度(默认两个序列长度相同)"); 25 int length = sc.nextInt(); 26 System.out.println("请输入 入栈整数序列"); 27 int[] pushA = new int[length]; 28 for(int i=0;i<length;i++){ 29 pushA[i]=sc.nextInt(); 30 } 31 System.out.println("请输入 出栈个整数序列"); 32 int[] pushB = new int[length]; 33 for(int j=0;j<length;j++){ 34 pushB[j]=sc.nextInt(); 35 } 36 sc.close(); 37 boolean result= IsPopOrder(pushA,pushB); 38 System.out.println("出栈序列是否是入栈序列的一个出栈顺利"+result); 39 40 } 41 }
思考1:给出入栈顺序,请给出所有的出栈可能(TODOLIST) 代码该如何写
思考2:对于选择题或者判断题,去迅速判断
原文：https://www.cnblogs.com/shareidea94/p/10877601.html
