22_栈的压入、弹出序列

分手后的思念是犯贱 2022-06-07 02:49 185阅读 0赞

> **题目：**输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
> 
> 例如：  
> 序列1,2,3,4,5是某栈的压入顺序  
> 序列4,5,3,2,1是该压栈序列对应的一个弹出序列；  
> 序列4,3,5,1,2就不可能是该压栈序列的弹出序列。  
> （注意：这两个序列的长度是相等的）
> 
> **思路：**  
> 1、如果下一个弹出的数字刚好是辅助栈的栈顶元素，那么直接弹出栈顶元素。  
> 2、如果下一个弹出的数字不是辅助栈的栈顶元素，就把压栈序列中还没有入栈的数字压入辅助栈，直到把下一个需要弹出的数字压入辅助栈的栈顶为止。  
> 3、如果所有元素都压入辅助栈了仍没有找到下一个弹出的数字，那么不可能为一个弹出序列。

import java.io.BufferedReader;
    import java.io.IOException;
    import java.io.InputStreamReader;
    import java.util.Stack;
    
    public class Solution{
        
    
        private static boolean isPopOrder(int[] push,int[] pop){
            Stack<Integer> stack = new Stack<Integer>();//辅助栈
            int i = 0 ;
            int j = 0;
            //第一个元素一定要压进去
            stack.push(push[i++]);
    
            while(j <= pop.length - 1){
                while(pop[j] != stack.peek()){
                    if(i == push.length)
                        return false;
                    stack.push(push[i++]);
                }
                j++;
                stack.pop();
            }   
            return true;
        }
    
        public static void main(String[] args) throws IOException {
            BufferedReader bf=new BufferedReader(
                    new InputStreamReader(System.in));
            System.out.println("入栈顺序：");
            String xString1 = bf.readLine();
            String[] num1 = xString1.split(",");
            System.out.println("出栈顺序：");
            String xString2 = bf.readLine();
            String[] num2 = xString2.split(",");
            int len1 = num1.length;
            int len2 = num2.length;
    
            boolean YesOrNo = false;
            if(len1!=len2 || xString1.equals("") || xString2.equals(""))
                YesOrNo = false;
            else{
                int[] num11 = new int[len1];
                int[] num22 = new int[len1];
                for(int i = 0;i<len1;i++){
                    num11[i] = Integer.parseInt(num1[i]);
                    num22[i] = Integer.parseInt(num2[i]);
                }
                YesOrNo =isPopOrder(num11,num22);           
            }
    
            if(YesOrNo == true)
                System.out.println("Yes!");
            else
                System.out.println("No!");
        }   
    }

![这里写图片描述][SouthEast] ![这里写图片描述][SouthEast 1] ![这里写图片描述][SouthEast 2]

![这里写图片描述][SouthEast 3] ![这里写图片描述][SouthEast 4] ![这里写图片描述][SouthEast 5] ![这里写图片描述][SouthEast 6]

[SouthEast]: https://img-blog.csdn.net/20171008112554340?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjQ4ODU2OTU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 1]: https://img-blog.csdn.net/20171008112646102?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjQ4ODU2OTU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 2]: /images/20220607/02407eefe9714fa9870c185f449b3632.png
[SouthEast 3]: https://img-blog.csdn.net/20171008113004872?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjQ4ODU2OTU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 4]: https://img-blog.csdn.net/20171008112849233?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjQ4ODU2OTU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 5]: https://img-blog.csdn.net/20171008112812462?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcXFfMjQ4ODU2OTU=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast
[SouthEast 6]: /images/20220607/cfdcd442d2614614936bc3f3db35cfba.png