出栈序列的判断，以及栈混洗。

栈：栈的结构是很简单的，简单来说就是一个先入后出的列表。
栈混洗：一个放在栈序列入中间栈再出中间栈得到一个新的栈。

那么如何判断一个序列是否是出栈序列呢？
1.简单判断：
首先，我们拿一种简单情况来看
初始栈：(1,2,3] 很明显新的栈不可能是[3,1,2)
圆括号代表栈顶
从这里我们就能看出， 对于（…i,…j…..,k..]，只要序列为[….k,…i,…j)那么这个序列一定不是出栈序列。
通常的面试题都会这样说：按 1,2,3,4,5的顺序入栈，那么正好对应了（…i,…j…..,k..]，出栈序列不可能为4,5,3,1,2 对应了 [….k,…i,…j)，这样你在判断的时候就可以一目了然

2.通过程序来判断

package dataQingHua;

import java.util.Scanner;
import java.util.Stack;

public class IsStackArrangement {

    /*
         * 给一个初始的入栈序列，其次序即为元素的入栈次序，栈顶元素可以随时出栈，每个元素只能入栈依次。输入一个入栈序列，后面依次输入多个序列，请判断这些序列是否为所给入栈序列合法的出栈序列。
            例如序列1，2，3，4，5是某栈的压入顺序，序列4，5，3，2，1是该压栈序列对应的一个出栈序列，但4，3，5，1，2就不可能是该序列的出栈序列。假设压入栈的所有数字均不相等。
        输入
        第一行输入整数n(1<=n<=10000)，表示序列的长度。
        第二行输入n个整数，表示栈的压入顺序。
        第三行输入整数t（1<=t<=10）。
        后面依次输入t行，每行n个整数，表示要判断的每一个出栈序列。
    输出
    对应每个测试案例输出一行，如果由初始入栈序列可以得到该出栈序列，则输出yes，否则输出no。

         * 分析：要证明一个序列是否是 栈混洗 后的序列，那么只要 模拟 栈混洗的过程就好了。
         * 1>栈混洗只能入栈出栈，因此绝对不能取到栈顶以下的元素。所以判断是否为栈混洗的条件就是
         *  1.我们希望从栈中出栈的元素不在栈顶，且初始栈又是空栈。那么此时就可以判断是错误序列了。
         *  
         * */

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        isStack1();
    }

    public static void isStack1(){

        Stack<Integer> a=new Stack<Integer>();

        Stack<Integer> o=new Stack<Integer>();

        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();              //原始序列的长度。
        int t=0;
        int[] arr=new int[n];
        for(int i=0;i<n;i++){
            t=sc.nextInt();
            arr[i]=t;
        }


        int m=sc.nextInt();

        while (m-->0)
        {
            for(int i=arr.length-1;i>=0;i--){
                a.push(arr[i]);
            }
            int  c; 
                    boolean flag = false;       
            for (int i = 0; i<n; i++)
            {
                t=sc.nextInt();          //
                if (flag)
                    continue;               
                if (o.empty())        
                {
                    /*if (a.empty())            //这里其实不需要
                    {
                        flag = true;         
                        continue;
                    }*/
                    o.push(a.peek());        
                    a.pop();
                }
                while (!o.empty())          
                {
                    c = o.peek();      
                    if (c == t)             //如果栈顶元素和我们期望的元素一致，那么就出栈，并判断下一个数。
                    {
                        o.pop();
                        break;             
                    }
                    else             //如果不一致，看看a中是否还有元素，没有的话，判断 不符合，跳出循环。
                    {
                        if (a.empty())
                        {
                            flag = true;
                            break;
                        }
                        o.push(a.peek());    //有就继续，往o中压栈，改变o的栈顶。继续循环。
                        a.pop();
                    }
                }
            }

            if(!o.empty()){
                o.pop();
            }
            if(!a.empty()){
                a.pop();
            }
            if (flag)
                System.out.println("no");
            else
                System.out.println("yes");

        }

    }


}

基本步骤已经在代码中解释了。

值得注意的是，这里要判断多个序列是否是出栈序列，那么每一次都要初始化原序列。我一开始直接用两个栈A,B来作为变量，每次判断一个序列的时候，都用A=B,B存放的是初始化好的原序列。结果出现问题了，大意之下，忘了java变量保存的是引用，改变a的同时，b也跟着改变了。

for(int i=arr.length-1;i>=0;i--){
                a.push(arr[i]);
            }

还是通过一次次赋值来重新初始化序列。还没想到更好的办法。